Java Reference
In-Depth Information
10.
What binary tree represents the general tree in each of the following figures from the previous chapter?
a.
Figure 23-5
b.
Figure 23-21
11.
Given a general tree, consider an equivalent binary tree. Define a traversal of this binary tree that is equivalent to
a level-order traversal of the general tree.
12.
Knowing the preorder and inorder traversals of a binary tree will enable you to uniquely define the tree. The same
is true for the postorder and inorder traversals.
a.
Draw the unique binary tree that has the following preorder and inorder traversals:
Preorder: A, B, D, E, C, F, G, H
Inorder: E, D, B, A, G, F, H, C
b.
Draw the unique binary tree that has the following postorder and inorder traversals:
Postorder: B, D, F, G, E, C, A
Inorder: B, A, D, C, F, E, G
13.
Although you can uniquely construct a binary tree from either its preorder and inorder traversals or its postorder
and inorder traversals, more than one binary tree can have the same preorder traversal and the same postorder
traversal. Give an example of two different binary trees that have the same preorder and postorder traversals.
14.
Suppose we want to create a method for the class
BinaryTree
that decides whether two trees have the same
structure. The header of the method could be as follows:
public boolean
isIsomorphic(BinaryTreeInterface<T> otherTree)
Write this method, using a private recursive method of the same name.
15.
Consider two binary trees that have the same structure. A node in one tree can contain different data than the
corresponding node in the other tree. Write code that uses a dictionary to map the objects in the first tree to the
corresponding objects in the second tree.
16.
Sometimes you need to move from a tree node to its parent. To do this, a binary tree node would need a reference
to its parent. You then would be able to traverse a path from a leaf to the root. Redesign the node used in a binary
tree so that each one has a reference to its parent as well as to its left child and right child. What methods will need
to be changed?
17.
Another way of representing a binary tree is to use an array. The items in the tree are assigned to locations in the array
in a level-order fashion. For example, Figure 24-11 shows an array that represents the binary tree in Figure 24-10.
Notice that gaps in the array correspond to missing nodes in the tree. The array is sufficiently large to represent any
binary tree up to height 4.
a.
What are the indices of the children of the node stored at index
i
?
b.
What is the parent of the node stored at index
i
?
c.
What are the advantages and disadvantages of this representation?
FIGURE 24-11
An array for Exercise 17 that represents the binary tree in Figure 24-10
g
a
b
c
d
e
h
f
14
0
1
2
3
4
5
7
8
9
10
11
12
13
6
