New Topic/Question
Reply
import java.io.*;
import java.io.FileReader;
import java.io.IOException;
public class SearchTree {
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) {
System.out.println("This programs stores strings that you enter in a binary sort");
System.out.println("tree. After each items is inserted, the contents of the tree");
System.out.println("are displayed. The number of nodes in the tree is also output.");
System.out.println("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.
System.out.println("\n\nEnter a string to be inserted, or press return to end.");
System.out.print("? ");
String item = StdIn.readString();
int c;
if ((c = item.read()) == 0)
break;
if (treeContains(root,item)) {
// Don't insert a second copy of an item that is already
// in the tree.
System.out.println("\nThat item is already in the tree.");
}
else {
treeInsert(item); // Add user's string to the tree.
System.out.println("\nThe tree contains " + countNodes(root) + " items.");
System.out.println("\nContents of tree:\n");
treeList(root);
}
} // end while
System.out.println("\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) < 0 ) {
// Since the new item is less than the item in runner,
// it belongs in the left subtree of runner. If there
// is an open space at runner.left, add a new node there.
// Otherwise, advance runner down one level to the left.
if ( runner.left == null ) {
runner.left = new TreeNode( newItem );
return; // New item has been added to the tree.
}
else
runner = runner.left;
}
else {
// Since the new item is greater than or equal to the item in
// runner it belongs in the right subtree of runner. If there
// is an open space at runner.right, add a new node there.
// Otherwise, advance runner down one level to the right.
if ( runner.right == null ) {
runner.right = new TreeNode( newItem );
return; // New item has been added to the tree.
}
else
runner = runner.right;
}
} // end while
} // end treeInsert()
static boolean treeContains( TreeNode root, String item ) {
// Return true if item is one of the items in the binary
// sort tree to which root points. Return false if not.
if ( root == null ) {
// Tree is empty, so it certainly doesn't contain item.
return false;
}
else if ( item.equals(root.item) ) {
// Yes, the item has been found in the root node.
return true;
}
else if ( item.compareTo(root.item) < 0 ) {
// If the item occurs, it must be in the left subtree.
return treeContains( root.left, item );
}
else {
// If the item occurs, it must be in the right subtree.
return treeContains( root.right, item );
}
} // end treeContains()
static void treeList(TreeNode node) {
// Print the items in the tree in postorder, one item
// to a line. Since the tree is a sort tree, the output
// will be in increasing order.
if ( node != null ) {
treeList(node.left); // Print items in left subtree.
System.out.println(" " + node.item); // Print item in the node.
treeList(node.right); // Print items in the right subtree.
}
} // end treeList()
static int countNodes(TreeNode node) {
// Count the nodes in the binary tree to which node
// points. Return the answer.
if ( node == null ) {
// Tree is empty, so it contains no nodes.
return 0;
}
else {
// Add up the root node and the nodes in its two subtrees.
int leftCount = countNodes( node.left );
int rightCount = countNodes( node.right );
return 1 + leftCount + rightCount;
}
} // end countNodes()
}
And when I complile the programme I get:
arron@arron-laptop:~/University$ javac SearchTree.java
SearchTree.java:44: cannot find symbol
symbol : variable StdIn
location: class SearchTree
String item = StdIn.readString();
^
SearchTree.java:46: cannot find symbol
symbol : method read()
location: class java.lang.String
if ((c = item.read()) == 0)
^
2 errors
I've been mulling this over and am pretty much getting anywhere. Oh btw I'm sorting names into alphabetical order.....
Thanks in advance for any help.
MultiQuote
| 