Solved

# Question for CEHJ - Binary Search Trees

Posted on 2003-03-17

Hi:

I need to write a method of the Tree class Comparable smallest() that returns the smallest element of a tree. Can you help me get started(do not give me the answer)?

public class TreeTest

{ public static void main(String[] args)

{ Tree staff = new Tree();

staff.insert("Romeo");

staff.insert("Juliet");

staff.insert("Tom");

staff.insert("Dick");

staff.insert("Harry");

staff.print();

}

}

/**

This class implements a binary search tree whose

nodes hold objects that implement the Comparable

interface.

*/

class Tree

{ /**

Constructs an empty tree.

*/

public Tree()

{ root = null;

}

/**

Inserts a new node into the tree.

@param obj the object to insert

*/

public void insert(Comparable obj)

{ Node newNode = new Node();

newNode.data = obj;

newNode.left = null;

newNode.right = null;

if (root == null) root = newNode;

else root.insertNode(newNode);

}

/**

Prints the contents of the tree in sorted order.

*/

public void print()

{ if (root != null)

root.printNodes();

}

/**

Method to return the smallest element in a tree.

@return

*/

public Comparable smallest()

{

return "something";

}

private Node root;

private class Node

{ /**

Inserts a new node as a descendant of this node.

@param newNode the node to insert

*/

public void insertNode(Node newNode)

{ if (newNode.data.compareTo(data) < 0)

{ if (left == null) left = newNode;

else left.insertNode(newNode);

}

else

{ if (right == null) right = newNode;

else right.insertNode(newNode);

}

}

/**

Prints this node and all of its descendants

in sorted order.

*/

public void printNodes()

{ if (left != null)

left.printNodes();

System.out.println(data);

if (right != null)

right.printNodes();

}

public Comparable data;

public Node left;

public Node right;

}

}