CS计算机代考程序代写 data structure algorithm INN701 Lecture 3

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