if (((t1 == NULL) && (t2 != NULL)) || ((t2 == NULL) && (t1 != NULL))) return false;

if ((t1 == NULL) && (t2 == NULL)) return true; 40 41

if (t1->val() != t2->val()) return false;

if (Compare2(t1->leftchild(), t2->leftchild()) if (Compare2(t1->rightchild(), t2->rightchild()) return true;

if (Compare2(t1->leftchild(), t2->rightchild()) if (Compare2(t1->rightchild(), t2->leftchild)) return true; return false; }

6.3 template // Print, postorder traversal void postprint(GTNode* subroot) {

for (GTNode* temp = subroot->leftmost_child(); temp != NULL; temp = temp->right_sibling()) postprint(temp);

if (subroot->isLeaf()) cout << \ else cout << \

cout << subroot->value() << \ }

6.4 template // Count the number of nodes int gencount(GTNode* subroot) { if (subroot == NULL) return 0 int count = 1;

GTNode* temp = rt->leftmost_child(); while (temp != NULL) { count += gencount(temp); temp = temp->right_sibling(); }

return count; }

6.5 The Weighted Union Rule requires that when two parent-pointer trees are merged, the smaller one’s root becomes a child of the larger one’s root. Thus, we need to keep track of the number of nodes in a tree. To do so, modify the node array to store an integer value with each node. Initially, each node is in its own tree, so the weights for each node begin as 1. Whenever we wish to merge two trees, check the weights of the roots to determine which has more nodes. Then, add to the weight of the final root the weight of the new subtree. 6.6

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 -1 0 0 0 0 0 0 6 0 0 0 9 0 0 12 0

6.7 The resulting tree should have the following structure: 42 Chap. 6 General Trees

Node 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Parent 4 4 4 4 -1 4 4 0 0 4 9 9 9 12 9 -1

6.8 For eight nodes labeled 0 through 7, use the following series of equivalences: (0, 1) (2, 3) (4, 5) (6, 7) (4 6) (0, 2) (4 0)

This requires checking fourteen parent pointers (two for each equivalence), but none are actually followed since these are all roots. It is possible to

double the number of parent pointers checked by choosing direct children of roots in each case.

6.9 For the “lists of Children” representation, every node stores a data value and a pointer to its list of children. Further, every child (every node except the root) has a record associated with it containing an index and a pointer. Indicating the size of the data value as D, the size of a pointer as P and the size of an index as I, the overhead fraction is 3P + I D + 3P + I .

For the “Left Child/Right Sibling” representation, every node stores three pointers and a data value, for an overhead fraction of 3P D + 3P .

The first linked representation of Section 6.3.3 stores with each node a data value and a size field (denoted by S). Each child (every node except the root) also has a pointer pointing to it. The overhead fraction is thus S + P D + S + P

making it quite efficient.

The second linked representation of Section 6.3.3 stores with each node a data value and a pointer to the list of children. Each child (every node except the root) has two additional pointers associated with it to indicate its place on the parent’s linked list. Thus, the overhead fraction is 3P D + 3P .

6.10 template

BinNode* convert(GTNode* genroot) { if (genroot == NULL) return NULL; 43

GTNode* gtemp = genroot->leftmost_child(); btemp = new BinNode(genroot->val(), convert(gtemp),

convert(genroot->right_sibling())); }

6.11 ? Parent(r) = (r ? 1)/k if 0 < r < n. ? Ith child(r) = kr + I if kr +I < n.

? Left sibling(r) = r ? 1 if r mod k = 1 0 < r < n.

? Right sibling(r) = r + 1 if r mod k = 0 and r + 1 < n.

6.12 (a) The overhead fraction is 4(k + 1) 4 + 4(k + 1).

(b) The overhead fraction is 4k

16 + 4k .

(c) The overhead fraction is 4(k + 2)

16 + 4(k + 2).

(d) The overhead fraction is 2k 2k + 4.

6.13 Base Case: The number of leaves in a non-empty tree of 0 internal nodes is (K ? 1)0 + 1 = 1. Thus, the theorem is correct in the base case. Induction Hypothesis: Assume that the theorem is correct for any full Kary tree containing n internal nodes.

Induction Step: Add K children to an arbitrary leaf node of the tree with n internal nodes. This new tree now has 1 more internal node, and K ? 1 more leaf nodes, so theorem still holds. Thus, the theorem is correct, by the principle of Mathematical Induction. 6.14 (a) CA/BG///FEDD///H/I// (b) CA/BG/FED/H/I 6.15 X | P ----- | | | C Q R --- | | V M

44 Chap. 6 General Trees

6.16 (a) // Use a helper function with a pass-by-reference // variable to indicate current position in the // node list.

template

BinNode* convert(char* inlist) {

int curr = 0;

return converthelp(inlist, curr); }

// As converthelp processes the node list, curr is // incremented appropriately. template

BinNode* converthelp(char* inlist, int& curr) {

if (inlist[curr] == ’/’) {

curr++; return NULL; }

BinNode* temp = new BinNode(inlist[curr++], NULL, NULL);

temp->left = converthelp(inlist, curr); temp->right = converthelp(inlist, curr); return temp; }

(b) // Use a helper function with a pass-by-reference // variable to indicate current position in the // node list.

template

BinNode* convert(char* inlist) { int curr = 0;

return converthelp(inlist, curr); }

// As converthelp processes the node list, curr is // incremented appropriately. template

BinNode* converthelp(char* inlist, int& curr) {

if (inlist[curr] == ’/’) {

curr++; return NULL; }

BinNode* temp =

new BinNode(inlist[curr++], NULL, NULL); if (inlist[curr] == ’\\’’) return temp; 45

curr++ // Eat the internal node mark. temp->left = converthelp(inlist, curr); temp->right = converthelp(inlist, curr); return temp; }