Java Reference
In-Depth Information
Methods within
BinaryTree
.
The methods
getHeight
and
getNumberOfNodes
are more interesting
than the methods given in the previous segment. Although we could perform the necessary compu-
tations within the class
BinaryTree
, performing them within the class
BinaryNode
is easier. Thus,
the following methods of
BinaryTree
invoke analogous methods of
BinaryNode
:
public int
getHeight()
{
return
root.getHeight();
}
// end getHeight
public int
getNumberOfNodes()
{
return
root.getNumberOfNodes();
}
// end getNumberOfNodes
We now complete the methods
getHeight
and
getNumberOfNodes
within
BinaryNode
.
24.11
Methods within
BinaryNode
.
Within
BinaryNode
, the method
getHeight
returns the height of the
subtree rooted at the node used to invoke the method. Likewise,
getNumberOfNodes
returns the
number of nodes within that same subtree.
The public method
getHeight
can call a private recursive method
getHeight
that has a node
as its parameter. The height of the tree rooted at a node is 1—for the node itself—plus the height of
the node's tallest subtree. Thus, we have the following implementation:
public int
getHeight()
{
return
getHeight(
this
);
// call private getHeight
}
// end getHeight
private int
getHeight(BinaryNode<T> node)
{
int
height = 0;
if
(node !=
null
)
height = 1 + Math.max(getHeight(node.left),
getHeight(node.right));
return
height;
}
// end getHeight
We could implement
getNumberOfNodes
by using the same approach, but instead we will
show you another way. The number of nodes in a tree rooted at a given node is 1—for the node
itself—plus the number of nodes in both the left and right subtrees. Thus, we have the following
recursive implementation:
public int
getNumberOfNodes()
{
int
leftNumber = 0;
int
rightNumber = 0;
if
(left !=
null
)
leftNumber = left.getNumberOfNodes();
if
(right !=
null
)
rightNumber = right.getNumberOfNodes();
return
1 + leftNumber + rightNumber;
}
// end getNumberOfNodes
