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

CHAP. 10] BINARY TREES 255

Fig. 10-25

(b) Scan the tree from the left as in Fig. 10-4(b) to obtain

∗+∗ 2 xy↑−∗ 5 ab 3

10.7. Draw all possible nonsimilar: (a) binary treesTwith three nodes; (b) 2-treesT′with four external nodes.

(a) There are five such treesT, which are pictured in Fig. 10-26(a).

(b) Each 2-treeT′with four external nodes is determined by a binary treeTwith three nodes, that is, by a treeTin

part (a). Thus there are five such 2-treesT′which are pictured in Fig. 10-26(b).

Fig. 10-26

BINARY SEARCH TREES, HEAPS

10.8. Consider the binary treeTin Fig.10-22(a).

(a) Why isTa binary search tree?

(b) Suppose ITEM=33 is added to the tree. Find the new treeT.

(a) Tis a binary, search tree since each nodeNis greater than the values in its left subtree and less than the values

in its right subtree.