CHAP. 10] BINARY TREES 253
Fig. 10-2210.2. Consider the binary treeTin Fig. 10-22(b)
(a) Find the depthdofT.
(b) TraverseTusing the preorder algorithm.
(c) TraverseTusing the inorder algorithm.
(d) TraverseTusing the postorder algorithm.
(e) Find the terminal nodes ofT, and the order they are traversed in (b), (c), and (d).
(a) The depthdis the number of nodes in a longest branch ofT; henced=4.
(b) The preorder traversal ofTis a recursive NLR algorithm, that is, it first processes a nodeN, then its left subtreeL,
and finally its right subtreeR. Letting[A 1 ,...,Ak]denote a subtree with nodesA 1 ,...,Ak, the treeTis traversed
as follows:
F−[A, K, C][D, H, G, B, E] or F−A−[K, C]−D−[H][G, B, E]
or, finally,
F−A−K−C−D−H−G−B−E
(c) The inorder traversal ofTis a recursive LNR algorithm, that is, it first processes a left subtreeL, then its nodeN,
and finally its right subtreeR. ThusTis traversed as follows:
[A, K, C]−F−[D, H, G, B, E] or A−[K, C]−F−[H]−D−[G, B, E]
or finally,
A−K−C−F−H−D−B−G−E
(d) The postorder traversal ofTis a recursive LRN algorithm, that is, it first processes a left subtreeL, then its right
subtreeR,and finally its nodeN. ThusTis traversed as follows:
[A, K, C][D, H, G, B, E]−F or [K, C]−A−[H][G, B, E]−D−F
or, finally,
C−K−A−H−B−E−G−D−F
(e) The terminal nodes are the nodes without children. They are traversed in the same order in all three traversal
algorithms:C, H, B, E.10.3. LetTbe the binary tree in Fig. 10-22(b). Find the sequential representation ofTin memory.
The sequential representation ofTuses only a single array TREE and a variable pointer END.(a) The rootRofTis stored in TREE[1]; henceR=TREE[ 1 ]=F.
(b) If nodeNoccupies TREE[K], then its left and right children are stored in TREE[2*K]and TREE[2*K+ 1 ],
respectively. Thus TREE[ 2 ]=Aand TREE[ 3 ]=DsinceAandDare the left and right children ofF.And so on.
Figure 10-23 contains the sequential representation ofT. Note that TREE[ 10 ]=CsinceCis the left child of
K, which is stored in TREE[5]. Also, TREE[ 14 ]=Band TREE[ 15 ]=EsinceBandEare the left and right
children ofG, which is stored in TREE[7].