DATA STRUCTURES

AND ALGORITHMS
Trees

1
Content

• Definition
• Terminology
• Traversal
• Data structures
• Operations

2
Tree: definition

10

... 11 1 3

5 4 8 2 7

6 9

3
Tree: definition
 Store objects in a hierarchical
structure
 Recursive definition
r
 Base case: r is a node, T is a
tree containing only one node r
which is also the root of T
 Recursion: r1 r2 ... rk
 Suppose T1, T2, …, Tk are
trees rooted at r1, r2, …, rk
 Given a node r
 Make r1, r2, .., rk children of r
creating a new tree T

4
Applications
• Family tree of mathematicians of the Bernoulli family

Nikolaus
1623-1708

Johan I Nikolaus Jacob I

1667-1748 1662-1716 1654-1705

Nikolaus II Daniel Johan II Nikolaus I

1695-1726 1700-1782 1710-1790 1687-1759

Johan III Jacob II

1746-1807 1759-1789

5
Applications

Table of contents Folders organization

6
Applications: expression tree

/ /

1 3 * 4

6 7

1/3 + 6*7 / 4
7
Terminology
• Path: sequence of nodes x1, x2, …, xq where xi is the parent of xi+1, i = 1,
2, …, q-1. Length of the path is q-1
• Leaves: do not have children
• Internal nodes: have children
• Sibling: 2 nodes u and v are sibling if they have the same parent
• Ancestors: node u is an ancestor of v is there is a path from u to v
• Descendants: node u is a descendant of v if v is an ancestor of u
• Height: the height of a node is the length of the longest path from that
node to some leaf plus 1
• Depth: the depth of a node v is the length of the unique path from that
node to the root plus 1

8
Terminology
• Root: do not have parent (example: node A)
• B, C, D are siblings;
• Internal nodes: A, B, C, F
• Leaves: E, I, J, K, G, H, D

Con của B:
• E, F B C D
Cha của E:
• B
Tổ tiên của F: E F G H
• B, A
Hậu duệ của B: Cây con của nút A
• E, F, I, J, K I J K

9
 Terminology

depth=1 A height=3
Height of tree = 3
depth=2 depth=2 C
B D depth=2
height=1 height=2 depth=1

depth=3 E depth=3 F
height=1 height=1

10
Traversal

• Visit nodes of a tree in some order

• Pre-order traversal
• In-order traversal
• Post-order traversal
• Consider a tree T
• root r
• subtrees T1 (root r1), T2 (root r2), …, Tk (root rk) from left to right

11
Traversal

• Pre-order traversal
• Visit the root preOrder(r){
if(r = NULL) return;
• Traverse T1 in the pre-order
visit(r);
• Traverse T2 in the pre-order
for each p = r1, r2, .., rk {
• … preOrder(p);
• Traverse Tk in the pre-order }
}

12
Traversal

• In-order traversal
• Traverse T1 in the in-order inOrder(r){
if(r = NULL) return;
• Visit the root r
inOrder(r1);
• Traverse T2 in the in-order
visit(r);
• … for each p = r2, .., rk {
• Traverse Tk in the in-order inOrder(p);
}
}

13
Traversal

• Post-order traversal
• Traverse T1 in the post-order postOrder(r){
if(r = NULL) return;
• Traverse T2 in the post-order
for each p = r1, r2, .., rk {
• …
postOrder(p);
• Traverse Tk in the post-order }
• Visit the root r visit(r);
}

14
Data structures

• Array:
• Suppose nodes are numbered 1, 2, …, n
• a[1..n] in which a[i] is the parent of i
• Implementation of many operations on the tree might be too
complicated
• Pointer: Each node has two pointers
• leftMostChild: a pointer to the left-most child
• rightSibling: a pointer to the right-sibling node

15
Data structures

struct Node{
int id; // identifier of the node
Node* leftMostChild;// pointer to the left-most child
Node* rightSibling;// pointer to the right-sibling
};
Node* root;// pointer to the root of the tree

16
Operations

• find(r, id): return the node having identifier id on the tree rooted at r
• insert(r, p, id): create a node having identifier id, insert that node to the
end of the children list of p on the tree rooted at r
• height(r, p): return the height of node p on the tree rooted at r
• depth(r, p): return the depth of the node p on the tree rooted at r
• parent(r, p): return the parent of p on the tree rooted at r
• count(r): return the number of nodes of the tree rooted at r
• countLeaves(r): return the number of leaves of the tree rooted at r

17
Operations

• Find a node given the identifier Node* find(Node* r, int v){

if(r == NULL) return NULL;
r if(r->id == v) return r;
Node* p = r->leftMostChild;
while(p != NULL){
Node* h = find(p,v);
r1 r2 ... rk
if(h != NULL) return h;
p = p->rightSibling;
}
return NULL;
}

18
Operations

• Pre-order traversal void preOrder(Node* r){

if(r == NULL) return;
r printf("%d ",r->id);
Node* p = r->leftMostChild;
while(p != NULL){
preOrder(p);
r1 r2 ... rk
p = p->rightSibling;
}
}

19
Operations

• In-order traversal void inOrder(Node* r){

if(r == NULL) return;
r Node* p = r->leftMostChild;
inOrder(p);
printf("%d ",r->id);
if(p != NULL)
r1 r2 ... rk p = p->rightSibling;
while(p != NULL){
inOrder(p);
p = p->rightSibling;
}
}

20
Operations

• Post-order traversal void postOrder(Node* r){

if(r == NULL) return;
r Node* p = r->leftMostChild;
while(p != NULL){
postOrder(p);
p = p->rightSibling;
r1 r2 ... rk }
printf("%d ",r->id);
}

21
Operations

• Count the number of nodes of a int count(Node* r){

tree if(r == NULL) return 0;
r int s = 1;
Node* p = r->leftMostChild;
while(p != NULL){
s += count(p);
r1 r2 ... rk
p = p->rightSibling;
}
return s;
}

22
Operations

• Count the number of leaves of a int countLeaves(Node* r){

tree if(r == NULL) return 0;
r int s = 0;
Node* p = r->leftMostChild;
if(p == NULL) s = 1;
while(p != NULL){
r1 r2 ... rk
s += countLeaves(p);
p = p->rightSibling;
}
return s;
}

23
Operations

• Compute the height of a node int height(Node* p){

if(p == NULL) return 0;
r int maxh = 0;
Node* q = p->leftMostChild;
while(q != NULL){
int h = height(q);
r1 r2 ... rk if(h > maxh) maxh = h;
q = q->rightSibling;
}
return maxh + 1;
}

24
Operations
int depth(Node* r, int v, int d){
// d la do sau cua nut r
• Compute the depth of a node if(r == NULL) return -1;
r if(r->id == v) return d;
Node* p = r->leftMostChild;
while(p != NULL){
if(p->id == v) return d+1;
r1 r2 ... rk int dv = depth(p,v,d+1);
if(dv > 0) return dv;
p = p->rightSibling;
}
return -1;
}
int depth(Node* r, int v){
return depth(r,v,1);
}

25
Operations

• Find the parent of a node Node* parent(Node* p, Node* r){

if(r == NULL) return NULL;
r Node* q = r->leftMostChild;
while(q != NULL){
if(p == q) return r;
Node* pp = parent(p, q);
r1 r2 ... rk if(pp != NULL) return pp;
q = q->rightSibling;
}
return NULL;
}

26
Binary trees

• Each node has at most two children

• Distinct between the left child and the right child
struct BNode{
int id;
BNode* leftChild; // pointer to the left child
BNode* rightChild;// pointer fo the right child
};
• leftChild = NULL: current node does not have the left child
• rightChild = NULL: current node does not have the right child

27
Binary trees

• Classification

10 10 10

1 2 1 2 1 2

5 6 4 7 5 6 5 4 7

Perfect tree Complete tree Balanced tree

28
Operations on a binary tree

void preOrder(BNode* r) { void inOrder(BNode* r) {

if(r == NULL) return; if(r == NULL) return;
printf("%d ",r->id); inOrder(r->leftChild);
preOrder(r->leftChild); printf("%d ",r->id);
preOrder(r->rightChild); inOrder(r->rightChild);
} }

29
 Operations on a binary tree

void postOrder(BNode* r) { int count(BNode* r) {

if(r == NULL) return; if(r == NULL) return 0;
postOrder(r->leftChild);
return 1 + count(r->leftChild) +
postOrder(r->rightChild);
count(r->rightChild);
printf("%d ",r->id);
}
}

30
Expression trees

• Binary tree
• Internal node are math
operations *
• Leaves are operands
(variables, constants)
• Infix expression: sequence of - +
elements visited by the in-order
traversal:
(5 - x/y) * (a + 7) 5 / a 7

• Postfix expression: sequence of

elements visited by the post-order
traversal: x y
5 x y / - a 7 + *

31
Evaluation of a postfix expression

• Initialize a stack S
• Scan elements of the postfix from left to right
• If meet an operand, then push it into the stack S
• If meet an operator op, then pop 2 operands A and B out of S, perform C
= B op A, and then push C into S
• Termination: the element stays in the stack S is the value of the given
postfix expression

32