Binary Tree
You might want to read these notes about trees before working on this program :
Trees
Introduction
/*** Binary Tree *******************************************************\
A BINARY SEARCH TREE stores Strings in "alphabetical order",
in the sense that it's very easy to print an alphabetical
list of the Strings. Here is an example of a properly ordered
binary search tree.
Mildred
/ \
Chuck Sue
/ \ / \
Alex Ellen Pete Tommy
This program reads strings from the keyboard, in any order.
Each word is inserted into the binary search tree in the proper position.
Then an in-order traversal prints the words in alphabetical order.
This concept could be used to sort a text file, if the input came
from a text file and the output went back into the same file.
\***********************************************************************/
class TreeNode
{
String data;
TreeNode leftChild;
TreeNode rightChild;
public TreeNode(String info)
{
data = info;
leftChild = null;
rightChild = null;
}
}
TreeNode root = null;
void setup()
{
makeTree();
showTree(root);
}
public void makeTree()
{
root = null;
String word = "";
do
{
word = input("Type a word (xxx to quit):");
if (!word.equals("xxx"))
{ addTreeNode(word); }
} while(!word.equals("xxx"));
}
public void addTreeNode(String word)
{
boolean done = false;
if (root == null)
{
root = new TreeNode(word);
done = true;
}
TreeNode temp = root;
while (!done)
{
if (temp.data.equals(word))
{ done =
true;
}
// word found, so don't add
else if (word.compareTo(temp.data)<0)
{
if (temp.leftChild == null)
{ temp.leftChild = new TreeNode(word);
done = true;
}
else
{ temp = temp.leftChild; }
}
else
{
if (temp.rightChild == null)
{ temp.rightChild = new TreeNode(word);
done = true;
}
else
{ temp = temp.rightChild; }
}
}
return;
}
public void showTree(TreeNode here)
{
if (here == null)
{ return; }
else
{
showTree(here.leftChild);
println(here.data);
showTree(here.rightChild);
}
}
public void output(String message)
{ javax.swing.JOptionPane.showMessageDialog(this,message); }
public String input(String prompt)
{ return javax.swing.JOptionPane.showInputDialog(this,prompt); }
//****************************************************************\\
(1) Run the program. Try typing in a variety of lists of words,
and check that each time the program prints the words in
correct alphabetical order.
(2) Change "showTree" so that it prints the names in REVERSE order.
This only requires changing the order of the commands in
the "showTree" method.
(3) Add a new method called "sampleData" that automatically inserts
8 names into the tree when the program starts.
(4) Change the program so that it starts by inserting sample data,
and then inputs a name to SEARCH for. Then it uses a SEARCH
method to TRAVERSE the tree and then tell whether the name
was found or not found. The SEARCH method is very similar
to the "showTree" method, except that it should not print
all the names - instead, it checks whether the right name
is found and print "found", and then quit. If it makes it
all the way through the tree without printing "found", then
it prints "not found" at the end.
\\****************************************************************//