This program demonstrates a few routines for processing binary sort trees. It uses a binary sort tree of strings. The user types in strings. The user’s string is converted to lower case, and — if it is not already in the tree — it is inserted into the tree. Then the number of nodes in the tree and a list of items in the tree are output. The program ends when the user enters an empty string.
/*******************************************************
* MYCPLUS Sample Code - https://www.mycplus.com *
* *
* This code is made available as a service to our *
* visitors and is provided strictly for the *
* purpose of illustration. *
* *
* Please direct all inquiries to saqib at mycplus.com *
*******************************************************/
public class SortTreeDemo {
static class TreeNode {
// An object of type TreeNode represents one node
// in a binary tree of strings.
String item; // The data in this node.
TreeNode left; // Pointer to left subtree.
TreeNode right; // Pointer to right subtree.
TreeNode(String str) {
// Constructor. Make a node containing the specified string.
item = str;
}
} // end nested class TreeNode
static TreeNode root; // Pointer to the root node in a binary tree. This
// tree is used in this program as a binary sort tree.
// The tree is not allowed to contain duplicate
// items. When the tree is empty, root is null.
public static void main(String[] args) {
TextIO.putln("This programs stores strings that you enter in a binary sort");
TextIO.putln("tree. After each items is inserted, the contents of the tree");
TextIO.putln("are displayed. The number of nodes in the tree is also output.");
TextIO.putln(" Any string you enter will be converted to lower case.");
TextIO.putln("Duplicate entries are ignored.");
while (true) {
// Get one string from the user, insert it into the tree,
// and print some information about the tree. Exit if the
// user enters an empty string. Note that all strings are
// converted to lower case.
TextIO.putln("\n\nEnter a string to be inserted, or press return to end.");
TextIO.put("? ");
String item; // The user's input.
item = TextIO.getln().trim().toLowerCase();
if (item.length() == 0)
break;
if (treeContains(root,item)) {
// Don't insert a second copy of an item that is already
// in the tree.
TextIO.putln("\nThat item is already in the tree.");
}
else {
treeInsert(item); // Add user's string to the tree.
TextIO.putln("\nThe tree contains " + countNodes(root) + " items.");
TextIO.putln("\nContents of tree:\n");
treeList(root);
}
} // end while
TextIO.putln("\n\nExiting program.");
} // end main()
static void treeInsert(String newItem) {
// Add the item to the binary sort tree to which the global
// variable "root" refers. (Note that root can't be passed as
// a parameter to this routine because the value of root might
// change, and a change in the value of a formal parameter does
// not change the actual parameter.)
if ( root == null ) {
// The tree is empty. Set root to point to a new node containing
// the new item. This becomes the only node in the tree.
root = new TreeNode( newItem );
return;
}
TreeNode runner; // Runs down the tree to find a place for newItem.
runner = root; // Start at the root.
while (true) {
if ( newItem.compareTo(runner.item)
