《数据结构与算法分析》（C++第二版）【美】Clifford A.Shaffer著 课后习题答案 二

5

Binary Trees

5.1 Consider a non-full binary tree. By definition, this tree must have some internal node X with only one non-empty child. If we modify the tree to remove X, replacing it with its child, the modified tree will have a higher fraction of non-empty nodes since one non-empty node and one empty node have been removed.

5.2 Use as the base case the tree of one leaf node. The number of degree-2 nodes is 0, and the number of leaves is 1. Thus, the theorem holds.

For the induction hypothesis, assume the theorem is true for any tree with n ? 1 nodes.

For the induction step, consider a tree T with n nodes. Remove from the tree any leaf node, and call the resulting tree T. By the induction hypothesis, T has one more leaf node than it has nodes of degree 2.

Now, restore the leaf node that was removed to form T. There are two possible cases.

(1) If this leaf node is the only child of its parent in T, then the number of nodes of degree 2 has not changed, nor has the number of leaf nodes. Thus, the theorem holds.

(2) If this leaf node is the child of a node in T with degree 2, then that node has degree 1 in T. Thus, by restoring the leaf node we are adding one new leaf node and one new node of degree 2. Thus, the theorem holds. By mathematical induction, the theorem is correct. 32 33

5.3 Base Case: For the tree of one leaf node, I = 0, E = 0, n = 0, so the theorem holds.

Induction Hypothesis: The theorem holds for the full binary tree containing n internal nodes.

Induction Step: Take an arbitrary tree (call it T) of n internal nodes. Select some internal node x from T that has two leaves, and remove those two

leaves. Call the resulting tree T’. Tree T’ is full and has n?1 internal nodes, so by the Induction Hypothesis E = I + 2(n ? 1).

Call the depth of node x as d. Restore the two children of x, each at level d+1. We have nowadded d to I since x is now once again an internal node. We have now added 2(d + 1) ? d = d + 2 to E since we added the two leaf

nodes, but lost the contribution of x to E. Thus, if before the addition we had E = I + 2(n ? 1) (by the induction hypothesis), then after the addition we have E + d = I + d + 2 + 2(n ? 1) or E = I + 2n which is correct. Thus, by the principle of mathematical induction, the theorem is correct. 5.4 (a) template

void inorder(BinNode* subroot) {

if (subroot == NULL) return; // Empty, do nothing preorder(subroot->left());

visit(subroot); // Perform desired action preorder(subroot->right()); }

(b) template

void postorder(BinNode* subroot) {

if (subroot == NULL) return; // Empty, do nothing preorder(subroot->left()); preorder(subroot->right());

visit(subroot); // Perform desired action }

5.5 The key is to search both subtrees, as necessary. template bool search(BinNode* subroot, Key K); if (subroot == NULL) return false; if (subroot->value() == K) return true; if (search(subroot->right())) return true; return search(subroot->left()); }

34 Chap. 5 Binary Trees

5.6 The key is to use a queue to store subtrees to be processed. template

void level(BinNode* subroot) { AQueue*> Q; Q.enqueue(subroot); while(!Q.isEmpty()) { BinNode* temp; Q.dequeue(temp); if(temp != NULL) { Print(temp);

Q.enqueue(temp->left()); Q.enqueue(temp->right()); }}}

5.7 template

int height(BinNode* subroot) {

if (subroot == NULL) return 0; // Empty subtree return 1 + max(height(subroot->left()),

height(subroot->right())); }

5.8 template

int count(BinNode* subroot) {

if (subroot == NULL) return 0; // Empty subtree if (subroot->isLeaf()) return 1; // A leaf return 1 + count(subroot->left()) + count(subroot->right()); }

5.9 (a) Since every node stores 4 bytes of data and 12 bytes of pointers, the overhead fraction is 12/16 = 75%.

(b) Since every node stores 16 bytes of data and 8 bytes of pointers, the overhead fraction is 8/24 ≈ 33%.

(c) Leaf nodes store 8 bytes of data and 4 bytes of pointers; internal nodes store 8 bytes of data and 12 bytes of pointers. Since the nodes have different sizes, the total space needed for internal nodes is not the same as for leaf nodes. Students must be careful to do the calculation correctly, taking the weighting into account. The correct formula looks as follows, given that there are x internal nodes and x leaf nodes. 4x + 12x 12x + 20x

= 16/32 = 50%.

(d) Leaf nodes store 4 bytes of data; internal nodes store 4 bytes of pointers. The formula looks as follows, given that there are x internal nodes and 35

x leaf nodes: 4x

4x + 4x

= 4/8 = 50%.

5.10 If equal valued nodes were allowed to appear in either subtree, then during a search for all nodes of a given value, whenever we encounter a node of that value the search would be required to search in both directions.

5.11 This tree is identical to the tree of Figure 5.20(a), except that a node with value 5 will be added as the right child of the node with value 2.

5.12 This tree is identical to the tree of Figure 5.20(b), except that the value 24 replaces the value 7, and the leaf node that originally contained 24 is removed from the tree.

5.13 template int smallcount(BinNode* root, Key K); if (root == NULL) return 0;

if (KEComp.gt(root->value(), K))

return smallcount(root->leftchild(), K); else

return smallcount(root->leftchild(), K) +

smallcount(root->rightchild(), K) + 1;

5.14 template void printRange(BinNode* root, int low, int high) {

if (root == NULL) return;

if (KEComp.lt(high, root->val()) // all to left printRange(root->left(), low, high);

else if (KEComp.gt(low, root->val())) // all to right printRange(root->right(), low, high); else { // Must process both children printRange(root->left(), low, high); PRINT(root->value());

printRange(root->right(), low, high); } }

5.15 The minimum number of elements is contained in the heap with a single node at depth h ? 1, for a total of 2h?1 nodes.

The maximum number of elements is contained in the heap that has completely filled up level h ? 1, for a total of 2h ? 1 nodes.

5.16 The largest element could be at any leaf node.

5.17 The corresponding array will be in the following order (equivalent to level order for the heap): 12 9 10 5 4 1 8 7 3 2 36 Chap. 5 Binary Trees

5.18 (a) The array will take on the following order: 6 5 3 4 2 1

The value 7 will be at the end of the array. (b) The array will take on the following order: 7 4 6 3 2 1

The value 5 will be at the end of the array. 5.19 // Min-heap class

template class minheap { private:

Elem* Heap; // Pointer to the heap array int size; // Maximum size of the heap int n; // # of elements now in the heap

void siftdown(int); // Put element in correct place public:

minheap(Elem* h, int num, int max) // Constructor { Heap = h; n = num; size = max; buildHeap(); } int heapsize() const // Return current size { return n; }

bool isLeaf(int pos) const // TRUE if pos a leaf { return (pos >= n/2) && (pos < n); }