Transcript PPT printable - Simpson College

Mark Allen Weiss: Data Structures and Algorithm Analysis in Java
Chapter 4: Trees
General Tree Concepts
Binary Trees
Lydia Sinapova, Simpson College
Trees
Definitions
Representation
Binary trees
Traversals
Expression trees
2
Definitions
tree - a non-empty collection of
vertices & edges
vertex (node) - can have a
name and carry other associated
information
path - list of distinct vertices in
which successive vertices are
connected by edges
3
Definitions
 any
two vertices must have one
and only one path between them
else its not a tree
a
tree with N nodes has N-1 edges
4
Definitions
 root
tree
- starting point (top) of the
 parent
(ancestor) - the vertex
“above” this vertex
 child
(descendent) - the vertices
“below” this vertex
5
Definitions
 leaves
(terminal nodes) - have
no children
 level - the number of edges
between this node and the root
 ordered tree - where children’s
order is significant
6
Definitions
 Depth of a node - the length of the path
from the root to that node
•
root: depth 0
 Height of a node - the length of the longest
path from that node to a leaf
•
any leaf: height 0
 Height of a tree: The length of the longest
path from the root to a leaf
7
Balanced Trees
the difference between the
height of the left sub-tree
and the height of the right
sub-tree is not more than 1.
8
Trees - Example
Level
root
0
E
1
2
A
A
R
Child (of
root)
S
E
T
Leaves or
terminal nodes
3
M
P
L
E
Depth of T: 2
Height of T: 1
9
Tree Representation
Class TreeNode
{
Object
element;
TreeNode firstChild;
TreeNode nextSibling;
}
10
Example
a
b
c
e
d
f
a
g
b
c
e
d
f
g
11
Binary Tree
S
P
O
I
S
N
M Internal
A
node
External
node
D
B
N
12
Height of a Complete Binary
Tree
L0
L1
L2
L3
At each level the number of the nodes is
doubled.
total number of nodes:
1 + 2 + 22 + 23 = 24 - 1 = 15
13
Nodes and Levels in a
Complete Binary Tree
Number of the nodes in a tree with M levels:
1 + 2 + 22 + …. 2M = 2 (M+1) - 1 = 2*2M - 1
Let N be the number of the nodes.
N = 2*2M - 1,
2*2M = N + 1
2M = (N+1)/2
M = log( (N+1)/2 )
N nodes : log( (N+1)/2 ) = O(log(N)) levels
M levels: 2 (M+1) - 1
= O(2M )
nodes
14
Binary Tree Node
Class BinaryNode
{
Object Element;
// the data in the node
BinaryNode left; // Left child
BinaryNode right; // Right child
}
15
Binary Tree – Preorder
Traversal
Root
Left
Right
C
O
T
M
P
E
U
R
L
N
A
First letter - at the root
Last letter – at the rightmost node
D
16
Preorder Algorithm
preorderVisit(tree)
{
if (current != null)
{
process (current);
preorderVisit (left_tree);
preorderVisit (right_tree);
}
}
17
Binary Tree – Inorder
Traversal
Left
Root
Right
U
P
T
O
C
R
M
E
A
D
L
First letter - at the leftmost node
Last letter – at the rightmost node
N
18
Inorder Algorithm
inorderVisit(tree)
{
if (current != null)
{
inorderVisit (left_tree);
process (current);
inorderVisit (right_tree);
}
}
19
Binary Tree – Postorder
Traversal
Left
Right
Root
D
P
N
M
C
A
O
U
L
R
T
First letter - at the leftmost node
Last letter – at the root
E
20
Postorder Algorithm
postorderVisit(tree)
{
if (current != null)
{
postorderVisit (left_tree);
postorderVisit (right_tree);
process (current);
}
}
21
Expression Trees
The stack contains references to tree nodes
(bottom is to the left)
3
+
1 2
1
*
2
3
+
(1+2)*3
Post-fix notation: 1 2 + 3 *
1
2
22
Expression Trees
In-order traversal:
*
(1 + 2) * ( 3)
3
+
1
2
Post-order traversal:
1 2+3*
23