Binary Search Tree
public class BinarySearchTree {
public static Node root;
public BinarySearchTree(){
this.root = null;
}
public boolean find(int id){
Node current = root;
while(current!=null){
if(current.data==id){
return true;
}else if(current.data>id){
current = current.left;
}else{
current = current.right;
}
}
return false;
}
public boolean delete(int id){
Node parent = root;
Node current = root;
boolean isLeftChild = false;
while(current.data!=id){
parent = current;
if(current.data>id){
isLeftChild = true;
current = current.left;
}else{
isLeftChild = false;
current = current.right;
}
if(current ==null){
return false;
}
}
//if i am here that means we have found the node
//Case 1: if node to be deleted has no children
if(current.left==null && current.right==null){
if(current==root){
root = null;
}
else if(isLeftChild ==true){
parent.left = null;
}else{
parent.right = null;
}
}
//Case 2 : if node to be deleted has only one child
else if(current.right==null){
if(current==root){
root = current.left;
}else if(isLeftChild){
parent.left = current.left;
}else{
parent.right = current.left;
}
}
else if(current.left==null){
if(current==root){
root = current.right;
}else if(isLeftChild){
parent.left = current.right;
}else{
parent.right = current.right;
}
}else if(current.left!=null && current.right!=null){
//now we have found the minimum element in the right sub tree
Node successor = getSuccessor(current);
if(current==root){
root = successor;
}else if(isLeftChild){
parent.left = successor;
}else{
parent.right = successor;
}
successor.left = current.left;
}
return true;
}
public Node getSuccessor(Node deleleNode){
Node successsor =null;
Node successsorParent =null;
Node current = deleleNode.right;
while(current!=null){
successsorParent = successsor;
successsor = current;
current = current.left;
}
//check if successor has the right child, it cannot have left child for sure
// if it does have the right child, add it to the left of successorParent.
// successsorParent 先把successor父亲的左节点连到successor的右节点，然后successor的右节点变为delete的右节点
if(successsor!=deleleNode.right){
successsorParent.left = successsor.right;
successsor.right = deleleNode.right;
}
return successsor;
}
public void insert(int id){
Node newNode = new Node(id);
if(root==null){
root = newNode;
return;
}
Node current = root;
Node parent = root;
while(true){
parent = current;
if(id<current.data){
current = current.left;
if(current==null){
parent.left = newNode;
return;
}
}else{
current = current.right;
if(current==null){
parent.right = newNode;
return;
}
}
}
}
public void display(Node root){
if(root!=null){
display(root.left);
System.out.print(" " + root.data);
display(root.right);
}
}
public static void main(String arg[]){
BinarySearchTree b = new BinarySearchTree();
b.insert(3);b.insert(8);
b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(10);b.insert(9);
b.insert(20);b.insert(25);b.insert(15);b.insert(16);
System.out.println("Original Tree : ");
b.display(b.root);
System.out.println("");
System.out.println("Check whether Node with value 4 exists : " + b.find(4));
System.out.println("Delete Node with no children (2) : " + b.delete(2));
b.display(root);
System.out.println("\n Delete Node with one child (4) : " + b.delete(4));
b.display(root);
System.out.println("\n Delete Node with Two children (10) : " + b.delete(10));
b.display(root);
}
}
class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
left = null;
right = null;
}
}
我自己的做法
class Node{
int id;
Node left;
Node right;
public Node(int id){
this.id = id;
}
}
public class Bst {
public static Node root;
public Bst(){
this.root = null;
}
public boolean insert(int id){
if(root == null){
root = new Node(id);
return true;
}
Node current = root;
Node parent = null;
while(current.id != id){
parent = current;
if(current.id > id){
current = current.left;
if(current == null){
parent.left = new Node(id);
return true;
}
}else{
current = current.right;
if(current == null){
parent.right = new Node(id);
return true;
}
}
}
return false;
}
public boolean find(int id){
Node current = root;
while(current != null){
if(current.id == id){
return true;
}else if(current.id > id){
current = current.left;
}else{
current = current.right;
}
}
return false;
}
public boolean delete(int id){
if(root == null) return true;
Node current = root;
Node parent = null;
boolean isLeftChild = false;
while(current.id != id){
parent = current;
if(current.id > id){
isLeftChild = true;
current = current.left;
}else{
isLeftChild = false;
current = current.right;
}
if(current == null){
return false;
}
}
//case 1: no child
if(current.right == null && current.left == null){
if(current == root){
root = null;
return true;
}else{
root.id = current.id;
if( isLeftChild){
parent.left = null;
}else{
parent.right = null;
}
}
}
//case 2: only one child
if(current.right == null){
if( isLeftChild){
parent.left = current.left;
}else{
parent.right = current.left;
}
return true;
}
if(current.left == null){
if( isLeftChild){
parent.left = current.right;
}else{
parent.right = current.right;
}
}
//find minimum of right subtree
//case 3 has right subtree, try to find minimum of right subree
Node nextNode = current.right;
Node nextNodeParent = current;
while(nextNode.left != null){
nextNodeParent = nextNode;
nextNode = nextNode.left;
}
//case 3a right subtree doesn't have left subtree
if(nextNodeParent == current){
if(parent == null){
nextNode.left = current.left;
root = nextNode;
}else if(isLeftChild){
parent.left = nextNode;
nextNode.left = current.left;
}else{
parent.right = nextNode;
nextNode.left = current.left;
}
return true;
}
//case 3b find item, delete that item and repoint that item and then make target node val equal this item
nextNodeParent.left = nextNode.right;
int val = nextNode.id;
current.id = val;
return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Bst b = new Bst();
b.insert(3);
b.insert(6);
b.insert(1);b.insert(8);b.insert(2);b.insert(10);b.insert(9);
b.insert(20);b.insert(25);b.insert(15);b.insert(16);
b.delete(3);
System.out.println(b.root.id);
}
}