A binary expression tree is a specific kind of a binary tree used to represent expressions. Two common types of expressions that a binary expression tree can represent are algebraic and boolean. These trees can represent expressions that contain both unary and binary operators.
Each node of a binary tree, and hence of a binary expression tree, has zero, one, or two children. This restricted structure simplifies the processing of expression trees.
The leaves of a binary expression tree are operands, such as constants or variable names, and the other nodes contain operators. These particular trees happen to be binary, because all of the operations are binary, and although this is the simplest case, it is possible for nodes to have more than two children. It is also possible for a node to have only one child, as is the case with the unary minus operator. An expression tree, T, can be evaluated by applying the operator at the root to the values obtained by recursively evaluating the left and right subtrees.
Algebraic Expression Trees
An algebraic expression such as (3 * 7) + 9 consists of:Operands such as 3, 7, 9 or x, y, z,
Binary Operators such as +, – , *, /, DIV, MOD, ^
Unary Operators such as –
Algebraic expressions can be represented using a binary expression tree where:
- Each node is an operator,
- Each leaf is an operand.
Boolean expressions
Boolean expressions are represented very similarly to algebraic expressions, the only difference being the specific values and operators used. Boolean expressions use true and false as constant values, and the operators include AND OR NOT
To generate an expression tree, given an expression, we first convert the expression to its postfix form. From the postfix expression, we read one symbol at a time from left to right. If the current symbol is an operand, then we push a tree of one node consisting of the operator onto a stack. If the symbol is an operator, then we pop two trees from the stack and create a tree with the root containing the operator and the result of the pop operations as the right and the left subtrees in that order. The resulting tree is again pushed onto the stack. When we have read all the symbols, the equivalent expression tree is the only element in the stack and a pop operation would give us the tree. The following example illustrates the algorithm. Let the postfix expression be a b + f - c d * e + /.
When we first read 'a' and 'b' in that order and create two trees containing a single node 'a' and 'b' respectively.
These trees are then pushed on to the stack in that order.
When we encounter the '+' operator, we pop two trees from the stack, creating a tree with '+' as the root and the two trees as the right and the left childs respectively.
On reading the operand 'f', we create a tree with 'f' as a single node and push it on to the stack.
On reading a '-' we create the tree with '-' as the root and the two previously created trees as its children and push the new tree onto the stack.
Similarly, on reading 'c' and 'd', the stack has three trees; '-' and two new trees corresponding to nodes 'c' and 'd'.
On reading a '*', the stack has two trees; '-' and a new tree consisting of '*' as the root and 'c' and 'd' as its children.
Continuing further, we create the tree with '+' as the root. On reading the last '/', the final tree is created
If we traverse the expression in in order we get infix expression, if we traverse in pre order. We get prefix expression and we traverse in post order we get post fix expression.
Example
(5-x)*y+6/(x + z)
Alternately click the below link to input an expression and see how the tree is constructed
No comments:
Post a Comment