Page 214 - DCAP407_DATA_STRUCTURE

Unit 11: Introduction to Binary Trees

Figure 11.10 shows an expression of binary tree.

Figure 11.10: An Expression Binary Tree

The figure 11.11 depicts the allocation of memory for the binary tree shown in figure 11.10.
In the figure 11.11, + node is stored at index i=2. The parent node of node + is node -, and is stored at
the index i/2 i.e.,2/2=1. The left child node of node +is node T1 and is stored at the index 2i i.e., 2*2= 4
and right child node T2 is stored at the index 2i+1 i.e., 2*2+1=5. This form of representation indicates the
array form of memory allocation of nodes of a binary tree.

Figure 11.11: Sequential Representation of Binary
Tree

1 2 3 4 5 6 7 8 9

- + * T1 T2 T3 + T4 T5

Let us now discuss the algorithm for implementing the sequential representation of binary trees.

Algorithm Binary_Tree (node2, info)
Input – info refers to the data of node2
Output – A binary tree containing two sub-trees of node2
Data Structure – Array representation of tree
Steps
1. If (node2 ≠ 0) then // If tree is not empty
(a) A[node2] = info // Store data of node2 into
array A
(b) node2 has left sub-tree (Give option = Y/N)?
(c) If (option = Y) then // If node2 has left sub-tree
(i) Binary_Tree (2*node2, NEWL) // Then it is 2*node2 with next
item as NEWL
(d) 4. Else

LOVELY PROFESSIONAL UNIVERSITY 207