package program10;
import java.io.*;
public class Main {
// Program #10
// Zach Krizan
// Data Structures
public static void main(String[] args) throws IOException {
/*********************************************************************
* This program will demonstrate deleting from a tree.
* It will insert 7 numbers into the tree.
* Then it will traverse the tree in in-order.
* It will then display the visual of the tree.
* Next it will ask the user if they want to enter a value in the tree
* to delete.
* They can either enter 'd' to delete or 'x' to exit the program.
* Once the user enters 'd' they will insert an odd value to delete.
* It will delete the value, then traverse the tree.
* Then it will display the visual of the tree with '0' in place of the
* deleted value.
* This will loop until the user enters 'x'.
**********************************************************************/
int value;
Tree theTree = new Tree(); //tree object
//runs method insert() with numbers 1-7
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();
System.out.println("Displaying Tree:");
theTree.displayTree(); //runs method displayTree()
System.out.println();
System.out.println("Traversing...");
theTree.traverse(); //runs method traverse()
//This loop will run until the user enters 'x' to end the program
while (true)
{
//user instructions
System.out.println();
System.out.println();
System.out.print("Enter 'd' to find a value or " +
"'x' to exit the program: ");
int choice = getChar();
switch (choice) //switch statement for d or x
{
case 'd':
//Will ask the user to insert an odd number to delete
System.out.println();
System.out.print("Insert an odd number to delete: ");
value = getInt(); //runs method getInt()
theTree.delete(value); //runs method delete()
System.out.println();
System.out.println("Traversing...");
System.out.println();
theTree.traverse(); //runs method traverse()
System.out.println();
System.out.println();
System.out.println("Deleted values will be " +
"replaced by '0'");
System.out.println("Displaying Tree:");
theTree.displayTree(); //runs method displayTree()
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 program10;
/*************************
* 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 program10;
/*********************
* Tree Class
*********************/
public class Tree
{
private Node root; // the only data field in Tree
int numRuns;
//constructor
public Tree() {
root = null;
numRuns = 0;
}
//method insert
public void insert(int v) {
/**************************************************
* This method will insert a node into the tree.
* It will follow the standard binary tree rule.
* 4, will be the root.
* 2, will be the left child
* 4, will be the right child
* 1, will be the left of the left child
* 3, will be the right of the left child
* 5, will be the left of the right child
* 7, will be the right of the right child
******************************************************/
Node newNode = new Node();
newNode.value = v;
Node current = root;
switch (numRuns)
{
case 0:
root = newNode;
numRuns = 1;
return;
case 1:
current.left = newNode;
numRuns = 2;
return;
case 2:
current.right = newNode;
numRuns = 3;
return;
case 3:
current.left.left = newNode;
numRuns = 4;
return;
case 4:
current.left.right = newNode;
numRuns = 5;
return;
case 5:
current.right.left = newNode;
numRuns = 6;
return;
case 6:
current.right.right = newNode;
numRuns = 7;
return;
default:
System.out.println("Invalid");
break;
}
} // end insert
//method traverse
public void traverse() {
System.out.println();
inOrder(root); //runs method inOrder()
}
//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)
{
//not used in this program but find() is still part of most tree programs
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 boolean delete(int key)
{
//this method will delete an odd value from the tree
Node current = root;
Node parent = root;
boolean isLeft = true;
while(current.value != key) //search for node
{
parent = current;
if(key < current.value) //go left
{
isLeft=true;
current = current.left;
}
else //go right
{
isLeft = false;
current = current.right;
}
if (current == null) //end of the line
{
return false; //didn't find it
}
}//end while
//found node to delete
//if no children, delete it
if(current.left == null && current.right == null)
{
if (current == root) //if root
{
root = null; //tree is empty
}
else if(isLeft)
{
parent.left = null;
} //disconnect
else //from parent
{
parent.right = null;
}
}
//if no right child, replace with left subtree
else if (current.right == null)
{
if (current == root)
{
root = current.left;
}
else if (isLeft)
{
parent.left = current.left;
}
else
{
parent.right = current.left;
}
}
//if no left child, replace with right subree
else if(current.left == null)
{
if (current == root)
{
root = current.right;
}
else if (isLeft)
{
parent.left = current.right;
}
else
{
parent.right = current.right;
}
}
//two children, so replace with inorder successor
else
{
//get successor of node to delte (current)
Node successor = getSuccessor(current);
//connect parent of current to succesor instead
if (current == root)
{
root = successor;
}
else if (isLeft)
{
parent.left = successor;
}
else
{
parent.right = successor;
}
//connect successor to current's left child
successor.left = current.left;
} //end else with two children
//successor cannot have a left hcild
return true; //success
}//end delete
//method getSuccessor
private Node getSuccessor (Node delNode)
{
//returns node with next-highest value after delNode
//goes to right child, then right child's left descendents
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.right;
//go to right child until no more left children
while (current != null)
{
successorParent = successor;
successor = current;
current = current.left; //go to left child
}
//if successor not right child, make connection
if (successor != delNode.right)
{
successorParent.left = successor.right;
successor.right = delNode.right;
}
return successor;
}
public void displayTree()
{
//this will display the tree using System.out.print to make a visual
/*
The tree will look like this:
+------------------------------------------+
4
/ \
2 6
/ \ / \
1 3 5 7
+------------------------------------------+*/
//the if statements prevent an error if the value is null as well as
// change the value to 0 if it is null
int t = 0;
if (root != null)
{
t=root.value;
}
int t1 = 0;
if (root.left != null)
{
t1 = root.left.value;
}
int t2 = 0;
if (root.right != null)
{
t2 = root.right.value;
}
int t3 = 0;
if (root.left.left != null)
{
t3 = root.left.left.value;
}
int t4 = 0;
if (root.left.right != null)
{
t4 = root.left.right.value;
}
int t5 = 0;
if (root.right.left != null)
{
t5 = root.right.left.value;
}
int t6 = 0;
if (root.right.right != null)
{
t6 = root.right.right.value;
}
//the visual
System.out.println();
System.out.println("+------------------------------------------+");
System.out.println(" "+t+" ");
System.out.println(" / \\ ");
System.out.println(" "+t1+" "+t2+" ");
System.out.println(" / \\ / \\ ");
System.out.println(" "+t3+" "+t4+" "+t5+" "+t6+" ");
System.out.println("+------------------------------------------+");
System.out.println("");
//you must use \\ because '\' is an escape character
}
}
No comments:
Post a Comment