PowerPoint Presentation
Data Structures: A Pseudocode Approach with C, Second Edition
1
Introduction to Trees
Data Structures: A Pseudocode Approach with C, Second Edition
2
Data Structures: A Pseudocode Approach with C, Second Edition
3
Data Structures: A Pseudocode Approach with C, Second Edition
4
Data Structures: A Pseudocode Approach with C, Second Edition
5
6
A (B (C D) E F (G H I ) )
Parenthetical Notation
7
Linear List: each node, except the last, has a unique successor.
8
Linear List: each node, except the last, has a unique successor.
Tree: each node, except the root, has one predecessor
and may have multiple successors.
Data Structures: A Pseudocode Approach with C, Second Edition
9
Data Structures: A Pseudocode Approach with C, Second Edition
10
Data Structures: A Pseudocode Approach with C, Second Edition
11
Binary Trees
Data Structures: A Pseudocode Approach with C, Second Edition
12
Data Structures: A Pseudocode Approach with C, Second Edition
13
14
Binary Tree Traversals
breadth-first
depth-first
Data Structures: A Pseudocode Approach with C, Second Edition
15
Breadth-first Traversal
Depth-first
Data Structures: A Pseudocode Approach with C, Second Edition
16
Breadth-first Traversal
Depth-first
A B E C D F
A B C D E
Data Structures: A Pseudocode Approach with C, Second Edition
17
Data Structures: A Pseudocode Approach with C, Second Edition
18
Data Structures: A Pseudocode Approach with C, Second Edition
19
Data Structures: A Pseudocode Approach with C, Second Edition
20
Data Structures: A Pseudocode Approach with C, Second Edition
21
Data Structures: A Pseudocode Approach with C, Second Edition
22
Data Structures: A Pseudocode Approach with C, Second Edition
23
Data Structures: A Pseudocode Approach with C, Second Edition
24
Data Structures: A Pseudocode Approach with C, Second Edition
25
Data Structures: A Pseudocode Approach with C, Second Edition
26
Data Structures: A Pseudocode Approach with C, Second Edition
27
Data Structures: A Pseudocode Approach with C, Second Edition
28
Expression Trees
Data Structures: A Pseudocode Approach with C, Second Edition
29
Data Structures: A Pseudocode Approach with C, Second Edition
30
Data Structures: A Pseudocode Approach with C, Second Edition
31
Data Structures: A Pseudocode Approach with C, Second Edition
32
Data Structures: A Pseudocode Approach with C, Second Edition
33
6-2 Binary Trees
A binary tree can have no more than two descendents. In this section we discuss the properties of binary trees, four different binary tree traversals, and two applications, expression trees and Huffman Code.
Properties
Binary Tree Traversals
Expression Trees
Huffman Code
34
David Huffman is best known for his legendary Huffman code, an optimal compression scheme for loss-less variable length encoding.
From the September 1991 issue of Scientific American, pp. 54, 58.
PROFILE: DAVID A. HUFFMAN
Encoding the “Neatness” of Ones and Zeroes
Huffman Coding
35
optimal compression scheme
o
3
Count
36
optimal compression scheme
o p
3 2
Count
37
optimal compression scheme
o p t
3 2 1
Count
38
optimal compression scheme
o p t i
3 2 1 2
Count
39
optimal compression scheme
o p t i m
3 2 1 2 3
Count
40
optimal compression scheme
o p t i m a l c r e s n h
3 2 1 2 3 1 1 2 1 2 3 1 1
Count
41
optimal compression scheme
t a l r n h p i c e s o m
1 1 1 1 1 1 2 2 2 2 3 3 3
Sort
42
optimal compression scheme
1 1 1 1 1 1 2 2 2 2 3 3 3
t a l r n h p i c e s o m
43
optimal compression scheme
2 2 2 4 4
1 1 1 1 1 1 2 2 2 2 3 3 3
t a l r n h p i c e s o m
Merge:
smallest and
2nd smallest
44
optimal compression scheme
4
2 2 2 4 4
1 1 1 1 1 1 2 2 2 2 3 3 3
t a l r n h p i c e s o m
Merge:
smallest and
2nd smallest
45
optimal compression scheme
4
2 2 2 4 4
1 1 1 1 1 1 2 2 2 2 3 3 3
t a l r n h p i c e s o m
Min(4, 2, 4, 4, 3, 3, 3) is 2
2nd Min(4, 2, 4, 4, 3, 3, 3) is 3
Merge:
smallest and
2nd smallest
46
optimal compression scheme
4
2 2 2 4 4
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
Min(4, 2, 4, 4, 3, 3, 3) is 2
2nd Min(4, 2, 4, 4, 3, 3, 3) is 3
Merge:
smallest and
2nd smallest
47
optimal compression scheme
4 5
2 2 2 4 4
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
Min(4, 2, 4, 4, 3, 3, 3) is 2
2nd Min(4, 2, 4, 4, 3, 3, 3) is 3
Merge:
smallest and
2nd smallest
48
optimal compression scheme
4 5
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
Merge:
smallest and
2nd smallest
49
optimal compression scheme
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
Merge:
smallest and
2nd smallest
50
optimal compression scheme
9
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
Merge:
smallest and
2nd smallest
51
optimal compression scheme
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
Merge:
smallest and
2nd smallest
52
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
Done merging:
Huffman tree
53
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Huffman codes:
0 – left branch
1 – right branch
54
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
110
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Encode
55
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
1101000
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Encode
56
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
11010000000
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Encode
57
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
110100000001001
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Encode
58
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
110100000001001111000100101010110111100000111011011011100111001000111010010110111111011
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Encode
59
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
110100000001001111000100101010110111100000111011011011100111001000111010010110111111011
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Done Encoding
60
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
101100010110000
01111100010010001010110110000
1111100110000
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Decode
61
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
101100010110000
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Decode:
start at the root
0 – go left
1 – go right
62
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
101100010110000
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Decode:
start at the root
0 – go left
1 – go right
63
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
101100010110000
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Decode:
start at the root
0 – go left
1 – go right
64
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
101100010110000
e
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Decode:
start at the root
0 – go left
1 – go right
65
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
101100010110000
e a
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Decode:
start at the root
0 – go left
1 – go right
66
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
101100010110000
e a s
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Decode:
start at the root
0 – go left
1 – go right
67
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
101100010110000
e a s t
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Decode:
start at the root
0 – go left
1 – go right
68
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
101100010110000
e a s t
01111100010010001010110110000
1111100110000
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Decode:
start at the root
0 – go left
1 – go right
69
optimal compression scheme
23
9 14
4 5 8
2 2 2 4 4 6
1 1 1 1 1 1 3 2 2 2 2 3 3
t a l r n h s p i c e o m
0000 0001 0010 0011 0100 0101 011 1000 1001 1010 1011 110 111
101100010110000
e a s t
01111100010010001010110110000
s m a l l e s t
1111100110000
m o s t
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Decode:
start at the root
0 – go left
1 – go right
Data Structures: A Pseudocode Approach with C, Second Edition
70
Data Structures: A Pseudocode Approach with C, Second Edition
71
Data Structures: A Pseudocode Approach with C, Second Edition
72
Data Structures: A Pseudocode Approach with C, Second Edition
73
Data Structures: A Pseudocode Approach with C, Second Edition
74
General Trees
Data Structures: A Pseudocode Approach with C, Second Edition
75
Data Structures: A Pseudocode Approach with C, Second Edition
76
Data Structures: A Pseudocode Approach with C, Second Edition
77
/docProps/thumbnail.jpeg