package program11;
import java.io.*;
public class Main
{
// Program #11
// Zach Krizan
// Data Structures
public static void main(String[] args) throws IOException {
/*********************************************************************
* This program will demonstrate deleting from a tree with one child.
* 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.
* It will display a message and delete value 7.
* Then it will traverse the tree and display the tree.
* Next it will display a message and delete value 6.
* Then it will traverse the tree and display the tree.
* Next it will display a message and delete value 1.
* Then it will traverse the tree and display the tree.
* Next it will display a message and delete value 2.
* Then it will traverse the tree and display the tree.
* When it displays the the visual of the tree, it will use a'0' in
* place of the deleted 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("Displaying Tree:");
theTree.displayTree(); //runs method displayTree()
System.out.println("Traversing...");
theTree.traverse(); //runs method traverse()
/*************************************
* Deleting Value 7
**************************************/
System.out.println();
System.out.println();
System.out.println("+-----------------------------+");
System.out.println("Deleting value '7'...");
System.out.println("+-----------------------------+");
theTree.delete(7); //runs method delete()
System.out.println();
System.out.println("Traversing...");
theTree.traverse(); //runs method traverse()
System.out.println();
System.out.println();
System.out.println("Deleted values will be " +
"replaced by '0'");
System.out.println();
System.out.println("Displaying Tree:");
theTree.displayTree(); //runs method displayTree()
/*************************************
* Deleting Value 6
**************************************/
System.out.println();
System.out.println("+-----------------------------+");
System.out.println("Deleting value '6'...");
System.out.println("+-----------------------------+");
theTree.delete(6); //runs method delete()
System.out.println();
System.out.println("Traversing...");
theTree.traverse(); //runs method traverse()
System.out.println();
System.out.println();
System.out.println("Deleted values will be " +
"replaced by '0'");
System.out.println();
System.out.println("Displaying Tree:");
theTree.displayTree(); //runs method displayTree()
/*************************************
* Deleting Value 1
**************************************/
System.out.println();
System.out.println("+-----------------------------+");
System.out.println("Deleting value '1'...");
System.out.println("+-----------------------------+");
theTree.delete(1); //runs method delete()
System.out.println();
System.out.println("Traversing...");
theTree.traverse(); //runs method traverse()
System.out.println();
System.out.println();
System.out.println("Deleted values will be " +
"replaced by '0'");
System.out.println();
System.out.println("Displaying Tree:");
theTree.displayTree(); //runs method displayTree()
/*************************************
* Deleting Value 2
**************************************/
System.out.println();
System.out.println("+-----------------------------+");
System.out.println("Deleting value '2'...");
System.out.println("+-----------------------------+");
theTree.delete(2); //runs method delete()
System.out.println();
System.out.println("Traversing...");
theTree.traverse(); //runs method traverse()
System.out.println();
System.out.println();
System.out.println("Deleted values will be " +
"replaced by '0'");
System.out.println();
System.out.println("Displaying Tree:");
theTree.displayTree(); //runs method displayTree()
System.out.println("Program will now end");
System.exit(0);
} //end main
} //end Main
/********************************
*
* Page 2
*
*********************************/
/*************************
* 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
*
*********************************/
/*********************
* 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