心里有点树 （三）

// tree
public class BinarySortTree {
    Node root;
}
// node
public class Node {
    private int value;
    private Node leftNode;
    private Node rightNode;
}

-----------BinarySortTree.class--------------- 
/**
     * 向二叉排序树中添加节点
     */
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }
-------------Node.class------------
/**
     * 添加节点
     *
     * @param node
     */
    public void add(Node node) {
        if (node == null)
            return;
        //判断需要添加的节点的值比传递进来的节点的值大还是小
        // 添加的节点小于当前节点的值
        if (node.value < this.value) {
            if (this.leftNode == null) {
                this.leftNode = node;
            } else {
                this.leftNode.add(node);
            }
        } else {
            if (this.rightNode == null) {
                this.rightNode = node;
            } else {
                this.rightNode.add(node);
            }
        }
    }

/**
     * 删除一个节点
     *
     * @param value
     * @return
     */
    public void delete(int value) {
        if (root == null) {
            return;
        } else {
            // 找到这个节点
            Node node = midleSearch(value);
            if (node == null)
                return;
            // 找到他的父节点
            Node parentNode = searchParent(value);
            // todo 当前节点是叶子节点
            if (node.getLeftNode() == null && node.getRightNode() == null) {
                if (parentNode.getLeftNode().getValue() == value) {
                    parentNode.setLeftNode(null);
                } else {
                    parentNode.setRightNode(null);
                }
                // todo 要删除的节点存在两个子节点
            } else if (node.getLeftNode() != null && node.getRightNode() != null) {
                // 假设就是删除7
                //1. 找到右子树中最小的节点,保存它的值,然后删除他
                int minValue = deleteMin(node.getRightNode());
                //2.替换被删除的节点值
                node.setValue(minValue);
            } else { // todo 要删除的节点有一个左子节点或者是右子节点
                // 左边有节点
                if (node.getLeftNode() != null) {
                    // 要删除的节点是父节点的左节点
                    if (parentNode.getLeftNode().getValue() == value) {
                        parentNode.setLeftNode(node.getLeftNode());
                    } else {// 要删除的节点是父节点的右节点
                        parentNode.setRightNode(node.getLeftNode());
                    }
                } else { // 右边有节点
                    // 要删除的节点是父节点的右节点
                    if (parentNode.getLeftNode().getValue() == value) {
                        parentNode.setLeftNode(node.getRightNode());
                    } else {// 要删除的节点是父节点的右节点
                        parentNode.setRightNode(node.getRightNode());
                    }
                }
            }
        }
    }
 /**
     * 删除并保存以当前点为根节点的树的最小值节点
     * @param node
     * @return
     */
    private int deleteMin(Node node) {
        // 情况1: 值最小的节点没有右节点
        // 情况2: 值最小的节点存在右节点
        // 但是下面我们使用delete,原来考虑到了
        while(node.getLeftNode()!=null){
            node=node.getLeftNode();
        }
        delete(node.getValue());
        return node.getValue();
    }
    /**
     * 搜索父节点
     *
     * @param value
     * @return
     */
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }