Page 197 - DCAP407_DATA_STRUCTURE

Data Structure

Did you know? If T is an m-ary tree with n nodes, then n(m-1) +1 of the nm link fields are null.
Array Representation of Trees
A tree can also be represented using arrays. In this case, you need to have three arrays namely, DATA,
LEFTCHILD and SIBLING. The information content of the node is stored in DATA array, the left-most
children of the node are stored in LEFTCHILD array, and the immediate sibling of the node is stored in
SIBLING array. The array representation of the tree shown in figure 10.20 is shown in the table 10.2.
Figure 10.20: A Tree

Table 10.2 shows array representation of the tree.

Table 10.2: Array Representation of the Tree

Data Left Sibling
child
1 A 2 0
2 B 6 3
3 C 8 4
4 D 9 5
5 E 0 0
6 F 0 7
7 G 11 0
8 H 0 0
9 I 14 10
10 J 0 0
11 K 0 12
12 L 0 13
13 M 0 0
14 N 0 0

190 LOVELY PROFESSIONAL UNIVERSITY