Java Reference
In-Depth Information
What is the output of the method presented in Figure 18.34 for the
tree shown in Figure 18.25?
18.3
Show the stack operations when an inorder and preorder traversal is
applied to the tree shown in Figure 18.25.
18.4
IN THEORY
18.5
Show that the maximum number of nodes in a binary tree of height
H
is 2
H
+ 1
- 1.
A
full node
is a node with two children. Prove that in a binary tree the
number of full nodes plus 1 equals the number of leaves.
18.6
How many
null
links are there in a binary tree of
N
nodes? How
many are in an
M
-ary tree of
N
nodes?
18.7
Suppose that a binary tree has leaves
l
1
l
2
,, ,
…
l
M
at depths
18.8
M
-
d
i
d
1
d
2
,
,
…
,
d
M
,
respectively. Prove that
∑
2
≤
1
and determine
i
=
1
when equality is true (known as
Kraft's inequality
).
IN PRACTICE
18.9
Write efficient methods (and give their Big-Oh running times) that
take a reference to a binary tree root
T
and compute
a.
The number of leaves in
T
b.
The number of nodes in
T
that contain one non-
null
child
c.
The number of nodes in
T
that contain two non-
null
children
Suppose a binary tree stores integers. Write efficient methods (and
give their Big-Oh running times) that take a reference to a binary tree
root
T
and compute
a.
18.10
The number of even data items
b.
The sum of all the items in the tree
1
public static <AnyType> void mysteryPrint( BinaryNode<AnyType> t )
2
{
3
if( t != null )
4
{
5
System.out.println( t.getElement( ) );
6
mysteryPrint( t.getLeft( ) );
7
System.out.println( t.getElement( ) );
8
mysteryPrint( t.getRight( ) );
9
System.out.println( t.getElement( ) );
10
}
11
}
figure 18.34
Mystery program for
Exercise 18.3
Search WWH ::
Custom Search