Section 6.2 Trees and Their Representations
513
Binary Tree representation
Because a tree is also a graph, the representations discussed in Section 6.1 for graphs
in general can also be used for trees. Binary trees, however, have special characteristics that we want to capture in the representation, namely, the identity of the left
and right child. The equivalent of an adjacency matrix is a two-column array (or
an array of records) where the data values for each node are the left and right child
of that node. The equivalent of the adjacency list representation is a collection of
records with three fields containing, respectively, the current node, a pointer to the
record for the left-child node, and a pointer to the record for the right-child node.
example 24
For the binary tree shown in Figure 6.41, the left child-right
child array representation is given in Figure 6.42a. Zeros again
indicate null pointers. The pointer representation is given in
Figure 6.42b.
1
2
3
4
5
6
(a)
(b)
1
2
3
4
5
6
2
4
0
0
0
0
3
5
6
0
0
0
Left child
Right child
Figure 6.42
4
5
6
3
2
1
Figure 6.41
praCTiCe 20 For the binary tree in Figure 6.43
a. Give the left child-right child array representation.
b. Give the pointer representation.
1
2
4
3
5
Figure 6.43
■