public class BST {
public static void main(String[] args) {
Tree myBst = new Tree();
Node one = new Node(1);
Node six = new Node(6);
Node three = new Node(3);
Node five = new Node(5);
Node two = new Node(2);
myBst.insert(one);
myBst.insert(six);
myBst.insert(three);
myBst.insert(five);
myBst.insert(two);
myBst.preOrderTraversal(myBst.root);
System.out.println("-----------------");
myBst.remove(3);
myBst.preOrderTraversal(myBst.root);
}
}
class Node {
Node leftChild;
Node rightChild;
int value;
Node(int i) {
this.value = i;
}
public boolean remove(int value, Node parent) {
if (value < this.value) {//not found, keep left search
if (leftChild != null)
return leftChild.remove(value, this);
else
return false;
} else if (value > this.value) {//not found , keep right search.
if (rightChild != null)
return rightChild.remove(value, this);
else
return false;
} else {//found
if (leftChild != null && rightChild != null) {//two leafs case
this.value = rightChild.minValue();
rightChild.remove(this.value, this);
} else if (parent.leftChild == this) {//left node is the only one child node
parent.leftChild = (leftChild != null) ? leftChild : rightChild;
} else if (parent.rightChild == this) {//right node is the only one child node
parent.rightChild = (leftChild != null) ? leftChild : rightChild;
}
return true;
}
}
/*
* The minimum value of a tree is always located in the left sub tree,
* so recursively search from left subtree.
*/
public int minValue() {
if (leftChild == null)
return value;
else
return leftChild.minValue();
}
}
class Tree {
Node root;
public void insert(Node node) {
if (root == null) {
root = node;
} else {
Node temp = root;
while (temp != null) {
if (node.value >= temp.value) {
if (temp.rightChild == null) {
temp.rightChild = node;
break;
} else {
temp = temp.rightChild;
}
} else {
if (temp.leftChild == null) {
temp.leftChild = node;
break;
} else {
temp = temp.leftChild;
}
}
}
}
}
public boolean remove(int value) {
if (root == null)
return false;
else {
if (root.value == value) {
Node auxRoot = new Node(0);
auxRoot.leftChild = root;
boolean result = root.remove(value, auxRoot);
root = auxRoot.leftChild;
return result;
} else {
return root.remove(value, null);
}
}
}
public void preOrderTraversal(Node root) {
System.out.println(root.value);
if (root.leftChild != null) {
preOrderTraversal(root.leftChild);
}
if (root.rightChild != null) {
preOrderTraversal(root.rightChild);
}
}
}
BST with c++
