/**

* This entire class is used to build a Binary Tree data structure.

* There is the Node Class and the Tree Class, both explained below.

*

* @author Unknown

*

*/

/**

* This class implements the nodes that will go on the Binary Tree.

* They consist of the data in them, the node to the left, the node

* to the right, and the parent from which they came from.

*

* @author Unknown

*

*/

class Node{

/** Data for the node */

public int data;

/** The Node to the left of this one */

public Node left;

/** The Node to the right of this one */

public Node right;

/** The parent of this node */

public Node parent;

/**

* Constructor of Node

*

* @param value Value to put in the node

*/

public Node(int value){

data = value;

left = null;

right = null;

parent = null;

}

}

/**

* A binary tree is a data structure in which an element

* has two successors(children). The left child is usually

* smaller than the parent, and the right child is usually

* bigger.

*

* @author Unknown

*

*/

class Tree{

/** The root of the Binary Tree */

private Node root;

/**

* Constructor

*/

public Tree(){

root = null;

}

/**

* Method to find a Node with a certain value

*

* @param key Value being looked for

* @return The node if it finds it, otherwise returns the parent

*/

public Node find(int key) {

Node current = root;

while (current != null) {

if(key < current.data) {

if(current.left == null)

return current; //The key isn't exist, returns the parent

current = current.left;

} else if(key > current.data) {

if(current.right == null)

return current;

current = current.right;

} else { // If you find the value return it

return current;

}

}

return null;

}

/**

* Inserts certain value into the Binary Tree

*

* @param value Value to be inserted

*/

public void put(int value){

Node newNode = new Node(value);

if(root == null)

root = newNode;

else{

//This will return the soon to be parent of the value you're inserting

Node parent = find(value);

//This if/else assigns the new node to be either the left or right child of the parent

if(value < parent.data){

parent.left = newNode;

parent.left.parent = parent;

return;

}

else{

parent.right = newNode;

parent.right.parent = parent;

return;

}

}

}

/**

* Deletes a given value from the Binary Tree

*

* @param value Value to be deleted

* @return If the value was deleted

*/

public boolean remove(int value){

//temp is the node to be deleted

Node temp = find(value);

//If the value doesn't exist

if(temp.data != value)

return false;

//No children

if(temp.right == null && temp.left == null){

if(temp == root)

root = null;

//This if/else assigns the new node to be either the left or right child of the parent

else if(temp.parent.data < temp.data)

temp.parent.right = null;

else

temp.parent.left = null;

return true;

}

//Two children

else if(temp.left != null && temp.right != null){

Node successor = findSuccessor(temp);

//The left tree of temp is made the left tree of the successor

successor.left = temp.left;

successor.left.parent = successor;

//If the successor has a right child, the child's grandparent is it's new parent

if(successor.right != null && successor.parent != temp){

successor.right.parent = successor.parent;

successor.parent.left = successor.right;

successor.right = temp.right;

successor.right.parent = successor;

}

if(temp == root){

successor.parent = null;

root = successor;

return true;

}

//If you're not deleting the root

else{

successor.parent = temp.parent;

//This if/else assigns the new node to be either the left or right child of the parent

if(temp.parent.data < temp.data)

temp.parent.right = successor;

else

temp.parent.left = successor;

return true;

}

}

//One child

else{

//If it has a right child

if(temp.right != null){

if(temp == root){

root = temp.right; return true;}

temp.right.parent = temp.parent;

//Assigns temp to left or right child

if(temp.data < temp.parent.data)

temp.parent.left = temp.right;

else

temp.parent.right = temp.right;

return true;

}

//If it has a left child

else{

if(temp == root){

root = temp.left; return true;}

temp.left.parent = temp.parent;

//Assigns temp to left or right side

if(temp.data < temp.parent.data)

temp.parent.left = temp.left;

else

temp.parent.right = temp.left;

return true;

}

}

}

/**

* This method finds the Successor to the Node given.

* Move right once and go left down the tree as far as you can

*

* @param n Node that you want to find the Successor of

* @return The Successor of the node

*/

public Node findSuccessor(Node n){

if(n.right == null)

return n;

Node current = n.right;

Node parent = n.right;

while(current != null){

parent = current;

current = current.left;

}

return parent;

}

/**

* Returns the root of the Binary Tree

*

* @return the root of the Binary Tree

*/

public Node getRoot(){

return root;

}

/**

* Prints leftChild - root - rightChild

*

* @param localRoot The local root of the binary tree

*/

public void inOrder(Node localRoot){

if(localRoot != null){

inOrder(localRoot.left);

System.out.print(localRoot.data + " ");

inOrder(localRoot.right);

}

}

/**

* Prints root - leftChild - rightChild

*

* @param localRoot The local root of the binary tree

*/

public void preOrder(Node localRoot){

if(localRoot != null){

System.out.print(localRoot.data + " ");

preOrder(localRoot.left);

preOrder(localRoot.right);

}

}

/**

* Prints rightChild - leftChild - root

*

* @param localRoot The local root of the binary tree

*/

public void postOrder(Node localRoot){

if(localRoot != null){

postOrder(localRoot.left);

postOrder(localRoot.right);

System.out.print(localRoot.data + " ");

}

}

}