DATA STRUCTURES

AND ALGORITHMS

OBJECTIVES
After the lesson, students can
1. Understand the concept of tree data structures and related concepts.

Chapter 6- Tree 2. Implement the tree data structure.

Lesson 1. Definitions and general concepts,

binary trees

3
CONTENTS 1. DEFINITIONS AND GENERAL CONCEPTS

• 1.1. Tree definition

1. Definitions and general concepts  A tree consists of nodes, has a special node called the root, and edges connect
the nodes
2. Binary tree Tree definition:
• Basic step: A node r is a tree and r is called the root r
of this tree
• Recursive step : Suppose T1,T2,...,Tk are trees with r2
r1 rk
roots r1,r2,...,rk :
• Build a new tree by making r the parent of Tk
T1 T2
nodes r1,r2,..., rk
• In this tree r is the root and T1, T2, . . . , Tk are
subtrees of root r. Nodes r1, r2, . . . , rk is called a …
child of node r Tree
Note: Null tree is the tree without node
5 6

1. DEFINITIONS AND GENERAL CONCEPTS 1. DEFINITIONS AND GENERAL CONCEPTS

• 1.1. Tree definition • 1.1. Tree definition

 Realistic tree examples in applications  Realistic tree examples in applications
Nikolaus
France France 1623-
Spain France 1708

Brazil Brazil Johan I Nikolaus Jacob I

1667-1748 1662-1716 1654-1705
UK Italy
Germany Germany
Ucraina Nikolaus II Daniel Johan II Nikolaus I
Italy 1695-1726 1700-1782 1710-1790 1687-1759
Italy Italy
Aghentina
Johan III Jacob II
1746-1807 1759-1789
Describe the schedule of sports tournaments in a knockout format, such as the
second round of the World Cup Family tree of the Bernoulli family of mathematicians

7 8
1. DEFINITIONS AND GENERAL CONCEPTS 1. DEFINITIONS AND GENERAL CONCEPTS

• 1.1. Tree definition • 1.1. Tree definition

 Realistic tree examples in applications  Realistic tree examples in applications

Manager

Administration Organization Finance Business Plan department

… …

Cây phân cấp quản lý hành chính

Directory tree

9 10

1. DEFINITIONS AND GENERAL CONCEPTS 1. DEFINITIONS AND GENERAL CONCEPTS

• 1.2. Terminology • 1.2. Terminology

Nodes parent node
(nút) (nút cha)

11 12
1. DEFINITIONS AND GENERAL CONCEPTS 1. DEFINITIONS AND GENERAL CONCEPTS

• 1.2. Terminology • 1.2. Terminology

Parent Child (con) Parent Child
(cha)

13 14

1. DEFINITIONS AND GENERAL CONCEPTS 1. DEFINITIONS AND GENERAL CONCEPTS

• 1.2. Terminology • 1.2. Terminology

Root (gốc) Leaf (lá) Subtree (cây con)

15 16
1. DEFINITIONS AND GENERAL CONCEPTS 1. DEFINITIONS AND GENERAL CONCEPTS

• 1.2. Terminology • 1.2. Terminology

Subtree Subtree

17 18

1. DEFINITIONS AND GENERAL CONCEPTS 1. DEFINITIONS AND GENERAL CONCEPTS

• 1.2. Terminology • 1.2. Terminology

root, ancestor
From parent to child There is only 1 path from one node
and to a a
to a node that is its descendants parent internal node
descendant nodes
b d (not the leaf)
b d
c c
Path 1 Path 2 sibling nút
e f leaf (don’t have child)
f g
e h h
g i
child child
Path 1: { a, b, f, j } i j
j descendent e, i, k, g, h
Path 2: { d, i }
k là lá (leaves)
Path on the tree Terminologies with rooted trees

19 20
1. DEFINITIONS AND GENERAL CONCEPTS CONTENTS

• 1.2. Terminology
1. Definitions and general concepts
Labeled Tree (Cây có nhãn)
 Each node of the tree has a label or value
n1
* 2. Binary tree
 The node's label is not the name of the node but the
value stored in it
n2 n3 -
 For example: Consider a tree with 7 nodes n1, ..., n7. +
Label the buttons:
 Node n1 is labeled *;
n4
 Node n2 is labeled +; a n5 b n6 a n7 c
 Node n3 has label -;
 Node n4 has label a; Expression tree (a+b)*(a-c)
 Node n5 has label b;
 Node n6 has label a;
 Node n7 is labeled c.
21 22

2. BINARY TREE 2. BINARY TREE

• 2.1. Binary tree • 2.2. Full binary tree

 Binary Tree: A tree in which each node has at most 2 child  Full Binary Tree (Cây nhị phân đầy đủ): is binary tree that satisfies

• Left child and right child • Each leaf node has the same depth

• Each node either: Left Right child

• The internal nodes have exactly 2 children
child
 Not have child

 Has only left child

 Has only right child

 Has both left and right child

23 24
2. BINARY TREE 2. BINARY TREE

• 2.3. Complete binary tree • 2.4. Balanced binary tree

 Complete Binary Tree (Cây nhị phân hoàn chỉnh): A binary tree of depth n satisfies:  A binary tree is called balanced if the height of the left subtree and the height of the right
subtree differ by no more than 1 unit.
• Is a complete binary tree if nodes at depth n are not taken into account, and
 Comment:
• All nodes at depth n are as far left as possible.
• If the binary tree is complete then it is complete
 A complete binary tree of depth n has a number of nodes ranging from 2n-1 to 2n - 1
• If the binary tree is complete then it is balanced

Example:
1. Which tree is complete?
2. Which tree is balance?
3. Which tree is full?

Complete binary tree

25 26

OBJECTIVES

After this lesson, students can

1. Understand the concept of traversing a tree: inorder, preorder, postorder

Chapter 6- Tree 2. Implement the tree representation data structure

Lesson 2. Tree representation data

structure, tree traversal

27
CONTENTS 1. THE DATA STRUCTURE REPRESENTS THE TREE

• 1.1. Represent the tree by array

1. The data structure represents a tree  Suppose T is a tree with nodes named 1, 2, . . . , n.
1.1. Represent trees using arrays  Represent T :
• linear list A where each element A[i] contains a pointer to node i's parent
1.2. Represent a tree as a list of children
• The root of T can be distinguished by a null pointer.
1.3. Represent the tree with the left child and the right neighbor • Assign A[i] = j if node j is parent of node i,
2. Traverse tree A[i] = 0 if node i is root.
• the parent operation returns the parent of a node
 This representation is based on the fact that each node of the tree (except
the root) has only one parent.

29 30

1. THE DATA STRUCTURE REPRESENTS THE TREE 1. THE DATA STRUCTURE REPRESENTS THE TREE

• 1.1. Represent the tree by array • 1.1. Represent the tree by array
 With this representation: the parent of a node can be determined in constant time.  Example 1

 Path from a node to an ancestor (including the root):

2 3
n ← parent(n) ← parent(parent(n)) ← ...
 You can also use the array L[i] to support recording labels for nodes, 4 5 6 10

 or use each element A[i] as a record with 2 fields:

7 8 9
• integer variable records parent
A 0 1 1 2 2 3 6 6 6 3
• label. • Limitation: The use of parent pointers is not suitable for operations with children.
• Given node n, it takes a long time to determine n's children and n's height.
• Do not give us the information about the order of the child nodes → leftmost_child and
right_sibling be undefined → this representation is only used in certain cases.

31 32
1. THE DATA STRUCTURE REPRESENTS THE TREE 1. THE DATA STRUCTURE REPRESENTS THE TREE

• 1.2. Represent the tree by list of children • 1.2. Represent the tree by list of children
 Each node of the tree stores a list of its children. 1 1 2 3

 List of children can be represented by one of the list representations presented in 2 4 5

2 3 3 6 10
the previous chapter. 4 
5 
 The number of children of nodes varies widely → linked lists are often the most
4 5 6 10 6 7 8 9
appropriate choice. 7 
8 
7 8 9
9 
10 
header

 There is an array of pointers to the beginning of the child list of nodes 1, 2, . . . , 10:
header[i] points to the child list of node i.
33 34

1. THE DATA STRUCTURE REPRESENTS THE TREE 1. THE DATA STRUCTURE REPRESENTS THE TREE

• 1.2. Represent the tree by list of children • 1.2. Represent the tree by list of children
 Example: The following description can be used to represent trees  Below is an illustration of the leftmost_child operation settings. The

typedef ? NodeT; /* sign ? needs to be replaced by a suitable type definition */ implementation of the remaining operations is considered an exercise.
typedef ? ListT; /* sign ? needs to be replaced by a suitable list type definition */
typedef ? position; NodeT leftmost_child (NodeT n, TreeT T)
typedef struct /* return the leftmost child of node n in tree T */
{ {
ListT header[maxNodes]; ListT L; /* list of child of node n */
labeltype labels[maxNodes];
L = T.header[n];
NodeT root;
if (empty(L)) /* n is leaf */
} TreeT;
return(0);
 Assume that the root of the tree is stored in the root field and 0 to represent an empty else return(retrive ( first(L), L));
node. }

35 36
1. THE DATA STRUCTURES REPRESENTS THE TREE 1. THE DATA STRUCTURE REPRESENTS THE TREE

• 1.3. Represent the tree with the leftmost child and the right sibling • 1.3. Represent the tree with the leftmost child and the right sibling

Comment: Use the following description: A A

 Each node of the tree is either

struct Tnode
• Childless { B C D
B C D
• has exactly 1 leftmost child node char word[20]; // Data stored in node
• don't have right sibling struct Tnode *leftmost_child;
E F G
• has exactly one right sibling
struct Tnode *right_sibling; E F
G
};
→ To represent a tree: store information
typedef struct Tnode treeNode;
about the leftmost child and right sibling of
treeNode Root; H I J K
each node.
H I J K

General tree Tree representation

37 38

1. THE DATA STRUCTURE REPRESENTS THE TREE CONTENTS

• 1.3. Represent the tree with the leftmost child and the right sibling
1. The data structure represents a tree
Comment:
 With this representation, basic operations are easy to implement. 2. Tree traversal
 Only the parent operation requires traversing the list, so it is inefficient. 2.1. Preorder
• In cases where this operation must be used frequently, add another field to the 2.2. Postorder
record to store the node's parent.
2.3. Inorder

3. Binary tree

39 40
2. TREE TRAVERSAL 2. TREE TRAVERSAL

 Order the nodes • 2.1. Preorder traversal

r
• Preorder, Postorder and Inorder
• These orders are defined recursively as follows: r1 r2 rk

 If tree T is empty, then the empty list is the preorder, postorder, and T1 T2 Tk

middle order list of tree T.

 Preorder traversal of tree T is:
 If tree T has 1 node, then then that node is the pre-ordered, post-ordered,
• Root r of T,
and middle-ordered list of the tree T.
• Next are the nodes of T1 in the preOrder,
 Otherwise, suppose T is a tree with root r with subtrees T1, T2,..., Tk. • Next are the nodes of T2 in the preOrder,
• ...
• And finally, the nodes of Tk in the preOrder.
41 42

2. TREE TRAVERSAL 2. TREE TRAVERSAL

• 2.1. Preorder traversal • 2.2. PostOrder traversal

Algorithm: r

void PREORDER ( nodeT r ) r2

r1 rk
{
T1 T2 Tk
(1) Print out r;
(2) for (each child c of r, if any, in the order from the left) do a
 PostOrder of nodes on tree T :
PREORDER(c);
b c d
• The nodes of T1 in postOrder,
} • Next are the nodes of T2 in postOrder,
e f g
Example: Preorder of nodes on the tree of the figure: • ...
a, b, c, e, h, i, f, j, d, g h i j • Nodes of Tk in postOrder,
• Finally is the root r.
43 44
2. TREE TRAVERSAL 2. TREE TRAVERSAL

• 2.2. PostOrder traversal • 2.3. InOrder traversal

Algorithm: r

void POSTORDER ( nodeT r )

r2 rk
{ r1

for (each child c of r, if any, in the order from the left ) do Tk

T1 T2
POSTORDER(c)
Print out r; a
}  Inorder of nodes on the tree T:
 Example: PostOrder of nodes on the tree of the figure: b c d • Nodes of T1 in InOder,
b, h, i, e, j, f, c, g, d, a e f g • Next is the root r,

h i
• The following are nodes of T2, . . . , Tk, each group is in InOrder.
j

45 46

2. TREE TRAVERSAL 2. TREE TRAVERSAL

• 2.3. InOrder traversal  Order the nodes

void INORDER (nodeT r ) a
{ Walk around the tree starting at the root, a

if ( r is leaf ) Print out r; counterclockwise and following the tree

b c d
else closest b c d
e f g
{ e f g

INORDER(leftmost child of r); h i j h i j

Print out r;
for (each child c of r, except the leftmost child, in order from the left) do • PreOrder: print out the node every time it is visited.
INORDER(c);
• PostOrder: print out the node when it was last passed before returning to its parent.
}
} • InOrder: print out the leaf as soon as it is visited, while internal nodes are printed out the
 Example: InOrder of nodes on the tree of the figure: second time it is visited.
b, a, h, e, i, c, j, f, g, d • Note: the leaves are arranged in the same order from left to right in all three orders.
47 48
CONTENTS 3. BINARY TREE

• 3.1. Representation of binary tree

1. The data structure represents a tree  Representation by using array

2. Tree traversal • Similar as in general tree representation.

• In the case of a complete binary tree, many operations can be implemented with the tree
3. Binary tree very efficiently.

3.1. Representation of binary tree  Consider a complete binary tree T with n nodes, where each node contains a value.

3.2. Tree traversal  Assign lables to the nodes of the complete binary tree T from top to bottom and from left
to right using the numbers 1, 2,..., n.

 Let tree T correspond to array A in which the ith element of A is the value stored in the ith
node of tree T, i = 1, 2, ..., n.

49 50

3. BINARY TREE 3. BINARY TREE

• 3.1. Representation of binary tree • 3.1. Representation of binary tree

 Representation by using array  Representation by using array
1
H
H D K B F J L A C E
0 1 2 3 4 5 6 7 8 9 10
D 2 K 3
Find Use Limit
B 4 Left child of A[i] A[2*i] 2*i <= n
F 5 J 6 L 7
Right child of A[i] A[2*i + 1] 2*i + 1 <= n

A C E Parent of A[i] A[i/2] i>1

Representation by using array
8 9 10 Root A[1] A is not empty
H D K B F J L A C E Check A[i] is leaf? True 2*i > n
0 1 2 3 4 5 6 7 8 9 10
51 52
3. BINARY TREE 3. BINARY TREE

• 3.1. Representation of binary tree • 3.1. Representation of binary tree

 Representation by using pointer  Representation by using pointer
A
A
Each node of tree has two pointers that point to left child and right child
B
B

Point to left child key Point to right child E C

E C

F G D F G D
struct Tnode {
DataType Item; // DataType –data type of node on the tree H
H
I
struct Tnode *left; I
struct Tnode *right; J
}; J
K K
typedef struct Tnode treeNode; Binary tree is represented by pointers
Binary tree
53 54

3. BINARY TREE 3. BINARY TREE

• 3.2. Tree traversal • 3.2. Tree traversal

 PreOrder traversal  PreOrder traversal
2
void printPreorder(treeNode *tree)
• Visit the node { 4 5
if( tree != NULL )
• Traverse the left subtree {
printf("%s\n", tree->word); 7 3 10 8
printPreorder(tree->left);
• Traverse the right subtree
printPreorder(tree->right);
} 1 9 6
11
}
2, 4, 7, 1, 9, 3, 6, 5, 10, 8, 11
55 56
3. BINARY TREE 3. BINARY TREE

• 3.2. Tree traversal • 3.2. Tree traversal

 InOrder traversal  InOrder traversal
2
void printInorder(treeNode *tree)
{ 4 5
• Traverse the left subtree if( tree != NULL )
{
• Visit the node printInorder(tree->left); 7 3 10 8
printf("%s\n", tree->word);
• Traverse the right subtree printInorder(tree->right);
} 1 9 6
11
}
1, 7, 9, 4, 6, 3, 2, 10, 5, 11, 8
57 58

3. BINARY TREE 3. BINARY TREE

• 3.2. Tree traversal • 3.2. Tree traversal

 PostOrder traversal  PostOrder traversal
2

void printPostorder(treeNode *tree)

{ 4 5
 Traverse the left subtree
if( tree != NULL )
 Visit the node { 7 3 10 8
printPostorder(tree->left);
printPostorder(tree->right);
 Traverse the right subtree
printf("%s\n", tree->word); 1 9 6
11
}
}
1, 9, 7, 6, 3, 4, 10, 11, 8, 5, 2
59 60
 OBJECTIVES
After the lesson, students can

1. Understand the concept of the height and depth of the internal on

Chapter 6- Tree tree

2. Implement the algorithm to calculate the height and depth of nodes

Lesson 3. Calculate the height, depth of
the node on the tree on the tree

61

CONTENTS 1. DEFINITION OF THE HEIGHT AND DEPTH OF NODE

• 1.1. Definition
1. Definitions of height and depth of the node
 The height of a node in the tree is equal to the length of the longest path
1.1. Definition
from that node to the leaf plus 1.
1.2 Example
 The height of a tree is the height of the root.
2. Algorithm to find the height and depth
 The depth/level of a node is equal to 1 plus the length of the unique path
from the root to it.

63 64
1. DEFINITION OF THE HEIGHT AND DEPTH OF NODE 1. DEFINITION OF THE HEIGHT AND DEPTH OF NODE

• 1.2. Example • 1.2. Example

height h = 5 7 depth 1
Height of the tree = 3

depth=1 A height=3 height h = 4 3 10 4 depth 2

depth=2 height h = 3
B C D depth=2 8 12 11 2 depth 3
height=2
height=1

h=2 6 5 1 depth 4
depth=3 E
depth=3 F
height=1 height=1

9 depth 5
height h=1 Height of the tree: 5

65 66

CONTENTS 2. ALGORITHM TO FIND THE HEIGHT AND DEPTH

 Tree representation
1. Definitions of height and depth of the node
struct Node{
2. Algorithm to find the height and depth
int id;
2.1 Height of the node Node* leftMostChild;
Node* rightSibling;
2.2 Depth of the node
};
Node* root;

67 68
 2. ALGORITHM TO FIND THE HEIGHT AND DEPTH 2. ALGORITHM TO FIND THE HEIGHT AND DEPTH

• 2.1. Find the height of a node • 2.1. Find the height of a node
 Height of a node  Height of a node
7 int height(Node* p){ 7 int height(Node* p){
if(p == NULL) return 0; if(p == NULL) return 0;
int maxh = 0; int maxh = 0;
Node* q = p->leftMostChild; Node* q = p->leftMostChild;
h =? 3 10 4 h =? 3 10 4
while(q != NULL){ while(q != NULL){
int h = height(q); int h = height(q);
if(h > maxh) maxh = h; if(h > maxh) maxh = h;
h=? 8 12 11 2 q = q->rightSibling; h=? 8 12 11 2 q = q->rightSibling;
} }
return maxh + 1; return maxh + 1;
} }
h=? 6 5 1 h=1 6 h=? 5 1

h=0 h=0 9 h=? 9

69 70

2. ALGORITHM TO FIND THE HEIGHT AND DEPTH 2. ALGORITHM TO FIND THE HEIGHT AND DEPTH

• 2.1. Find the height of a node • 2.1. Find the height of a node
 Height of a node  Height of a node
7 int height(Node* p){ 7 int height(Node* p){
if(p == NULL) return 0; if(p == NULL) return 0;
int maxh = 0; int maxh = 0;
Node* q = p->leftMostChild; Node* q = p->leftMostChild;
h =? 3 10 4 h =4
=? 3 10 4
while(q != NULL){ while(q != NULL){
int h = height(q); int h = height(q);
if(h > maxh) maxh = h; if(h > maxh) maxh = h;
h=3
h=? 8 h=? 12 11 2 q = q->rightSibling; h=3 8 h=2 12
h=? 11 2 q = q->rightSibling;
} }
return maxh + 1; return maxh + 1;
} }
h=1 6 h=2
h=? 5 h=? 1 h=1 6 h=2 5
h=? h=1 1

h=1 9 h=1 9
71 72
 2. ALGORITHM TO FIND THE HEIGHT AND DEPTH

• 2.2. Find the depth of a node

 Depth of a node
int depth(Node* r, int v, int d){
// d is the depth of node r
d =1 7 if(r == NULL) return -1;
if(r->id == v) return d;

THANK YOU !
Node* p = r->leftMostChild;
while(p != NULL){
d =2 3 10 4 if(p->id == v) return d+1;
int dv = depth(p,v,d+1);
if(dv > 0) return dv;
d=3 8 d=3 12 11 2 p = p->rightSibling;
}
return -1;
}
d=4 6 d=4 5 1 d =?
=4
int find_depth(Node* r, int v){
return depth(r,v,1);
d=5 9 }
73 74