Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 10] BINARY TREES 259

GENERAL TREES

10.16. LetTbe the general tree in Fig. 10-32(a). Find the corresponding binary treeT′.

The nodes ofT′will be the same as the nodes of the general treeT. In particular, the root ofT′will be the same

as the root ofT. Furthermore, ifNis a node in the binary treeT′, then its left child is the first child ofNinTand its

right child is the next sibling ofNinT. ConstructingT′from the root down we obtain the tree in Fig. 10-32(b).

Fig. 10-32

SupplementaryProblems

10.17. Consider the binary treeTin Fig. 10-33(a).

(a) Find: (i) depthdofT; (ii) descendants ofB.

(b) TraverseTin: (i) preorder; (ii) inorder; (iii) postorder.

(c) Find the terminal nodes ofTand the orders they are traversed in (b).

10.18. Repeat Problem 10.17 for the binary treeTin Fig. 10-33(b).

10.19. Repeat Problem 10.17 for the binary treeTin Fig. 10-33(c).

Fig. 10-33

10.20. LetTbe the binary tree stored in memory as in Fig. 10-34 where ROOT=14.

(a) Draw the diagram ofT.

(b) TraverseTin: (i) preorder; (ii) inorder; (iii) postorder.

(c) Find the depthdofT.

(d) Find the minimum number of locations required for a linear array TREE ifTwere stored sequentially in TREE.