Program 9

package program9;

import java.io.*;

public class Main {

// Program #9
// Zach Krizan
// Data Structures

public static void main(String[] args) throws IOException {
/*********************************************************************
* This program will demonstrate searching a tree.
* It will insert 7 numbers into the tree.
* Then it will traverse the tree in in-order.
* Next it will ask the user if they want to find a value in the tree.
* They can either enter 'f' to find a value or 'x' to exit the program.
* The user will enter a value to search for.
* The results will be either: "Found {value}" or "Could not Find value".
* This will loop until the user enters 'x'.
**********************************************************************/
int value;
Tree theTree = new Tree(); //tree object


System.out.println("Inserting...");
theTree.insert(4);
theTree.insert(2);
theTree.insert(6);
theTree.insert(1);
theTree.insert(3);
theTree.insert(5);
theTree.insert(7);
System.out.println("The values inserted are 4,2,6,1,3,5,7");

System.out.println();
System.out.println("Traversing...");
theTree.traverse();




//This loop will run until the user enters 'x' to end the program
while (true) {

//user instructions
System.out.println();
System.out.print("Enter 'f' to find a value or " +
"'x' to exit the program: ");
int choice = getChar();
switch (choice) //switch statement for i or x
{
case 'f':
System.out.println();
System.out.print("Insert a value to search for: ");
value = getInt();
Node found = theTree.find(value);
if(found != null)
{
System.out.print("Found: ");
found.displayNode();
System.out.print("\n");
}
else
System.out.println("Could not find: " + value );
System.out.println();
break;
case 'x': //ends program
System.out.println("Program will now end");
System.exit(0);
default: //shows the user they incorrectly inputted
System.out.print("Invalid entry\n");
} //end switch

}//end while
} //end main

//method getString
public static String getString() throws IOException {
//uses IOException on the string
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}

//method getChar
public static char getChar() throws IOException {
//uses IOException on the char
String s = getString();
return s.charAt(0);
}

//method getInt
public static int getInt() throws IOException {
//uses IOException on the int
String s = getString();
return Integer.parseInt(s);
}
} //end Main




/***************************************
*
* Page 2
*
***************************************/

package program9;

/*************************
* Node Class
************************/

public class Node
{
public int value; //data used as key value
Node left; //his node's left child
Node right; //this node's right child


//method displayNode
public void displayNode()
{
//This method will print the Node's value
System.out.print('{');
System.out.print(value);
System.out.print('}');
}

}


/***************************************
*
* Page 3
*
***************************************/



package program9;

/*********************
* Tree Class
*********************/
public class Tree {

private Node root; // the only data field in Tree

//constructor
public Tree() {
root = null;
}

//method insert
public void insert(int v) {
/**************************************************
* This method will insert a node into the tree.
* It will follow the standard binary tree rule.
******************************************************/

Node newNode = new Node(); //make new node
newNode.value = v; //insert data
if (root == null) //no node in root
{
root = newNode;
} else {
Node current = root; //start at root
Node parent;
while (true) //exists internally
{
parent = current;
if (v < current.value) //go left
{
current = current.left;
if (current == null) //if end of the line
{
parent.left = newNode;
return;
}
} //end if go left
else {
current = current.right;
if (current == null) //if end of the line
{
parent.right = newNode;
return;
}
} //end else go right
} // end while
} //end else not root
} // end insert

//method traverse
public void traverse() {

System.out.println();
inOrder(root);
}

//method inOrder
public void inOrder(Node localRoot) {
//This method will traverse the tree and print the nodest in order
//An example of in order (infix):
//If the root is A, the left child is B, and the right child is C
//The infix order would be B,A,C


if (localRoot != null) {
inOrder(localRoot.left);
System.out.print(localRoot.value + " ");
inOrder(localRoot.right);
}

}

//method find
public Node find(int key)
{
//
Node current = root; //start a root
while(current.value != key) //while no match
{
if (key < current.value) //go left
current = current.left;
else //go right
current = current.right;
if (current == null) //if no child
return null; //didn't find
} // end while loop
return current; //found it
}



//method delete
public void delete(int id) {
//this method will be implemented for program #10
}
}