public class BinaryTreeNode {

    private int id;
    private double data;// other data
    BinaryTreeNode leftChild;
    BinaryTreeNode rightChild;

    public BinaryTreeNode(int id, double data, BinaryTreeNode leftChild,
            BinaryTreeNode rightChild) {
        super();
        this.id = id;
        this.data = data;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public double getData() {
        return data;
    }

    public void setData(double data) {
        this.data = data;
    }

    public BinaryTreeNode getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(BinaryTreeNode leftChild) {
        this.leftChild = leftChild;
    }

    public BinaryTreeNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(BinaryTreeNode rightChild) {
        this.rightChild = rightChild;
    }

}

public class BinaryTree {

    private BinaryTreeNode root;

        //查找
    public BinaryTreeNode find(int id) {
        BinaryTreeNode current = root;
        while (id != current.getId()) {
            if (id < current.getId()) {
                current = current.getLeftChild();
            } else {
                current = current.getRightChild();
            }
            if (current == null)
                return null;
        }
        return current;
    }

        //插入
    public void insert(BinaryTreeNode node) {
        if (this.root == null) {
            this.root = node;
        } else {
            BinaryTreeNode current = root;
            BinaryTreeNode parent;
            while (true) {
                parent = current;
                if (node.getId() < parent.getId()) {
                    // go left
                    current = current.getLeftChild();
                    if (current == null) {
                        parent.setLeftChild(node);
                        return;
                    }
                } else {
                    // go right
                    current = current.getRightChild();
                    if (current == null) {
                        parent.setRightChild(node);
                        return;
                    }
                }
            }
        }
    }

        //删除
    public boolean delete(int key) {
        BinaryTreeNode current = root;
        BinaryTreeNode parent = root;
        boolean isLeftChild = true;

        while (current.getId() != key) {
            parent = current;
            if (key < current.getId()) {
                isLeftChild = true;
                current = current.getLeftChild();
            } else {
                isLeftChild = false;
                current = current.getRightChild();
            }
            if (current == null)
                return false;
        }
        // 叶子节点
        if (current.getLeftChild() == null && current.getRightChild() == null) {
            if (current == root)
                root = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
            // 只有一个子节点
        } else if (current.getRightChild() == null) {
            if (current == root)
                root = current.getLeftChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getLeftChild());
            else
                parent.setRightChild(current.getLeftChild());
        } else if (current.getLeftChild() == null) {
            if (current == root) {
                root = current.getRightChild();
            }

            else if (isLeftChild) {
                parent.setLeftChild(current.getRightChild());
            }

            else {
                parent.setRightChild(current.getRightChild()); 
            }

        }
        // 两个子节点
        else {
            BinaryTreeNode successor = getSuccessor(current);

            // 步骤三
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.setLeftChild(successor);
            } else
                parent.setRightChild(successor);

            // 步骤四
            successor.setLeftChild(current.getLeftChild()); 

        }

        return true;
    }

        //查找节点的后继节点
    private BinaryTreeNode getSuccessor(BinaryTreeNode delNode) {
        BinaryTreeNode successorParent = delNode;
        BinaryTreeNode successor = delNode;
        BinaryTreeNode current = delNode.getRightChild();

        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.getLeftChild();
        }
        if (successor != delNode.getRightChild()) {

            // 步骤一
            successorParent.setLeftChild(successor.getRightChild());

            // 步骤二
            successor.setRightChild(successor.getRightChild());
        }
        return successor;
    }
}