public class BinarySortTree {

    public Node root;
    
    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] arrays = {12,1,33,21,14,27,13,16,23,29,25};
        BinarySortTree tree = new BinarySortTree();
        for (int i = 0; i < arrays.length; i++) {
            tree.put(arrays[i]);
        }
        tree.deleteNode(21);
        tree.deleteNode(23);
        tree.middleTraversal(tree.getRoot());
    }
    
    private void deleteNode(int data){
        if(root != null){
            Node searchNode = searchNode(data);
            if(searchNode != null){
                if(searchNode.leftNode == null && searchNode.rightNode == null){
                    // 要刪除的節(jié)點是葉子節(jié)點
                    Node parent = searchNode.parent;
                    if(parent.leftNode == searchNode){
                        // 要刪除的節(jié)點在他父節(jié)點的左邊
                        parent.leftNode = null;
                    }else if(parent.rightNode == searchNode){
                        // 要刪除的節(jié)點在他父節(jié)點的右邊
                        parent.rightNode = null;
                    }
                    searchNode.parent = null;
                }else if(searchNode.leftNode != null && searchNode.rightNode == null){
                    // 要刪除的節(jié)點有左節(jié)點沒有右節(jié)點，先判斷要刪除的節(jié)點在他父節(jié)點的左邊還是右邊
                    Node parent = searchNode.parent;
                    if(parent.leftNode == searchNode){
                        parent.leftNode = searchNode.leftNode;
                    }else if(parent.rightNode == searchNode){
                        parent.rightNode = searchNode.leftNode;
                    }
                    searchNode.leftNode.parent = parent;
                    searchNode.leftNode = null;
                    searchNode.rightNode = null;
                }else if(searchNode.leftNode == null && searchNode.rightNode != null){
                    // 要刪除的節(jié)點有右節(jié)點沒有左節(jié)點，先判斷要刪除的節(jié)點在他父節(jié)點的左邊還是右邊
                    Node parent = searchNode.parent;
                    if(parent.leftNode == searchNode){
                        parent.leftNode = searchNode.rightNode;
                    }else if(parent.rightNode == searchNode){
                        parent.rightNode = searchNode.rightNode;
                    }
                    searchNode.rightNode.parent = parent;
                    searchNode.leftNode = null;
                    searchNode.rightNode = null;
                }else if(searchNode.leftNode != null && searchNode.rightNode != null){
                    // 要刪除的節(jié)點左右都有節(jié)點，先判斷要刪除的節(jié)點在他父節(jié)點的左邊還是右邊
                    // 找到被刪除節(jié)點右子樹的最小節(jié)點掛到被刪的位置上
                    Node parent = searchNode.parent;
                    // 找右子樹的最小節(jié)點
                    Node smallestNode = searchNode.rightNode;
                    while(smallestNode.leftNode != null){
                        smallestNode = smallestNode.leftNode;
                    }
                    // 這個最小的節(jié)點如果存在右節(jié)點，把右節(jié)點放到該節(jié)點的位置
                    if(smallestNode.rightNode != null){
                        smallestNode.parent.leftNode = smallestNode.rightNode;
                        smallestNode.rightNode.parent = smallestNode.parent;
                    }else{
                        smallestNode.parent.leftNode = null;
                    }
                    smallestNode.leftNode = searchNode.leftNode;
                    searchNode.leftNode.parent = smallestNode;
                    
                    if(smallestNode != searchNode.rightNode){
                        smallestNode.rightNode = searchNode.rightNode;
                        searchNode.rightNode.parent = smallestNode;
                    }
                    
                    if(parent.leftNode == searchNode){ // 在左邊
                        parent.leftNode = smallestNode;
                    }else if(parent.rightNode == searchNode){ // 在右邊
                        parent.rightNode = smallestNode;
                    }
                    smallestNode.parent = parent;
                    searchNode.leftNode = null;
                    searchNode.rightNode = null;
                    searchNode.parent = null;
                }
            }
        }
    }
    
    private static void middleTraversal(Node root){
        if(root == null){
            return ;
        }
        middleTraversal(root.leftNode);
        System.out.println(root.data);
        middleTraversal(root.rightNode);
    }
    
    private Node searchNode(int data){
        if(root != null){
            Node currentNode = root;
            while(currentNode != null){
                if(data == currentNode.data){
                    return currentNode;
                }else if(data < currentNode.data){
                    currentNode = currentNode.leftNode;
                }else if(data > currentNode.data){
                    currentNode = currentNode.rightNode;
                }
            }
        }
        return null;
    }
    
    private Node put(int data){
        if(root == null){
            Node node = new Node(data);
            root = node;
            return node;
        }
        Node currentNode = root;
        while(currentNode!= null){
            if(data == currentNode.data){
                break;
            }else if(data < currentNode.data){
                if(currentNode.leftNode == null){
                    // 直接在左邊添加新的節(jié)點
                    Node newNode = new Node(data);
                    currentNode.leftNode = newNode;
                    newNode.parent = currentNode;
                    break;
                }else{
                    currentNode = currentNode.leftNode;
                }
            }else if(data > currentNode.data){
                if(currentNode.rightNode == null){
                    // 直接在右邊添加新的節(jié)點
                    Node newNode = new Node(data);
                    currentNode.rightNode = newNode;
                    newNode.parent = currentNode;
                    break;
                }else{
                    currentNode = currentNode.rightNode;
                }
            }
            
        }
        return root;
    }
    
    static class Node{
        public int data;
        public Node leftNode;
        public Node rightNode;
        public Node parent;
        
        public Node(int data){
            this.data = data;
        }
    }

    public Node getRoot(){
        return root;
    }
}