Tree Implementations - Data Structures and Abstractions with Java - page 604

Creating a Basic Binary Tree

24.4

Recall from Segment 23.18 of the previous chapter the following interface for a class of binary trees:

public interface BinaryTreeInterface<T>
extends TreeInterface<T>, TreeIteratorInterface<T>

{

public void setTree(T rootData);
public void setTree(T rootData, BinaryTreeInterface<T> leftTree,
BinaryTreeInterface<T> rightTree);

} // end BinaryTreeInterface

Recall that TreeInterface in Segment 23.16 specifies basic operations— getRootData , getHeight ,
getNumberOfNodes , isEmpty , and clear —common to all trees, and TreeIteratorInterface in
Segment 23.17 specifies operations for traversals of a tree. These three interfaces are in our package
TreePackage .
We begin our implementation of a binary tree with constructors and the setTree methods, as given
in Listing 24-3. The private method privateSetTree has parameters of type BinaryTree , whereas the
public setTree that the interface specifies has parameters of type BinaryTreeInterface . We use this
private method in the implementation of setTree to simplify the casts from BinaryTreeInterface to
BinaryTree .
The third constructor—which has parameters of type BinaryTree —also calls privateSetTree .
If it called setTree , we would declare setTree as a final method so that no subclass could override it
and thereby change the effect of the constructor. Note as well that we could have named the private
method setTree instead of privateSetTree .

VideoNote

Creating a binary tree

LISTING 24-3

A first draft of the class BinaryTree

package TreePackage;
import java.util.Iterator;
import java.util.NoSuchElementException;
import StackAndQueuePackage.*; // needed by tree iterators
/**

A class that implements the ADT binary tree.
@author Frank M. Carrano.

*/
public class BinaryTree<T> implements BinaryTreeInterface<T>
{

private BinaryNodeInterface<T> root;

public BinaryTree()
{

root = null ;
} // end default constructor

public BinaryTree(T rootData)
{

root = new BinaryNode<T>(rootData);
} // end constructor