Draw an Expression Tree a B C D P Q

A binary expression tree is a specific application of a binary tree to evaluate certain expressions. Two common types of expressions that a binary expression tree can represent are algebraic ^[1] and boolean. These trees can represent expressions that contain both unary and binary operators. ^[1]

In general, expression trees are special kind of binary trees. Binary tree is a tree in which all nodes contain zero, one or two children. The expression trees have been implemented as binary trees mainly because binary trees allows you to quickly find what you are looking for. The upper limit of steps necessary to find required information in binary tree equals to log₂N, where N denotes the number of all nodes in a tree.

Contents

• 1 Overview
  • 1.1 Traversal
    • 1.1.1 Infix Traversal
    • 1.1.2 Postfix Traversal
    • 1.1.3 Prefix Traversal
• 2 Construction of an Expression Tree
  • 2.1 Example
• 3 Algebraic expressions
• 4 Boolean expressions
• 5 See also
• 6 References

Overview

Expression Tree

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. ^[2]

Traversal

An algebraic expression can be produced from a binary expression tree by recursively producing a parenthesized left expression, then printing out the operator at the root, and finally recursively producing a parenthesized right expression. This general strategy (left, node, right) is known as an in-order travesal. An alternate traversal strategy is to recursively print out the left subtree, the right subtree, and then the operator. This traversal strategy is generally known as post-order traversal. A third strategy is to print out the operator first and then recursively print out the left and right subtree. ^[2]

These three standard depth-first traversals are representations of the three different expression formats: infix, postfix, and prefix. An infix expression is produced by the inorder traversal, a postfix expression is produced by the post-order traversal, and a prefix expression is produced by the pre-order traversal. ^[3]

Infix Traversal

When an infix expression is printed, an opening and closing parenthesis must be added at the beginning and ending of each expression. As every subtree represents a subexpression, an opening parenthesis is printed at its start and the closing parenthesis is printed after processing all of its children.

Pseudocode:

Algorithm infix            (tree)            /*Print the infix expression for an expression tree. Pre : tree is a pointer to an expression tree Post: the infix expression has been printed*/            if            (tree not empty)            if            (tree token is operand)            print            (tree token)            else            print            (open parenthesis)            infix            (tree left subtree)            print            (tree token)            infix            (tree right subtree)            print            (close parenthesis)            end            if            end            ifend infix

Postfix Traversal

The postfix expression is formed by the basic postorder traversal of any binary tree. It does not require parentheses.

Pseudocode:

Algorithm postfix            (tree)            /*Print the postfix expression for an expression tree. Pre : tree is a pointer to an expression tree Post: the postfix expression has been printed*/            if            (tree not empty)            postfix            (tree left subtree)            postfix            (tree right subtree)            print            (tree token)            end            ifend postfix

Prefix Traversal

The prefix expression formed by prefix traversal uses the standard pre-order tree traversal. No parentheses are necessary.

Pseudocode:

Algorithm prefix            (tree)            /*Print the prefix expression for an expression tree. Pre : tree is a pointer to an expression tree Post: the prefix expression has been printed*/            if            (tree not empty)            print            (tree token)            prefix            (tree left subtree)            prefix            (tree right subtree)            and check            if            stack is not empty end            ifend prefix

Construction of an Expression Tree

The evaluation of the tree takes place by reading the expression one symbol at a time. If the symbol is an operand, one-node tree is created and a pointer is pushed onto a stack. If the symbol is an operator, the pointers are popped to two trees T1 and T2 from the stack and a new tree whose root is the operator and whose left and right children point to T2 and T1 respectively is formed . A pointer to this new tree is then pushed to the Stack. ^[4]

Example

The input is: a b + c d e + * *

Since the first two symbols are operands, one-node trees are created and pointers are pushed to them onto a stack. For convenience the stack will grow from left to right.

Stack growing from Left to Right

The next symbol is a '+'. It pops the two pointers to the trees, a new tree is formed, and a pointer to it is pushed onto to the stack.

Formation of a New Tree

Next, c, d, and e are read. A one-node tree is created for each and a pointer to the corresponding tree is pushed onto the stack.

Creating One-Node Tree

Continuing, a '+' is read, and it merges the last two trees.

Merging Two Trees

Now, a '*' is read. The last two tree pointers are popped and a new tree is formed with a '*' as the root.

Forming a New Tree with a Root

Finally, the last symbol is read. The two trees are merged and a pointer to the final tree remains on the stack. ^[5]

Steps to Construct an Expression tree a b + c d e + * *

Algebraic expressions

Binary algebraic expression tree equivalent to ((5 + z) / -8) * (4 ^ 2)

Algebraic expression trees represent expressions that contain numbers, variables, and unary and binary operators. Some of the common operators are × (multiplication), ÷ (division), + (addition), − (subtraction), ^ (exponentiation), and - (negation). The operators are contained in the internal nodes of the tree, with the numbers and variables in the leaf nodes. ^[1] The nodes of binary operators have two child nodes, and the unary operators have one child node.

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).

See also

Expression (mathematics)

References

1. ^ ^{a b c} Bruno R. Preiss (1998). "Expression Trees". http://www.brpreiss.com/books/opus5/html/page264.html#SECTION0010500000000000000000 . Retrieved December 20, 2010.
2. ^ ^{a b} Gopal, Arpita. Magnifying Data Structures. PHI Learning, 2010, p. 352.
3. ^ Richard F. Gilberg & Behrouz A. Forouzan. Data Structures: A Pseudocode Approach with C. Thomson Course Technology, 2005, p. 280.
4. ^ Mark Allen Weiss,Data Structures and Algorithm Analysis in C,2nd edition, Addison Wesley publications
5. ^ Gopal, Arpita. Magnifying Data Structures. PHI Learning, 2010, p. 353.

smithstrooks.blogspot.com

Source: https://p2k.unkris.ac.id/IT/3065-2962/Binary-expression-tree_7436_p2k-unkris.html

Share this post