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

260 BINARY TREES [CHAP. 10

Fig. 10-34

10.21. Suppose the preorder and inorder traversals of a binary treeTyield the following sequences of nodes:

Preorder: G, B, Q, A, C, K, F, P, D, E, R, H

Inorder: Q, B, K, C, F, A, G, P , E, D, H, R

(a) Draw the diagram ofT.

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

(c) List the terminal nodes ofT.

10.22. Consider the algebraic expressionE=(x+ 3 y)^4 (a− 2 b). (a) Draw the corresonding 2-tree. (b) WriteEin Polish

prefix form.

BINARY SEARCH TREES, HEAPS

10.23. Find the final treeTif the following numbers are inserted into an empty binary search treeT:

50 , 33 , 44 , 22 , 77 , 35 , 60 , 40

10.24. Find the final heapHif the numbers in Problem 10-23 are inserted into an empty maxheapH.

10.25. Find the final heapHif the numbers in Problem 10-23 are inserted into an empty minheapH.

10.26. LetTbe the binary search tree in Fig. 10-35(a). Suppose nodes 20, 55, 88 are added one after the other toT. Find the
final treeT.

10.27. LetTbe the binary search tree in Fig. 10-35(a). Suppose nodes 22, 25, 75 are deleted one after the other fromT. Find
the final treeT.

Fig. 10-35

10.28. LetHbe the heap in Fig. 10-35(b). Find the final heapHif the numbers 65, 44, and 75 are inserted one after the other
intoH.

10.29. LetHbe the heap in Fig. 10-35(b). Find the final heapHif the root and then the next root are deleted fromH.