Page 110 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 5: Trees

curr->right = new; Notes
}
}
Program: Binary tree creation

Array-based representation of a Binary Tree

Consider a complete binary tree T having n nodes where each node contains an item (value).
Label the nodes of the complete binary tree T from top to bottom and from left to right 0, 1, ...,
th
n-1. Associate with T the array A where the i entry of A is the item in the node labelled i of T, i =
0, 1, ..., n-1. Figure 5.8 depicts the array representation of a Binary tree of fi gure.
Given the index i of a node, we can easily and efficiently compute the index of its parent and left

and right children:
Index of Parent: (i – 1)/2, Index of Left Child: 2i + 1, Index of Right Child: 2i + 2.
Table 5.1: Array representation of a Binary Tree

Node Item Left child Right child
0 A 1 2
1 B 3 4
2 C –1 –1
3 D 5 6
4 E 7 8
5 G –1 –1
6 H –1 –1
7 I –1 –1
8 J –1 –1
9 ? ? ?

First column represents index of node, second column consist of the item stored in the node and
third and fourth columns indicate the positions of left and right children (–1 indicates that there
is no child to that particular node.)

5.5 Binary Tree Traversal

This section discusses different orders in which a binary tree can be traversed. The algorithms
for some commonly used orders of traversal are also presented. It also discusses the issue of
construction of a unique binary tree given the orders of traversal.

5.5.1 Order of Traversal of Binary Tree

The following are the possible orders in which a binary tree can be traversed:
1. LDR
2. LRD
3. DLR
4. RDL
5. RLD
6. DRL

LOVELY PROFESSIONAL UNIVERSITY 105