Java Reference
In-Depth Information
techniques, see Managing Gigabytes by Witten, Moffat, and Bell [WMB99], and
Codes and Cryptography by Dominic Welsh [Wel88].
Tables 5.23 and 5.24 are
derived from Welsh [Wel88].
5.8
Exercises
5.1 Section 5.1.1 claims that a full binary tree has the highest number of leaf
nodes among all trees with n internal nodes. Prove that this is true.
5.2 Define the degree of a node as the number of its non-empty children. Prove
by induction that the number of degree 2 nodes in any binary tree is one less
than the number of leaves.
5.3 Define the internal path length for a tree as the sum of the depths of all
internal nodes, while the external path length is the sum of the depths of all
leaf nodes in the tree. Prove by induction that if tree T is a full binary tree
with n internal nodes, I is T's internal path length, and E is T's external path
length, then E = I + 2n for n 0.
5.4 Explain why function
preorder2
from Section 5.2 makes half as many
recursive calls as function
preorder
. Explain why it makes twice as many
accesses to left and right children.
5.5 (a) Modify the preorder traversal of Section 5.2 to perform an inorder
traversal of a binary tree.
(b) Modify the preorder traversal of Section 5.2 to perform a postorder
traversal of a binary tree.
5.6 Write a recursive function named
search
that takes as input the pointer to
the root of a binary tree (not a BST!) and a value K, and returns
true
if
value K appears in the tree and
false
otherwise.
5.7 Write an algorithm that takes as input the pointer to the root of a binary
tree and prints the node values of the tree in level order. Level order first
prints the root, then all nodes of level 1, then all nodes of level 2, and so
on. Hint: Preorder traversals make use of a stack through recursive calls.
Consider making use of another data structure to help implement the level-
order traversal.
5.8 Write a recursive function that returns the height of a binary tree.
5.9 Write a recursive function that returns a count of the number of leaf nodes in
a binary tree.
5.10 Assume that a given BST stores integer values in its nodes. Write a recursive
function that sums the values of all nodes in the tree.
5.11 Assume that a given BST stores integer values in its nodes. Write a recursive
function that traverses a binary tree, and prints the value of every node who's
grandparent has a value that is a multiple of five.
