CS 112 – Data Structures
Sesh Venugopal
Binary Trees
Binary Trees
BST and AVL Tree are special kinds of binary trees, specialized for searching: every node holds a key that can be searched for
Binary trees can be used for other purposes. For example, you can use a binary tree to model a 20-questions game, or an if statement:
C1
T
T C2 F
C3 F S2
if (C1) then
if (C2) then
S1 else
if (!C3) then
S2
endif endif
endif
S1
A non-search binary tree models some scenario with nodes holding context-specific info (e.g. question, condition) and branches showing at most two outcomes
Sesh Venugopal CS 112: Binary Trees 2
Expression Tree
An important use of a binary tree is to model arithmetic expressions:
+
* * (a+b)*c +c
a+b*c
a
bc
Unary operators are not allowed, only binary operators permitted. Which means every node has either no children (leaf nodes) or exactly two children (internal nodes). No node can have exactly one child.
Every internal node is an operator, and every leaf node is an operand
ab
a+b*3-c
– *c
+3
ab
Sesh Venugopal
CS 112: Binary Trees 3
Expression Tree Traversals Inorder traversal of expression tree
(recurse on Left subtree, then Visit root, then Recurse on right subtree – LVR):
+
* +c
ab
a
bc
a+b*c
a+b*c
But this is a different expression than the original from which the tree was built!
*
This ambiguity arises because the expression tree does not store parentheses
You can use a preorder traversal instead. In a preorder traversal, visit the root first, then recursively traverse the left subtree, then recursively traverse the right subtree (VLR):
+
Or, you can use a postorder traversal, in which recursively traverse the left subtree, then recursively traverse the right subtree, and finally visit (LRV):
+
a*+a*bca* The operator precedes the
two operands on which it b b c applies
c
abc*+
The operator follows the two operands on which it applies
Sesh Venugopal CS 112: Binary Trees
4
– *c
+3 ab
Inorder: Preorder:
a+b*3-c Infixformofexpression
Prefix form Postfix form
Tree Traversals
– * + a b 3 c Postorder: a b + 3 * c –
Inorder, preorder, and postorder traversals are doable on ANY binary tree, not just expression trees:
Sesh Venugopal CS 112: Binary Trees 5
Prefix and Postfix Expressions
The advantage of prefix and postfix expressions is that you do not need parentheses, ever:
Infix
Prefix
Postfix
a+b*c
+a*bc
abc*+
(a + b) * c
*+abc
ab+c*
(a + b) * (3 – c)
*+ab–3c
ab+3c-*
The postfix form, in particular, is very easy to evaluate, using a stack: Scan the expression left to right. If an operand/constant is seen, push its value on the stack. If an operator is seen, apply it on the top two operands (in that order), and push the result on to stack. The result is the single value on the stack when the scan is done.
Sesh Venugopal CS 112: Binary Trees 6
Postfix Expression Evaluation: Example (Equivalent Infix expression: 2 – 3 + 5 * 2 * 3 + 4)
Sesh Venugopal CS 112: Binary Trees 7