Transcript Binary tree

IKI 10100I: Data Structures & Algorithms
Trees
Ruli Manurung
(acknowledgments to Denny & Ade Azurat)
Fasilkom UI
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
1
Outline
Tree Data Structure
 Examples
 Terminology & Definition
Binary Tree
Tree Traversal
Tree Iterators
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
2
Trees: Some Examples
A tree represents a hierarchy, for example:
 Organizational structure of a company
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
3
Trees: Some Examples

Table of contents of a book
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
4
Trees: Some Examples

File system (Unix, Windows, Internet)
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
5
Trees: Terminology
A is the root node
B is the parent of D and E
C is the sibling of B
D and E are the children of B
D, E, F, G, I are external nodes,
or leaves
A, B, C, H are internal nodes
The depth, level, or path length
of E is 2
The height of the tree is 3
The degree of node B is 2
Property: |edges| = |nodes| - 1
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
6
Trees: Viewed Recursively
A sub-tree is also a tree!!
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
7
Binary Trees
Binary tree: tree with all internal nodes of degree 2
Recursive View: a binary tree is either
 empty
 an internal node (the root) and two binary trees (left subtree
and right subtree)
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
8
Binary Trees: An Example
Arithmetic expression
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
9
Binary Trees: Properties
If we restrict that each parent can have two and only two
children, then:
 |external nodes| = |internal nodes| + 1
 |nodes at level i|  2i
 |external nodes|  2 (height)
 height  log2 |external nodes|
 height  log2 |nodes| - 1
 height  |internal nodes| = (|nodes| - 1)/2
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
10
Traversing Trees: Preorder
Preorder Traversal
Algorithm preOrder(v)
“visit” node v
for each child w of v do
recursively perform preOrder(w)
Example: reading a document from beginning to end
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
11
Traversing Trees: Postorder
Postorder Traversal
Algorithm postOrder(v)
for each child w of v do
recursively perform postOrder(w)
“visit” node v
Example: du (disk usage) command in Unix
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
12
Traversing Trees
Algorithm evaluateExpression(v)
if v is an external node
return the variable stored at v
else
let o be the operator stored at v
x  evaluateExpression(leftChild(v))
y  evaluateExpression(rightChild(v))
return x o y
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
13
Traversing Trees: Inorder
Inorder traversal of a binary tree
Algorithm inOrder(v)
recursively perform inOrder(leftChild(v))
“visit” node v
recursively perform inOrder(rightChild(v))
Example: printing an arithmetic expression
 print “(“ before traversing the left subtree
 print “)” after traversing the right subtree
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
14
The BinaryNode in Java
A tree is a collection of nodes:
class BinaryNode <T>
{
T element;
/* Item stored in node */
BinaryNode<T> left;
BinaryNode<T> right;
}
The tree stores a reference to the root node, which is
the starting point.
public class BinaryTree <T>
{
private BinaryNode<T> root; // Root node
public BinaryTree() // Default constructor
{
root = null;
}
}
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
15
Think Recursively
Computing the height of a tree is complex without
recursion.
The height of a tree is one more than the maximum of
the heights of the subtrees.
 HT = max (HL+1, HR+1)
HL+1
Ruli Manurung (Fasilkom UI)
HR+1
HR
HL
IKI10100I: Data Structures & Algorithms
Week 8
16
Routine to Compute Height
Handle base case (empty tree)
Use previous observation for recursive case.
public static int height (BinaryNode t)
{
if (t == null)
return 0;
else
return 1 + max(height (t.left),
height (t.right));
}
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
17
Running Time
This strategy is a postorder traversal: information for
a tree node is computed after the information for its
children is computed.
The running time of tree traversal is N times the cost
of processing each node.
Thus, the running time is linear because we do
constant work for each node in the tree.
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
18
Print Preorder
class BinaryNode
{
void printPreOrder( )
{
System.out.println( element );
if( left != null )
left.printPreOrder( );
if( right != null )
right.printPreOrder( );
}
}
// Node
// Left
// Right
class BinaryTree
{
public void printPreOrder( )
{
if( root != null )
root.printPreOrder( );
}
}
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
19
Print Postorder
class BinaryNode
{
void printPostOrder( )
{
if( left != null )
left.printPostOrder( );
if( right != null )
right.printPostOrder( );
System.out.println( element );
}
}
// Left
// Right
// Node
class BinaryTree
{
public void printPostOrder( )
{
if( root != null )
root.printPostOrder( );
}
}
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
20
Print Inorder
class BinaryNode
{
void printInOrder( )
{
if( left != null )
left.printInOrder( );
// Left
System.out.println( element ); // Node
if( right != null )
right.printInOrder( );
// Right
}
}
class BinaryTree
{
public void printInOrder( )
{
if( root != null )
root.printInOrder( );
}
}
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
21
Traversing Tree
Pre-Order
Ruli Manurung (Fasilkom UI)
Post-Order
IKI10100I: Data Structures & Algorithms
InOrder
Week 8
22
Exercise
A tree contains Integer objects.
 Find the maximum value
 Find the total value
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
23
Tree Iterator Class
Can we implement traversal non-recursively?
 Recursion is implemented by using a stack.
 We can traverse non-recursively by maintaining the stack
ourselves (emulate stack of activation records).
Is a non-recursive approach faster than recursive
approach?
 Possibly:we can place only the essentials, while the
compiler places an entire activation record.
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
24
Postorder Traversal using Stack
Use stack to store the current state (nodes we have
traversed but not yet completed)
 Similar to PC (program counter) in the activation record
We “pop” each node three times, when:
0. about to make a recursive call to left subtree
1. about to make a recursive call to right subtree
2. about to process the current node itself
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
25
Postorder Algorithm
init: push root onto stack with state 0
advance:
 while (true)
• node X = pop from the stack
• switch (state X):
• case 0:
• push node X with state 1
• push left child of X (if it exists) with state 0
• case 1:
• push node X with state 2
• push right child of X (if it exists) with state 0
• case 2:
• visit/process node X
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
26
Postorder Traversal: Stack States
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
27
Exercise
Create a non-recursive algorithm for inorder
traversal using stack.
Create a non-recursive algorithm for preorder
traversal using stack.
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
28
Inorder Traversal using Stack
What are the states for inorder traversal?
0. about to make a recursive call to left subtree
1. about to process the current node
2. about to make a recursive call to right subtree
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
29
Inorder Algorithm
init: push root onto the stack with state 0
advance:
 while (true)
• node X = pop from the stack
• switch (state X):
• case 0:
• push node X with state 1
• push left child of X (if it exists) with state 0
• case 1:
• push node X with state 2
• visit/process node X
• case 2:
• push right child of X (if it exists) with state 0
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
30
Inorder Algorithm (improved)
init: push root onto the stack with state 0
advance (optimize):
 while (true)
• node X = pop from the stack
• switch (state X):
• case 0:
• push node X with state 1
• push left child of X (if it exists) with state 0
• case 1:
• visit/process node X
• push right child of X (if it exists) with state 0
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
31
Preorder Traversal using Stack
What are the states for preorder traversal?
0. about to process the current node
1. about to make a recursive call to left subtree
2. about to make a recursive call to right subtree
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
32
Preorder Algorithm
init: push root onto the stack with state 0
advance:
 while (true)
• node X = pop from the stack
• switch (state X):
• case 0:
• push node X with state 1
• visit/process the node X
• case 1:
• push node X with state 2
• push left child of X (if it exists) with state 0
• case 2:
• push right child of X (if it exists) with state 0
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
33
Preorder Algorithm (improved)
init: push root onto the stack
advance (optimized):
 while (true)
•
•
•
•
node X = pop from the stack
visit/process node X
push right child of X (if it exists) with state 0
push left child of X (if it exists) with state 0
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
34
Euler Tour Traversal
Generic traversal of a binary tree
The preorder, inorder, and postorder traversals are special cases
of the Euler tour traversal
“walk around” the tree and visit each node three times:
 on the left
 from below
 on the right
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
35
Level-Order Traversal
Visit root followed by its children from left to right and
followed by their children. So we go down the tree
level by level.
Sequence: A - B - C - D - E - F - G - H - I
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
36
Level-Order Traversal: Idea
Using a queue instead of a stack
Algorithm (similar to pre-order)
 init: enqueue the root into the queue
 advance:
•
•
•
•
node X = dequeue from the queue
“visit”/”set current to” the node X;
enqueue left child node X (if it exists);
enqueue right child node X (if it exists);
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
37
Binary Tree: Properties
Maximum number of nodes in a binary tree of height k
is 2k+1 -1.
A full binary tree with height k is a binary tree which
has 2k+1 - 1 nodes.
A complete binary tree with height k is a binary tree
which has maximum number of nodes possible in
levels 0 through k -1, and in (k -1)’th level all nodes
with children are selected from left to right.
Complete binary tree with n nodes can be shown by
using an array, then for any node with index i, we have:
 Parent (i) is at i/2 if i 1; for i =1, we have no parent.
 Left-child (i ) is at 2i if 2i  n. (else no left-child)
 Right-child (i ) is at 2i+1 if 2i +1  n (else no right-child)
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
38
Summary
Tree, Binary Tree
In order to process the elements of a tree, we consider accessing
the elements in certain order
Tree traversal is a tree operation that involves "visiting” (or"
processing") all the nodes in a tree.
Depth First Search (DFS):
 Pre-order: Visit node first, pre-order all its subtrees from leftmost to
rightmost.
 Inorder: Inorder the node in left subtree and then visit the root
following by inorder traversal of all its right subtrees.
 Post-order: Post-order the node in left subtree and then post-order
the right subtrees followed by visit to the node.
Breadth First Search (BFS):
 Level-order: Visit root followed by its children from left to right and
followed by their children. So we go down the tree level by level.
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 8
39