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

CHAP. 10] BINARY TREES 245 Accordingly, in a heap, the value ofNexceeds the value of every one of its descendants. In particular ...

246 BINARY TREES [CHAP. 10 Fig. 10-12 In other words, we set TREE[ 21 ]=70 and END=21. Then we reheap, i.e., we let ITEM rise to ...

CHAP. 10] BINARY TREES 247 Fig. 10-14 which is not a heap. (Note that both subtrees of 22 are still heaps.) Then we reheap, that ...

248 BINARY TREES [CHAP. 10 Thus Fig. 10-15(d) is the required heapHwithout its original rootR=95. Observe that we ringed the pat ...

CHAP. 10] BINARY TREES 249 Huffman’s Algorithm The general problem we want to solve is the following. Suppose a list ofnweights ...

250 BINARY TREES [CHAP. 10 Fig. 10-18 and RIGHT[ 12 ]=4. The last step tells us that ROOT=15, or we use that fact that ROOT= 2 n ...

CHAP. 10] BINARY TREES 251 EXAMPLE 10.13 Consider again the eight data itemsA,B,C,D,E,F,G,Hin Example 10-12. Suppose the weights ...

252 BINARY TREES [CHAP. 10 Remark:A binary treeTis not a special case of a general treeT. They are two different objects. The tw ...

CHAP. 10] BINARY TREES 253 Fig. 10-22 10.2. Consider the binary treeTin Fig. 10-22(b) (a) Find the depthdofT. (b) TraverseTusing ...

254 BINARY TREES [CHAP. 10 (c) END points to the location of the last node ofT; hence END=15. We finally obtain the sequential r ...

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 ...

256 BINARY TREES [CHAP. 10 (b) Compare ITEM=33 with the root, 60. Since 33<60, move to the left child, 30. Since 33>30, mo ...

CHAP. 10] BINARY TREES 257 (b) The inorder traversal ofTfollows: A, D, E, F, G, H, J, M, P, Q, R, W Observe that this is the alp ...

258 BINARY TREES [CHAP. 10 Fig. 10-30 (The circled number indicates the root of the new subtree in the step.) The treeTis drawn ...

CHAP. 10] BINARY TREES 259 GENERAL TREES 10.16. LetTbe the general tree in Fig. 10-32(a). Find the corresponding binary treeT′. ...

260 BINARY TREES [CHAP. 10 Fig. 10-34 10.21. Suppose the preorder and inorder traversals of a binary treeTyield the following se ...

CHAP. 10] BINARY TREES 261 HUFFMAN ALGORITHM, GENERAL TREES 10.30. Consider the 2-treeTin Fig. 10-36(a) which contains the lette ...

262 BINARY TREES [CHAP. 10 10.37. Write a program which reads the social security numberSSSof an employee and prints the employe ...

CHAP. 10] BINARY TREES 263 10.24. Level by level: 77, 50, 60, 40, 33, 35, 44, 22. 10.25. Level by level: 22, 33, 35, 40, 77, 44, ...

CHAPTER 11 Properties of the Integers 11.1Introduction This chapter investigates some basic properties of thenatural numbers(orp ...