b. What is the maximum number of nodes that a binary tree of depth d can have?
2. Suppose t is a binary tree with n internal nodes and m terminal nodes. T is a full binary tree if each of its nodes has zero or two successors. What is the relation between m and n when t is a fully binary tree?
3. There are 0, 1, 2, and 5 distinct binary trees with, respectively, 0, 1, 2, and 3 nodes.
a. how many distinct binary trees are there with 4 nodes?
b. Can you find a formula for the number of distinct binary trees with n nodes? This formula bt(n) may be expressed in terms of bt(k) for k < n.
4. Modify the program segments of Section 7.2.1 so that they work correctly in all cases.
5. a. Suppose the binary tree that follows is preorder, inorder, and postorder traversed. List the order in which the nodes will be accessed for each.
b. Do you notice anything striking about the inorder listing?
6. Prove that all terminal nodes will always be accessed in the same relative order for all three travelsals.
7. a. Suppose the stack used in a pre-, in-, or postorder traversal is implemented as an array. What is the requirement for limit in terms of the depth of the binary tree, to guarantee that the stack is large enough for the traversal to work?
b. What is the necessary value for limit in order to guarantee that the traversal will work with the stack, for any binary tree with n nodes?
8. Suppose the following two binary trees are preorder and postorder traversed. The preorder and postorder listings are given for each tree.
Both binary trees have identical listings. This cannot happen with preorder and inorder listings. That is, we cannot find two distinct binary trees that have identical preorder and inorder listings. The same is true for postorder and inorder listings. Find an algorithm that will create the unique binary tree that is thus determined by its preorder and inorder listings.
9. a. Can you find a way to use the left and right pointer fields of terminal and internal nodes that contain null pointers in a binary tree to create "threaded binary trees" so that they can be traversed without using a stack? (Hint: Consider pointers that point to the predecessor and successor of a terminal node in an inorder traversal.)
b. What about for inorder and postorder traversals?
10. Write inorder and postorder traversal routines (nonrecursive and recursive).
11. a. Suppose you wish to use a linked representation for binary trees with an array implementation as in Figure 7.10. Suppose tht input is given as a name value followed by a sequence of records, each record representing a node of a binary tree. For the binary tree fred of Figure 7.10, the input would be
Three records appear in the input in the order in which they would be accessed by a preorder traversal. Assume the head value is read into fred, and preorder traverse is called. Write a process routine that will turn preorder traverse into a routine that reads the records of the binary tree into the leftptr, info, and rightptr fields properly.
b. Same as Exercise 11(a), but assume the records are given in the order in which they would be accessed in a postorder traversal.
12. The binary tree sample is stored using a linked representation. List the order in which its nodes will be accessed in a preorder traversal.
13. What will be in the stack during a preorder traversal of sample in Exercise 12 when its rightmost node is accessed? What about when it is inorder and postorder traversed?
14. a. Suppose every subtree of sample of Exercise 12 is interchanged with its right subtree. What will leftptr, info, and rightptr look like?
b. What would leftptr, info, and rightptr look like if all the terminal nodes of sample were deleted in Exercise 12?
15. Suppose a binary tree is stored using the records array implementation as in Figure 7.10. If tree points to its root node, write a function to print out the sequence of pointers that specify the path in the tree to the right most node in tree. For example, in Figure 7.10 the rightmost node of fred is 1, and the sequence of pointers to be printed out for fred would be 6, 1, 5.
16. a. If the binary tree of Figure 7.5 were represented sequentially, what numbers would be assigned to its nodes?
b. What binary tree with n nodes will require the largest array for its sequential representation?
17. When dealing with arbitrary binary trees, would you use linked or sequential representation? Why?
18. a. Write a function that will return, given a binary tree t, with a pointer to a terminal node of t containing the largest value in its information field.
b. Write a function that, given a binary tree t and two pointers p and q to nodes of t, returns a value true if node.q is a successor of node.p and a value false otherwise.
c. Write a function that does the same thing as Exercise 18(b), except that the function returns a value true if node.q is in the subtree of node.p and a value false otherwise.
19. Consider the binary tree that was produced by the transformation from a general tree to a binary tree as a general tree, and find the binary tree produced by its transformation.
20. Consider again the solution to the information retrieval problem of Chapter 6. Suppose you create a record, r, in memory. R will have a pointer field pointing to the record for a father. You can then think of r as a record representing the node of a binary tree.
a. Describe this binary tree.
b. What general tree would have r as its binary tree under the transformation of Section 7.5.1?
21. a. Write a function to append a binary tree t1 to a binary tree t2 by replacing some terminal node in t2 at least depth by the whole tree t1. For example, see the figure. Use a linked representation with pointer variables.
b. What does your function do if t1 and t2 are the same tree?
c. How will your solution change if a sequential representation is used?
22. a. Write a routine that deletes all the terminal nodes of a binary tree.
b. Write a routine that deletes node.q if it is a successor of node.p in a binary tree.
23. a. Write a function to interchange all left and right subtrees of a binary tree.
b. Create a function to interchange all left and right subtrees, except that the interchanged version of the original tree will be created as a new tree, leaving the original tree unchanged. Assume pointer variables are used for its implementation.
24. a. Modify the preorder traversal so that it returns, in a variable identical, a value true if t1 and t2 point to identical trees, and a value false otherwise. That is, the value is true if the two trees have the same structure and the same information field values.
b. Do the same task, except that the binary trees need have only the same structure.
25. a. Suppose you are given a maze with the structure of a binary tree. The maze has a starting point and an exit. A node is associated with the starting point, with the exit, and with every point in the maze where one of two paths must be taken. The maze is given as a two-dimensional array a. A [i,j] is 1 if there is a path from node i to node j in the maze, and is 0 otherwise. There are n points in the maze. Adapt the preorder traversal to achieve an algorithm for solving the maze?/FONT>that is, for printing out the path from the starting node to the exit node. Your solution should be detailed enough to write a function corresponding to it directly.
b. If the maze has loops, what modifications must be made in your solution so that the algorithm works correctly?
26. a. Modify the preorder traversal algorithm for creating a binary tree from a general tree (p. 332) and the process algorithm so the preorder traversal returns, in the variable transform, a value "true" only if a binary tree bt is the transformed version of a general tree t.
b.
27. Write the function create used in the process algorithm.
28. Modify the backtracking preorder traversal algorithm so that it does a backtracking breadth-first traversal.
29. Suppose you are given a "map" of n cities and the distances between them. Can you find a way to modify the preorder traversal algorithm to determine the shortest distance between two cities? What is a feasible test to use to allow feasible to limit the execution time of the solution?
30. a. Suppose a general tree is given as follows:
(A(B(E, F, G), C(H), D(I(K, L, M), J)))
This corresponds to the general tree:
Suppose that input is given by such a parenthesized expression. Can you find an algorithm that will create the general tree from it? Assume that the general tree will be represented in memory as a collection of lists of successors, with one successor list for each node.
b. What is the connection between parenthesized expressions and a listing of nodes in the order in which they are accessed by a preorder traversal?
31. T is a binary tree. Result(t) is defined by
Left(t) and right(t) are, respectively, the left and right subtrees of t.
a. If t is the binary tree that follows, then what is result(t)?
b. What does result do?
32. T1 and t2 point to binary trees represented using pointer variables.
a. Find the function value if it is invoked for trees t1 and t2.
b. What does check do?
33. a. Find b(4) where
b. Find a connection between the number of distinct binary trees with n nodes and b(n).
34. a. Give a recursive definition of balanced binary trees.
b. Find a recursive definition for F(d), the number of nodes of a Fibonacci tree of depth d.
35. Write a recursive function result corresponding to Exercise 31.
36. a. Write a recursive function count to return the number of terminal nodes of a binary tree.
b. Write a recursive function terminal to delete all terminal nodes of a binary tree using pointer variables.
37. Write a recursive routine partialexchange to interchange all subtrees of a binary tree whose left subtree info field value exceeds the right subtree value. Assume the binary tree is represented using pointer variables.
38. Write a recursive function using pointers to transform a general tree into its binary tree representation.
39. Write a recursive program that produces a solution, if one exists, to the n-queens problem.
40. Write a recursive function to produce a copy of a binary tree. Both trees should be implemented using pointers.
5
8 L 0
-1 O -1
3 U 4
-1 S -1
-1 T -1
leftptr info rightptr
1 0 R 0
2 3 W 4
3 5 R 0
sample 7 4 0 C 0
5 4 E 6
6 0 T 0
7 10 C 3
8 6 A 3
9 1 B 4
10 1 O 0
(a) Input
(b) Output
check (t1,t2)
binarytreepointer t1,t2;
{binarytreepointer null,setnull();
null = setnull();
if(((t1 == null) && (t2 == null)) || ((t1 != null)
&& (t2 != null)))
return(check(t1->leftptr,t2->leftptr)
&& check(t1->rightptr,t2->rightptr));
else
return (FALSE);
}
b(0) = 1
b(n) = b(0) ?/FONT> b(n - 1) + b(1) ?/FONT> b(n - 2) + b(2)b(n - 3) + . . .
+ b(n - 1) x b(0) n > 0