INN701 Lecture 3
Queensland University of Technology
CRICOS No. 00213J
CAB301 Algorithms and Complexity
Lecture 7 – Tree and algorithms
Maolin Tang
School of Computer Science
Queensland University of Technology
CRICOS No. 00213J
a university for the worldreal R 2
Aims of this lecture
• This lecture introduces tree data structures and algorithms
– Tree
– Tree implementation
– Breadth-first traversal algorithm
– Depth-first traversal algorithm
CRICOS No. 00213J
a university for the worldreal R
References
• A. Drozdek. Data Structures and Algorithms in C++. Thomson
Course Technology, third edition, 2005. Section 6.4
3
CRICOS No. 00213J
a university for the worldreal R
Tree
Tree is an important non-linear data structure
It is often used to represent a hierarchy
It has many applications
Filesystems—files inside folders inside folders
Comments—comments, replies to comments, replies to
replies
Family trees—parents, grandparents, children, and
grandchildren
4
CRICOS No. 00213J
a university for the worldreal R
Tree
A tree T is a set of one or more nodes such that T is partitioned
into disjointed subsets:
– A single node r, the root
– Sets that are trees, called subtrees of r.
root
node
edge
5
CRICOS No. 00213J
a university for the worldreal R
Tree
• Parent of node n: the node directly above node n in the tree.
– e.g., B is the parent of H.
• Child of node n: a node directly below node n in the tree.
– e.g., H is a child of B.
• Root: the only node in the tree with no parent.
• Leaf: a node with no child.
– e.g., C F G H I and J are leaves.
• Siblings: nodes with a common parent.
– e.g., F, G and H are siblings.
6
CRICOS No. 00213J
a university for the worldreal R
Tree
• Subtree: any node in a tree together with all of its descendants.
• Height: the number of nodes on the longest path from root to a
leaf.
subtree
Height = 3
Depth = 0
Depth = 1
Depth = 2
7
CRICOS No. 00213J
a university for the worldreal R
key firstchild firstsibling
Tree implementation
firstchild: a pointer to the head of its child linked list
firstsibling: a pointer to next sibling
The structure of a node in trees:
8
CRICOS No. 00213J
a university for the worldreal R
Tree implementation
^ nullA ^
G ^F ^
E ^C ^B
H ^ ^ I ^ J ^ ^
root
9
CRICOS No. 00213J
a university for the worldreal R
Breadth-first traversal
• Breadth-first traversal visits the nodes in the tree in the order of
their depth.
• It first visits the node at depth zero (i.e., the root), then all the
nodes at depth one, and so on.
• At each depth, the nodes are visited from left to right.
10
CRICOS No. 00213J
a university for the worldreal R
Breadth-first traversal
1
2 3 4
5 6 7 8 9
Output: A B C E F G H I J
depth = 0
depth = 1
depth = 2
11
CRICOS No. 00213J
a university for the worldreal R
Breadth-first traversal
ALGORITHM BreadthFirstTraveral (root)
q ← Φ // q is a queue; initially it is empty
q.enqueue(root)
while q ≠ Φ do
r ← q.dequeue()
visit r
// add r’s all children to q one by one from left to right
r ← r.firstchild //r.firstchild is the first child of r
while r ≠ null do
q.enqueue(r)
r ← r.firstsibling
12
CRICOS No. 00213J
a university for the worldreal R
Ainitially
after visiting A B C E
C E Fafter visiting B G H
E F Gafter visiting C H
F G Hafter visiting E I J
G H Iafter visiting F J
H I Jafter visiting G
I Jafter visiting H
Jafter visiting I
after visiting J
Queue q
13
CRICOS No. 00213J
a university for the worldreal R
Depth-first traversal
• It visits the root, and then
• It traverses its subtrees in depth-first order from left to right.
14
CRICOS No. 00213J
a university for the worldreal R
Depth-first traversal
1
2 6 7
3 4 5 8 9
Output: A B F G H C E I J
15
CRICOS No. 00213J
a university for the worldreal R
Depth-first traversal
ALGORITHM DepthFirstTraversal (root)
s ← Φ // s is a stack; initially it is empty
s.push(root)
while s ≠ Φ do
r ← s.pop()
repeat
visit r
if r.firstsibling ≠ null s.push(r.firstsibling)
r ← r.firstchild;
until r = null
16
CRICOS No. 00213J
a university for the worldreal R
Ainitially
after visiting A
after visiting B
C Gafter visiting F
C Hafter visiting G
Cafter visiting H
Eafter visiting C
after visiting E
Jafter visiting I
after visiting J
Stack s
A
GF
ECB
H I J
C
17
CAB301 Algorithms and Complexity��Lecture 7 – Tree and algorithms
Aims of this lecture
References
Tree
Tree
Tree
Tree
Tree implementation
Tree implementation
Breadth-first traversal
Breadth-first traversal
Breadth-first traversal
Slide Number 13
Depth-first traversal
Depth-first traversal
Depth-first traversal
Slide Number 17