Data Structures
16. Binary Tree Implementation
Tree Implementation 1
Tree ADT
• Data Type: Any type of objects can be stored in a tree
• Accessor methods
– r o o t ( ) – return the root of the tree
– pare nt( p ) – return the parent of a node
– c h i l d r e n ( p ) – return the children of a node
• Query methods
– s i z e ( ) – return the number of nodes in the tree
– isEmpty() – return true if the tree is empty
– elements() – return all elements
– isRoot( p ) – return true if node p is the root
• Other methods
– Tree traversal, Node addition/deletion, create/destroy
Tree Implementation 2
Binary Tree Storage
• Contiguous storage
• Linked list based storage
Tree Implementation 3
Contiguous Storage
Tree Implementation 4
Array Storage (1)
• We are able to store a binary tree as an array
• Traverse tree in breadth-first order, placing the entries into array
– Storage of elements (i.e., objects/data) starts from root node
– Nodes at each level of the tree are stored left to right
Tree Implementation 5
Array Storage Example (1)
A
[1] A
[2] B
B C [3] C
[4] D
[5] E
D E F G [6] F
[7] G
[8] H
H I [9] I
Tree Implementation 6
Array Storage Example (2)
• Unused nodes in tree represented by a predefined bit pattern
A [1] A
[2] B
[3] -
B
[4] C
[5] -
C [6] -
[7] -
D [8] D
[9] -
… …
E
[16] E
Tree Implementation 7
Array Storage (3)
• The children of the node with index k are in 2k and 2k + 1
• The parent of node with index k is in k ÷ 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Tree Implementation 8
Array Storage Example (3)
• Node 10 has index 5
– Its children 13 and 23 have indices 10 and 11, respectively
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Tree Implementation 9
Array Storage Example (4)
• Node 10 has index 5
– Its children 13 and 23 have indices 10 and 11, respectively
– Its parent is node 9 with index 5/2 = 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Tree Implementation 10
Array Storage (4)
• Why array index is not started from 0
– In C++, this simplifies the calculations
parent = k >> 1 ;
l e f t _ c h i l d = k << 1 ;
right_child = left_child | 1;
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Tree Implementation 11
Array Storage: Disadvantage
• Why not store any tree as an array using breadth-first traversals?
– There is a significant potential for a lot of wasted memory
• Consider the following tree with 12 nodes
– What is the required size of array?
Tree Implementation 12
Array Storage: Disadvantage
• Why not store any tree as an array using breadth-first traversals?
– There is a significant potential for a lot of wasted memory
• Consider the following tree with 12 nodes
– What is the required size of array? 32
– What will be the array size if a child is added to node K?
Tree Implementation 13
Array Storage: Disadvantage
• Why not store any tree as an array using breadth-first traversals?
– There is a significant potential for a lot of wasted memory
• Consider the following tree with 12 nodes
– What is the required size of array? 32
– What will be the array size if a child is added to node K? double
Tree Implementation 14
Linked List Storage
Tree Implementation 15
As Linked List Structure (1)
• We can implement a binary tree by using a class which:
– Stores an element
– A left child pointer (pointer to first child)
– A right child pointer (pointer to second child)
clas s Node{
Type v alu e;
Node * L e f t C h i l d , * R i g h t C h i l d ;
}root;
• The root pointer points to the root node
– Follow pointers to find every other element in the tree
• Leaf nodes have L e f t C h i l d and RightChild pointers set to NULL
Tree Implementation 16
As Linked List Structure: Example
Root pointer
a
b c
d e f
g h i j k
l
Tree Implementation 17
Tree Traversal
Tree Implementation 18
Tree Traversal
• To traverse (or walk) the tree is to visit each node in the tree
exactly once
– Traversal must start at the root node
There is a pointer to the root node of the binary tree
• Two types of traversals
– Breadth-First Traversal
– Depth-First Traversal
Tree Implementation 19
Breadth-First Traversal (For Arbitrary Trees)
• All nodes at a given depth d are traversed before nodes at d+1
• Can be implemented using a queue
• Order: A B H C D G I E F J K
Tree Implementation 20
Breadth-First Traversal – Implementation
• Create a queue and push the root node onto the queue
• While the queue is not empty:
– Enqueue all children of the front node onto the queue
– Dequeue the front node
Tree Implementation 21
Depth-First Traversal (For Arbitrary Trees)
• Traverse as much as possible along the branch of each child before
going to the next sibling
– Nodes along one branch of the tree are traversed before backtracking
• Each node could be visited multiple times in such a scheme
– The first time the node is approached (before any children)
– The last time it is approached (after all children)
Tree Implementation 22
Depth-First Tree Traversal (Binary Trees)
• For each node in a binary tree, there are three choices
– Visit the node first
– Visit the one of the subtrees first
– Visit the both the subtrees first
• These choices lead to three commonly used traversals
– Inorder traversal: (Left subtree) visit Root (Right subtree)
– Preorder traversal: visit Root (Left subtree) (Right subtree)
– Postorder traversal: (Left subtree) (Right subtree) visit Root
Tree Implementation 23
Inorder Traversal
• Algorithm
1. Traverse the left subtree in inorder
2. Visit the root
3. Traverse the right subtree in inorder
A, B, C, D, E, F, G, H, I, J
Tree Implementation 24
Inorder Traversal
• Algorithm
1. Traverse the left subtree in inorder +
2. Visit the root
3. Traverse the right subtree in inorder * +
A B * E
• Example
– Left + Right
C D
– [Left * Right] + [Left + Right]
– (A * B) + [(Left * Right) + E)
– (A * B) + [(C * D) + E]
Tree Implementation 25
Inorder Traversal – Implementation
void inorder(Node * p ) const
{
i f (p ! = NULL)
{
inorder(p->leftChild);
cout << p - > i n f o << " " ;
i nor der ( p- >r i ght Chi l d) ;
}
}
void main ( ) {
. . .
ino rde r ( r o o t ) ;
}
Tree Implementation 26
Preorder Traversal
• Algorithm
1. Visit the node +
2. Traverse the left subtree
3. Traverse the right subtree * +
A B * E
• Example
– + Left Right
C D
– + [ * Left Right] [+ Left Right]
– + ( * AB) [+ * Left Right E]
– +*AB + *C D E
Tree Implementation 27
Preorder Traversal – Implementation
void preorder(Node * p ) const
{
i f (p ! = NULL)
{
cout << p - > in f o << " " ;
preorder(p->leftChild);
preorder(p->rightChild);
}
}
void main ( ) {
. . .
preorder ( r o o t ) ;
}
Tree Implementation 28
Postorder Traversal
• Algorithm
1. Traverse the left subtree +
2. Traverse the right subtree
3. Visit the node * +
A B * E
• Example
– Left Right +
C D
– [Left Right *] [Left Right+] +
– (AB*) [Left Right * E + ]+
– (AB*) [C D * E + ]+
– AB* C D * E + +
Tree Implementation 29
Postorder Traversal – Implementation
void postorder(Node * p ) const
{
i f (p ! = NULL)
{
postorder(p->leftChild);
postorder(p->rightChild);
cout << p - > i n f o << " " ;
}
}
void main ( ) {
. . .
postorder ( r o o t ) ;
}
Tree Implementation 30
Example: Printing a Directory Hierarchy
• Consider the directory structure presented on the left
– Which traversal should be used?
/
usr/
bin/
l ocal /
var/
adm/
cr on/
log/
Tree Implementation 31
Expression Tree
Tree Implementation 32
Expression Tree
• Each algebraic expression has an inherent tree-like structure
• An expression tree is a binary tree in which
– The parentheses in the expression do not appear
Tree representation captures the intent of parenthesis
– The leaves are the variables or constants in the expression
– The non-leaf nodes are the operators in the expression
Binary operator has two non-empty subtrees
+
Unary operator has one non-empty subtree
3 -
* +
4 5 9 6
Tree Implementation 33
Convert Postfix into Expression Tree – Algorithm
1 w hile(not the end o f the expression)
2{
3 i f ( t h e next symbol i n the expression i s an operand)
4 {
5 create a node f o r the operand ;
6 push the reference t o the created node onto the stack ;
7 }
8 i f ( t h e next symbol i n the expression i s a binary operato r)
9 {
10 create a node f o r the operator ;
11 pop from the stack a reference t o an operand ;
12 make the operand the r i g h t subtree o f the operator node ;
13 pop from the stack a reference t o an operand ;
14 make the operand the l e f t subtree o f the operator node ;
15 push the reference t o the operator node onto the stack ;
16 }
17 }
Tree Implementation 34
Convert Postfix into Expression Tree – Example (1)
w hile(not the end o f the expression)
{
i f ( t h e next symbol i s an operand)
{
create a node f o r the operand ;
push the reference t o the created node onto the s t a c k ;
Example:
}
ab+cde+**
i f ( t h e next symbol i s a binary o p e ra t or)
{
create an operator node;
pop operant from the s t a c k ;
make the operand the r i g h t subtree ;
pop operand from the s t a c k ;
make the operand the l e f t subtree ;
push the operator node onto the s t a c k ;
}
}
Tree Implementation 35
Convert Postfix into Expression Tree – Example (2)
w hile(not the end o f the expression)
{
i f ( t h e next symbol i s an operand)
{
create a node f o r the operand ;
push the reference t o the created node onto the stack ;
Example:
}
ab+cde+**
i f ( t h e next symbol i s a binary o p er at or)
{
create an operator node;
pop operant from the s t a c k ;
make the operand the r i g h t subtree ;
pop operand from the s t a c k ;
make the operand the l e f t subtree ;
push the operator node onto the s t a c k ;
}
}
Tree Implementation 36
Convert Postfix into Expression Tree – Example (3)
w hile(not the end o f the expression)
{
i f ( t h e next symbol i s an operand)
{
create a node f o r the operand ;
push the reference t o the created node onto the s t a c k ;
Example:
}
ab+cde+**
i f ( t h e next symbol i s a binary o p era t or)
{
create an operator node;
pop operant from the s t a c k ;
make the operand the r i g h t subtree ;
pop operand from the s t a c k ;
make the operand the l e f t subtree ;
push the operator node onto the s t a c k ;
}
}
Tree Implementation 37
Convert Postfix into Expression Tree – Example (4)
w hile(not the end o f the expression)
{
i f ( t h e next symbol i s an operand)
{
create a node f o r the operand ;
push the reference t o the created node onto the stack ;
Example:
}
ab+cde+**
i f ( t h e next symbol i s a binary o p er at or)
{
create an operator node;
pop operant from the s t a c k ;
make the operand the r i g h t subtree ;
pop operand from the s t a c k ;
make the operand the l e f t subtree ;
push the operator node onto the s t a c k ;
}
}
Tree Implementation 38
Convert Postfix into Expression Tree – Example (5)
w hile(not the end o f the expression)
{
i f ( t h e next symbol i s an operand)
{
create a node f o r the operand ;
push the reference t o the created node onto the stack ;
Example:
}
ab+cde+**
i f ( t h e next symbol i s a binary o p er at or)
{
create an operator node;
pop operant from the s t a c k ;
make the operand the r i g h t subtree ;
pop operand from the s t a c k ;
make the operand the l e f t subtree ;
push the operator node onto the s t a c k ;
}
}
Tree Implementation 39
Convert Postfix into Expression Tree – Example (6)
w hile(not the end o f the expression)
{
i f ( t h e next symbol i s an operand)
{
create a node f o r the operand ;
push the reference t o the created node onto the stack ;
Example:
}
ab+cde+**
i f ( t h e next symbol i s a binary o p er at or)
{
create an operator node;
pop operant from the s t a c k ;
make the operand the r i g h t subtree ;
pop operand from the s t a c k ;
make the operand the l e f t subtree ;
push the operator node onto the s t a c k ;
}
}
Tree Implementation 40
Why Expression Tree?
• Expression trees impose a hierarchy on the operations
– Terms deeper in the tree get evaluated first
– Establish correct precedence of operations without using parentheses
• A compiler will read an expression in a language like C++/Java,
and transform it into an expression tree
• Expression trees can be very useful for:
– Evaluation of the expression
– Generating correct compiler code to actually compute the expression's
value at execution time
Tree Implementation 41
Evaluating an Expression Tree
• Perform a post-order traversal of the tree
– Ask each node to evaluate itself
• An operand node evaluates itself by just returning its value
• An operator node has to apply the operator
– To the results of evaluations from its left subtree and right subtree
Order of evaluation: 3 1 2 2 *
(2 + ((5 – 1) * 3))
- 3
5 1
Tree Implementation 42
Evaluating an Expression Tree – Example
• Expression: ab+cde+**
12+345+**
Tree Implementation 43
Evaluating an Expression Tree - Implementation
1 evaluate(ExpressionTree t ) {
2 i f ( t is a leaf)
3 return value o f t ' s operand ;
4 el se{
5 operator = t.element ;
6 operand1 = e v a l u a t e ( t . l e f t ) ;
7 operand2 = e v a l u a t e ( t . r i g h t ) ;
8 return(applyOperator(operand1, ope rat o r, operand2) ;
9 }
10 }
Tree Implementation 44
Any Question So Far?
Tree Implementation 45
