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){
                    // 要删除的节点是叶子节点
                    Node parent = searchNode.parent;
                    if(parent.leftNode == searchNode){
                        // 要删除的节点在他父节点的左边
                        parent.leftNode = null;
                    }else if(parent.rightNode == searchNode){
                        // 要删除的节点在他父节点的右边
                        parent.rightNode = null;
                    }
                    searchNode.parent = null;
                }else if(searchNode.leftNode != null && searchNode.rightNode == null){
                    // 要删除的节点有左节点没有右节点，先判断要删除的节点在他父节点的左边还是右边
                    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){
                    // 要删除的节点有右节点没有左节点，先判断要删除的节点在他父节点的左边还是右边
                    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){
                    // 要删除的节点左右都有节点，先判断要删除的节点在他父节点的左边还是右边
                    // 找到被删除节点右子树的最小节点挂到被删的位置上
                    Node parent = searchNode.parent;
                    // 找右子树的最小节点
                    Node smallestNode = searchNode.rightNode;
                    while(smallestNode.leftNode != null){
                        smallestNode = smallestNode.leftNode;
                    }
                    // 这个最小的节点如果存在右节点，把右节点放到该节点的位置
                    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){
                    // 直接在左边添加新的节点
                    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){
                    // 直接在右边添加新的节点
                    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;
    }
}