Program 8

package program8;

import java.io.*;

public class Main
{

// Program #8
// Zach Krizan
// Data Structures

public static void main(String[] args) throws IOException
{
/*********************************************************************
* This program will demonstrate a tree using Dynamic Memory.
* It will display text asking the user to enter either 'i' or 'x'.
* 'i' will be to insert a value, and 'x' will be to end the program
* Once you insert a value, it will be added to the tree, then it will
* traverse the tree in in-order.
**********************************************************************/

int value;
Tree theTree = new Tree(); //tree object


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

//user instructions
System.out.println();
System.out.print("Type 'i' to insert or 'x' to exit: ");
int choice = getChar();
switch(choice) //switch statement for i or x
{
case 'i': //inserts the value, then traverses
System.out.println();
System.out.print("Enter value to insert: ");
value = getInt();
theTree.insert(value);
System.out.println();
System.out.println("Traversing...");
theTree.traverse();
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 program8;

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

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


}

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

package program8;

/*********************
* 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 void find(int key)
{
//this method will be implemented for program # 9
}

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

}