BINARY SEARCH TREES - Introduction to Java Programming: Comprehensive Version - page 960

P ROGRAMMING E XERCISES

Sections 25.2-25.6
*25.1

( Add new methods in BST ) Add the following new methods in BST .

/** Displays the nodes in a breadth-first traversal */
public void breadthFirstTraversal()

/** Returns the height of this binary tree */
public int height()

*25.2

( Test full binary tree ) A full binary tree is a binary tree with the leaves on the
same level. Add a method in the BST class to return true if the tree is a full
binary tree. ( Hint : The number of nodes in a full binary tree is 2 depth - 1.)

/** Returns true if the tree is a full binary tree */
boolean isFullBST()

**25.3

( Implement inorder traversal without using recursion ) Implement the inorder
method in BST using a stack instead of recursion. Write a test program that
prompts the user to enter 10 integers, stores them in a BST, and invokes the
inorder method to display the elements.

**25.4

( Implement preorder traversal without using recursion ) Implement the
preorder method in BST using a stack instead of recursion. Write a test pro-
gram that prompts the user to enter 10 integers, stores them in a BST, and
invokes the preorder method to display the elements.

**25.5

( Implement postorder traversal without using recursion ) Implement the
postorder method in BST using a stack instead of recursion. Write a test
program that prompts the user to enter 10 integers, stores them in a BST, and
invokes the postorder method to display the elements.

**25.6

( Find the leaves ) Add a method in the BST class to return the number of the
leaves as follows:

/** Returns the number of leaf nodes */
public int getNumberOfLeaves()

**25.7

( Find the nonleaves ) Add a method in the BST class to return the number of the
nonleaves as follows:

/** Returns the number of nonleaf nodes */
public int getNumberofNonLeaves()

***25.8

( Implement bidirectional iterator ) The java.util.Iterator interface defines
a forward iterator. The Java API also provides the java.util.ListIterator
interface that defines a bidirectional iterator. Study ListIterator and define
a bidirectional iterator for the BST class.

**25.9

( Tree clone and equals ) Implement the clone and equals methods in the
BST class. Two BST trees are equal if they contain the same elements. The
clone method returns an identical copy of a BST .