How to Draw a Binary Tree From an Expression


<< Previous - BST

Next - Expression Tree Examples >>



Expression Tree is used to represent expressions.

An expression and expression tree shown below

              a + (b * c) + d * (e + f)
Expression Tree

All the below are also expressions. Expressions may includes constants value as well as variables

                              a * 6                          
                              16                          
              (a^2)+(b^2)+(2 * a * b)                          
                              (a/b) + (c)                          
                              m * (c ^ 2)            

It is quite common to use parenthesis in order to ensure correct evaluation of expression as shown above

There are different types of expression formats:

  • Prefix expression
  • Infix expression and
  • Postfix expression

Expression Tree is a special kind of binary tree with the following properties:

  • Each leaf is an operand. Examples: a, b, c, 6, 100
  • The root and internal nodes are operators. Examples: +, -, *, /, ^
  • Subtrees are subexpressions with the root being an operator.

Traversal Techniques

There are 3 standard traversal techniques to represent the 3 different expression formats.

Inorder Traversal

We can produce an infix expression by recursively printing out

  • the left expression,
  • the root, and
  • the right expression.

Postorder Traversal

The postfix expression can be evaluated by recursively printing out

  • the left expression,
  • the right expression and
  • then the root

Preorder Traversal

We can also evaluate prefix expression by recursively printing out:

  • the root,
  • the left expressoion and
  • the right expression.

If we apply all these strategies to the sample tree above, the outputs are:

  • Infix expression:
                    (a+(b*c))+(d*(e + f))              
  • Postfix Expression:
                    a b c * + d e f + * +                              
  • Prefix Expression:
                                      + + a * b c * d + e f                              

Construction of Expression Tree

Let us consider a postfix expression is given as an input for constructing an expression tree. Following are the step to construct an expression tree:

  1. Read one symbol at a time from the postfix expression.
  2. Check if the symbol is an operand or operator.
  3. If the symbol is an operand, create a one node tree and push a pointer onto a stack
  4. If the symbol is an operator, pop two pointers from the stack namely T1 & T2 and form a new tree with root as the operator, T1 & T2 as a left and right child
  5. A pointer to this new tree is pushed onto the stack

Thus, An expression is created or constructed by reading the symbols or numbers from the left. If operand, create a node. If operator, create a tree with operator as root and two pointers to left and right subtree


Example - Postfix Expression Construction

The input is:

a b + c *

The first two symbols are operands, we create one-node tree and push a pointer to them onto the stack.


Next, read a'+' symbol, so two pointers to tree are popped,a new tree is formed and push a pointer to it onto the stack.


Next, 'c' is read, we create one node tree and push a pointer to it onto the stack.

Finally, the last symbol is read ' * ', we pop two tree pointers and form a new tree with a, ' * ' as root, and a pointer to the final tree remains on the stack.


Examples - How to Write Infix, Prefix, Postfix Expressions from Expression Tree >>



<< Previous - BST

Next - Expression Tree Examples >>



<< Previous - BST

Next - Expression Tree Examples >>



Expression Tree is used to represent expressions.

An expression and expression tree shown below

              a + (b * c) + d * (e + f)
Expression Tree

All the below are also expressions. Expressions may includes constants value as well as variables

                              a * 6                          
                              16                          
              (a^2)+(b^2)+(2 * a * b)                          
                              (a/b) + (c)                          
                              m * (c ^ 2)            

It is quite common to use parenthesis in order to ensure correct evaluation of expression as shown above

There are different types of expression formats:

  • Prefix expression
  • Infix expression and
  • Postfix expression

Expression Tree is a special kind of binary tree with the following properties:

  • Each leaf is an operand. Examples: a, b, c, 6, 100
  • The root and internal nodes are operators. Examples: +, -, *, /, ^
  • Subtrees are subexpressions with the root being an operator.

Traversal Techniques

There are 3 standard traversal techniques to represent the 3 different expression formats.

Inorder Traversal

We can produce an infix expression by recursively printing out

  • the left expression,
  • the root, and
  • the right expression.

Postorder Traversal

The postfix expression can be evaluated by recursively printing out

  • the left expression,
  • the right expression and
  • then the root

Preorder Traversal

We can also evaluate prefix expression by recursively printing out:

  • the root,
  • the left expressoion and
  • the right expression.

If we apply all these strategies to the sample tree above, the outputs are:

  • Infix expression:
                    (a+(b*c))+(d*(e + f))              
  • Postfix Expression:
                    a b c * + d e f + * +                              
  • Prefix Expression:
                                      + + a * b c * d + e f                              

Construction of Expression Tree

Let us consider a postfix expression is given as an input for constructing an expression tree. Following are the step to construct an expression tree:

  1. Read one symbol at a time from the postfix expression.
  2. Check if the symbol is an operand or operator.
  3. If the symbol is an operand, create a one node tree and push a pointer onto a stack
  4. If the symbol is an operator, pop two pointers from the stack namely T1 & T2 and form a new tree with root as the operator, T1 & T2 as a left and right child
  5. A pointer to this new tree is pushed onto the stack

Thus, An expression is created or constructed by reading the symbols or numbers from the left. If operand, create a node. If operator, create a tree with operator as root and two pointers to left and right subtree


Example - Postfix Expression Construction

The input is:

a b + c *

The first two symbols are operands, we create one-node tree and push a pointer to them onto the stack.


Next, read a'+' symbol, so two pointers to tree are popped,a new tree is formed and push a pointer to it onto the stack.


Next, 'c' is read, we create one node tree and push a pointer to it onto the stack.

Finally, the last symbol is read ' * ', we pop two tree pointers and form a new tree with a, ' * ' as root, and a pointer to the final tree remains on the stack.


Examples - How to Write Infix, Prefix, Postfix Expressions from Expression Tree >>



<< Previous - BST

Next - Expression Tree Examples >>


hayeshige1998.blogspot.com

Source: https://www.krivalar.com/data-structures-expression-tree

0 Response to "How to Draw a Binary Tree From an Expression"

Post a Comment

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel