public class Node {
String item; // The data in this node.
Node left; // Pointer to left subtree.
Node right; // Pointer to right subtree.
int freq = 1;
Node(String str) {
// Constructor. Make a node containing the specified string.
// Note that left and right pointers are initially null.
item = str;
}
} // end nested class TreeNode
//Driver Class:
import java.io.*;
import java.util.Scanner;
public class Driver{
public static void main(String[] args) {
BinaryTree tree = new BinaryTree(null);
Scanner input = new Scanner(System.in);
int select = 0;
System.out.println("Welcome to the Binary Search Tree program.");
select = tree.menuStart();
while (select != 4) {
// 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("? ");
while(select == 1){
System.out.print("Enter new string: ");
String item; // The user's input.
item = input.nextLine();
if (item.length() == 0)
System.out.println("Invalid input, please enter a string.");
if (tree.treeContains(tree.root,item)) {
// Don't insert a second copy of an item that is already
// in the tree.
System.out.println(item + " is already in the tree. It's frequency is now: " + tree.treeInsertFrequency(tree.root, item));
}
else {
tree.treeInsert(item, tree.root); // Add user's string to the tree.
} System.out.println("Please enter a new command: ");
select = tree.menuStart();
}
while(select == 2) {
System.out.println("Please enter the string to search for: ");
String item = input.nextLine();
if (item.length() == 0)
System.out.println("Invalid search input, please enter a string.");
tree.Show();
if (tree.treeContains(tree.root,item)) {
System.out.println(item + " exists in the tree. It's frequency is " + tree.treeFrequency(tree.root, item));
} else System.out.println("String does not exist in the Binary Tree.");
select = tree.menuStart();
}
while(select == 3){
System.out.println("The tree contains " + tree.countNodes(tree.root) + " unique strings.");
System.out.println("Contents of tree:");
tree.preOrderList(tree.root);
select = tree.menuStart();}
}
// end while
}}
//Finally the problem, the BinaryTree class:
import java.io.*;
import java.util.Scanner;
public class BinaryTree{
public static int size =1;
public static Node root = new Node(null);
public BinaryTree(String str){
String initStr = str;
}
static int menuStart(){
Scanner input = new Scanner(System.in);
System.out.println("Enter one of the following numbers to use the tree:");
System.out.println("1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.");
int temp = 0;
temp = input.nextInt();
while(temp!=1 && temp!=2 && temp!=3 && temp!=4){
System.out.println("Invalid command, choose a number 1-4 please.");
temp = input.nextInt();
}
return temp; }
public static void treeInsert(String newItem, Node r) {
String it = newItem;
if(r == null){
r = new Node(newItem);}
else{
System.out.println(treeBalance(r));
System.out.println(r);
if(r == null){
r = new Node(it);
System.out.println(r.item);}
else{
if(treeBalance(r) == true)
treeInsert(newItem, r.left);
else
treeInsert(newItem, r.right);}
} }
public static void Show(){
System.out.println(root.item);
}
public static void setNode(String it, Node sr){
if(sr == null){
sr = new Node(it);}
else{
if(treeBalance(sr) == true)
sr = sr.left;
else
sr = sr.right;
setNode(it, sr);
}
}
static boolean treeBalance(Node b){
if((countNodes(b.left) == countNodes(b.right)) || (countNodes(b.left) < countNodes(b.right)
))
return true;
else
return false;}
/**
* Return true if item is one of the items in the binary
* sort tree to which root points. Return false if not.
*/
static boolean treeContains( Node root, String item ) {
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 != null) {
// 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 int treeInsertFrequency( Node rf, String item ) {
if ( rf == null ) {
// Tree is empty, so it certainly doesn't contain item.
return 0;
}
else if ( item.equals(rf.item) ) {
// Yes, the item has been found in the rf node.
rf.freq++;
return rf.freq;
}
else if ( item.compareTo(rf.item) < 0 ) {
// If the item occurs, it must be in the left subtree.
return treeInsertFrequency( rf.left, item );
}
else {
// If the item occurs, it must be in the right subtree.
return treeInsertFrequency( rf.right, item );
}
}
static int treeFrequency( Node f, String item ) {
if ( f == null ) {
// Tree is empty, so it certainly doesn't contain item.
return 0;
}
else if ( item.equals(f.item) ) {
// Yes, the item has been found in the f node.
return f.freq;
}
else if ( item.compareTo(f.item) < 0 ) {
// If the item occurs, it must be in the left subtree.
return treeFrequency( f.left, item );
}
else {
// If the item occurs, it must be in the right subtree.
return treeFrequency( f.right, item );
}
}
static boolean rootExists(){
if(root == null){
return false;
} else return true;
}
public static void preOrderList(Node node) {
if ( node != null ) {
System.out.println(node.item + " ");
preOrderList(node.left); // Print items in l subtree.
// Print item in the node.
preOrderList(node.right); // Print items in the r subtree.
}
} // end preOrderList()
/**
* Count the nodes in the binary tree.
* @param node A pointer to the root of the tree. A null value indicates
* an empty tree
* @return the number of nodes in the tree to which node points. For an
* empty tree, the value is zero.
*/
public static int countNodes(Node node) {
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()
LinkBack URL
About LinkBacks
Help with my Binary tree. (Node links are incorrect) Please!
Reply With Quote
Related threads:
Re: Help with my Binary tree. (Node links are incorrect) Please!
Originally Posted by Norm
