Trees
04/01/17
04/01/17
04/01/17
04/01/17
Find the parent of c, the children of g, the siblings of h,, all internal
vertices, and all leaves. What is the subtree rooted at g?
The parent of c is b.
The children of g are h, i, and j .
The siblings of h are i and j .
The internal vertices are a, b, c, g, h, and j .
The leaves are d, e, f , i, k, l, and m.
The subtree rooted at g is shown in right Figure.
04/01/17
04/01/17
Are the rooted trees in Figure full m-ary trees for
some positive integer m?
T1 is a full binary tree because each of its internal vertices has
two children.
T2 is a full 3-ary tree because each of its internal vertices has
three children.
In T3 each internal vertex has five children, so T3 is a full 5-ary
tree.
T4 is not a full m-ary tree for any m because some of its internal
vertices have two children and others have three children.
04/01/17
We can change any unrooted tree into a rooted tree by
choosing any vertex as the root.
04/01/17
Find the level of each vertex in the rooted tree shown in Figure. What is
the height of this tree?
The root a is at level O.
Vertices b, j, and k are at level 1 .
Vertices c, e, f, and I are at level
2.
Vertices d, g, i , m , and n are at
level 3 .
Finally, vertex h is at level 4.
Because the largest level of any
vertex is 4, this tree has height 4.
04/01/17
04/01/17
04/01/17
1. How many edges does a tree with 10,000
vertices have?
2. How many vertices does a full 5-ary tree with
100 internal vertices have?
3. How many edges does a full binary tree with
1000 internal vertices have?
4. How many leaves does a full 3-ary tree with 100
vertices have?
04/01/17
Applications of
Trees
Binary Search Trees
Ordered rooted trees are often used to store information.
A binary search tree:
Is a binary tree in which each vertex is labeled with a
key such that:
No two vertices have the same key.
If vertex u belongs to the left subtree of vertex v,
then u<v.
If vertex w belongs to the right subtree of vertex
v, then v<w.
04/01/17
Binary Search Trees
Binary search tree construction algorithm:
Start with a tree containing just one vertex (the root).
Let v= the root.
To add a new item a, do the following until stop:
If a< v:
If v has a left child then v = left child of v(move to the
left)
Else add a new left child to v with this item as its key.
Stop.
04/01/17
Binary Search Trees
If a> v:
If v has a right child then v= right child of
v(move to the right).
Else add a new right child to v with this item
as its key.
Stop.
Example :
5 9 8 1 2 4 6 10
04/01/17
04/01/17
Exercises :
1. Construct a binary search tree for the words
mathematics, physics, geography, zoology,
meteorology, geology, psychology, and chemistry
using alphabetical order.
2. Build a binary search tree for the words banana,
peach, apple, pear, coconut, mango, and papaya
using alphabetical order.
3. Using alphabetical order, construct a binary
search tree for the words in the sentence The
quick brown fox jumps over the lazy dog.
04/01/17
Answer 1:
04/01/17
What are the codes for a, e, i, k, o, p and u if the coding scheme is
represented by this tree?
0 1
0 1 1
0
0 1
i
0 1 1
a e
o
k 0 1
04/01/17 p u
Class work
Given the coding scheme a: 01, b: 001, e : 1, r :
0000, s: 0100, t: 011, x: 01010. Find the word
represented by
1. 01000110010111
2. 01110100011
3. 000110010000
4. 01100101010
04/01/17
Tree Traversal
Tree traversal:
Is a procedure that systematically visits every
vertex of an ordered rooted tree.
Visiting a vertex = processing the data at
the vertex.
Three most commonly used algorithms:
Preorder traversal.
Inorder traversal.
Postorder traversal.
04/01/17
Traversal Algorithm
Procedures for systematically visiting every vertex of an
ordered rooted tree are called Traversal algorithm.
Three most commonly used such algorithms are:
Preorder Traversal
Inorder Traversal
Postorder Traversal
04/01/17
04/01/17
04/01/17
04/01/17
04/01/17
04/01/17
04/01/17
04/01/17
04/01/17
04/01/17
Preorder Traversal, Inorder Traversal
and Postorder Traversal
a
d
b
c
e g
i
f h
j l m
n o p
04/01/17
Answer:
Preorder: a b e j k n o p f c d g l m h i
Inorder: j e n k o p b f a c l g m d h i
Postorder: j n o p k e f b c l m g h I d a
04/01/17
04/01/17
Infix, Prefix, and Postfix notation
Example 1: What is the ordered rooted tree that
represents the expression
((x + y) 2 ) + ((x 4) / 3) ?
Example 2: What is the prefix form for
((x + y) 2 ) + ((x 4) / 3) ?
Example 3: What is the postfix form for
((x + y) 2 ) + ((x 4) / 3) ?
04/01/17
Example 1: What is the ordered rooted tree that represents the
expression
((x + y) 2 ) + ((x 4) / 3) ?
04/01/17
Example 2: What is the prefix form for
((x + y) 2 ) + ((x 4) / 3) ?
Solution: We obtain the prefix form for this expression by
traversing the binary tree that represents it, shown in
previous Figure. This produces + t + x y 2 / - x 4 3 .
Example 3: What is the postfix form for
((x + y) 2 ) + ((x 4) / 3) ?
Solution: We obtain the prefix form for this expression by
traversing the binary tree that represents it, shown in
previous Figure. This produces the postfix expression:x y
+ 2 t x 4 - 3 / +.
04/01/17
What is the value of the prefix expression
+ - *2 3 5 / 2 3 4?
- * 2 / 8 4 3
* + 3 + 3 3 + 3 3 3
What is the value of the postfix expression
7 2 3 * -4 9 3 / +?
9 3 / 5 + 7 2 - *
3 2 * 2 5 3 - 8 4 / * -
04/01/17
04/01/17
Exercises:
Construct the ordered rooted tree whose
preorder traversal is a, b, f, c, g, h, i, d, e, j, k, l,
where a has four children, c has three children,
j has two children, b and e have one child
each, and all other vertices are leaves.
04/01/17