Solutions to other chapters:
Java Methods A & AB:
Object-Oriented Programming and Data Structures
Answers and Solutions to Exercises
Chapter 23
2. |
|
[log2 100000] + 1 = log2 131072 = 17 |
4. |
|
Base case: For h = 0 the
number of nodes in the tree
is 0 and 0 = 20-1.
Likewise, for h = 1 the
number of nodes in the tree
is 1 and 1 = 21-1.
Suppose the statement is true for
any h < n.
Take a tree with n levels.
From the inductive hypothesis,
the numbers of nodes in its left and
right subtrees do not exceed
2n-1 - 1.
Therefore, the total
number of nodes for the tree does not exceed
(2n-1 - 1) + (2n-1 - 1) + 1 = 2n - 1
QED. |
6. |
|
public boolean isLeaf(TreeNode node)
{
return node != null && node.getLeft() == null && node.getRight() == null;
} |
10. |
|
public int depth(TreeNode root)
{
if (root == null)
return -1;
return 1 + Math.max(depth(root.getLeft()), depth(root.getRight()));
} |
12. |
(a) |
public TreeNode copy(TreeNode root)
{
if (root == null)
return null;
return new TreeNode(root.getValue(), copy(root.getLeft()),
copy(root.getRight()));
} |
15. |
(a) |
-:-
/ \
2 +
/ \
-:- -:-
/ \ / \
1 x 1 y
|
|
(g) |
Inorder, preorder, and postorder traversals
of a binary tree visit its leaves in the same sequence.
You can use mathematical induction (over the total number of nodes)
to prove this fact: apply the induction hypothesis to the left and
the right subtrees. |
16. |
(b) |
T |
|
(c) |
F -- the tree may have degenerated
into a near linear shape |
18. |
|
475 557
/ \ / \
474 749 474 681
/ / / \ / \
292 623 292 475 623 749
/ \
557 681 |
19. |
|
L
/ \
G O
/ \ / \
A I M R
/ \
H T
Inorder: A G H I L M O R T Preorder: L G A I H O M R T
Postorder: A H I G M T R O L |
22. |
|
public TreeNode maxNode(TreeNode root)
{
if (root == null)
return null;
TreeNode node = root;
while (node.getRight() != null)
node = node.getRight();
return node;
} |
|