二叉排序树

二叉排序树（也叫二叉搜索树、查找树）。

具有如下特点：

或者是一颗空树，或者是一颗具有如下性质的树：
 1）若左子树不为空，那么左子树上面的所有节点的关键字值都比根节点的关键字值小
 2）若右子树不为空，那么右子树上面的所有节点的关键字值都比根节点的关键字值大
 3）左右子树都为二叉树
 4）没有重复值

代码实践

1、树的表示形式：孩子表示法

    /**
     * 树中的节点
     */
    public static class TreeNode {
        int data;          //本例中以 int 型数据为例
        TreeNode leftChild;
        TreeNode rightChild;
        TreeNode parent;
        
        public TreeNode(int data) {
            this.data = data;
        }
    }

2、添加结点

    /**
     * 添加节点
     */
    public TreeNode put(int data) {
        if (root == null) {  //空树
            TreeNode node = new TreeNode(data);
            root = node;
            return node;
        }

        TreeNode node = root;
        TreeNode parent = null;
        while (node != null) {
            parent = node;
            if (data < node.data) {
                node = node.leftChild;
            } else if (data > node.data) {
                node = node.rightChild;
            } else {  // 插入节点重复，直接返回
                return node;
            }
        }

        TreeNode newNode = new TreeNode(data);
        if (data < parent.data) {
            parent.leftChild = newNode;
        } else {
            parent.rightChild = newNode;
        }
        //切记别忘了（有点类似于双向链表的那种）
        newNode.parent = parent;

        return newNode;
    }

3、树的遍历（中序LCR）

1、递归形式

    
    /**
     * 中序遍历
     */
    public void midOrderTraverse(TreeNode root) {
        if (root == null) {
            return;
        }

        //LDR
        midOrderTraverse(root.leftChild);
        System.out.printf(root.data + " ");
        midOrderTraverse(root.rightChild);
    }

2、非递归形式

    /**
     * 中序遍历 非递归形式
     */
    public void midOrderTraverse(TreeNode root){
        if (root == null) return;

        /**
         * Stack 出站的顺序即 中序遍历 的顺序
         */
        Stack stack = new Stack();

        TreeNode target = root;
        while (target != null){
            stack.push(target);
            target = target.leftChild;
        }

        while (!stack.isEmpty()){
            TreeNode node = (TreeNode) stack.pop();

            System.out.print(node.data + " ");

            TreeNode tmp = node.rightChild;
            while (tmp != null){
                stack.push(tmp);
                tmp = tmp.leftChild;
            }
        }
    }

4、查找结点

    /**
     * 查找一个节点
     */
    public TreeNode searchNode(int data) {
        if (root == null) {
            return null;
        }
        TreeNode node = root;
        while (node != null) {
            if (node.data == data) {
                return node;
            } else if (data > node.data) {
                node = node.rightChild;
            } else if (data < node.data) {
                node = node.leftChild;
            }
        }
        return null;
    }

5、删除节点（难点）

删除节点时，所有可能出现的情况：

image.png

1、一种比较精简的实现方式：

    /**
     * 删除一个结点：参考TreeMap的方式，值赋值，效率高。
     * <p>
     * 这样的代码写起来精简，稍微不易读。每种条件判断排列组合以后，覆盖了所有情况。
     *
     * @param p 要删除的节点。
     *             使用 ：
     *             TreeNode node = searchNode(3);
     *             tree.delNode(node);
     */
    public void delNode(TreeNode p) {
        if(p == null) throw new NoSuchElementException();

        //左右孩子都存在的情况
        if (p.leftChild != null && p.rightChild != null) {
            TreeNode s = successor(p);
            p.data = s.data;
            p = s;
        }

        TreeNode replacement = p.leftChild != null ? p.leftChild : p.rightChild;
        if (replacement != null) {
            replacement.parent = p.parent;

            if(p.parent == null){
                root = replacement;
            } else if (p.parent.leftChild == p) {
                p.parent.leftChild = replacement;
            } else if (p.parent.rightChild == p) {
                p.parent.rightChild = replacement;
            }

            //注意这样写法
            p.leftChild = p.rightChild = p.parent = null;

        } else if (p.parent == null) {
            root = null;
        } else {
            if (p.parent.leftChild == p) {
                p.parent.leftChild = null;
            } else {
                p.parent.rightChild = null;
            }
        }

    }

    //寻找一个节点的后继节点
    private TreeNode successor(TreeNode t) {
        if (t == null) {
            return null;
        } else if (t.rightChild != null) {
            TreeNode p = t.rightChild;
            while (p.leftChild != null) {
                p = p.leftChild;
            }
            return p;
        } else {
            TreeNode p = t.parent;
            TreeNode ch = t;
            while (p != null && ch == p.rightChild) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

2、引用赋值（代码复杂，思路简单）

/**
     * 删除一个结点：注意各个指针之间的关系，没用的指针及时废掉。
     *
     * @param node 要删除的节点。
     *             使用 ：
     *             TreeNode node = searchNode(3);
     *             tree.delNode(node);
     */
    public void delNode(TreeNode node) {
        if (node == null) {
            throw new NoSuchElementException();
        } else {
            //先得到父节点，方便后边的操作
            TreeNode parent = node.parent;
            if (node.leftChild == null && node.rightChild == null) {   //1、如果node是叶子节点
                if (parent == null) {    //根节点
                    root = null;
                } else if (parent.leftChild == node) { //是某一个节点的左节点
                    parent.leftChild = null;
                } else if (parent.rightChild == node) {// 是某一个节点的右节点
                    parent.rightChild = null;
                }
                node.parent = null;
            } else if (node.leftChild != null && node.rightChild == null) { //2、node只有左子树
                if (parent == null) { //根节点
                    root = node.leftChild;
                    node.leftChild = null;  //断开连接
                    root.parent = null; //注意，因为root的parent为空，如果不设置会出问题
                } else {
                    if (parent.leftChild == node) {   //要删除的节点是父亲的左节点
                        parent.leftChild = node.leftChild;
                        node.leftChild.parent = parent;
                    } else {  //要删除的节点是父亲的右节点
                        parent.rightChild = node.leftChild;
                        node.leftChild.parent = parent;
                    }
                    node.leftChild = null;
                    node.parent = null;
                }
            } else if (node.leftChild == null && node.rightChild != null) { //3、node只有右子树
                if (parent == null) {
                    root = node.rightChild;
                    node.rightChild = null;
                    root.parent = null; //注意，因为root的parent为空，如果不设置会出问题
                } else {
                    if (parent.leftChild == node) {   //要删除的节点是父亲的左节点
                        parent.leftChild = node.rightChild;
                        node.rightChild.parent = parent;
                    } else if (parent.rightChild == node) { //要删除的节点是父亲的右节点
                        parent.rightChild = node.rightChild;
                        node.rightChild.parent = parent;
                    }
                    node.rightChild = null;
                    node.parent = null;
                }
            } else if (node.leftChild != null && node.rightChild != null) {//4、有左右两个孩子
                if (node.rightChild.leftChild == null) { //如果被删除节点的右孩子节点的左子树为空，则直接补上右孩子节点
                    if (parent == null) {    //要删除的是根节点
                        root = node.rightChild;
                        node.rightChild.leftChild = node.leftChild;
                        node.leftChild.parent = node.rightChild;

                        node.leftChild = null;
                        node.rightChild = null;
                        root.parent = null; //尽管只移动了root指针，此时要记得置空
                    } else {
                        if (parent.leftChild == node) {  //要删除的节点是父节点的左节点
                            parent.leftChild = node.rightChild;
                            node.rightChild.parent = parent;

                            node.rightChild.leftChild = node.leftChild;
                            node.leftChild.parent = node.rightChild;

                        } else {//要删除的节点是父节点的右节点
                            parent.rightChild = node.rightChild;
                            node.rightChild.parent = parent;

                            node.rightChild.leftChild = node.leftChild;
                            node.leftChild.parent = node.rightChild;
                        }

                        node.leftChild = null;
                        node.rightChild = null;
                        node.parent = null;
                    }
                } else { //如果被删除节点的右孩子节点的左子树不为空，则补上左子树中最小的一个
                    TreeNode minLeftNode = getMinLeftTreeNode(node.rightChild);

                    //处理好最左侧节点的事情
                    minLeftNode.parent.leftChild = minLeftNode.rightChild;
                    if (minLeftNode.rightChild != null) {
                        minLeftNode.rightChild.parent = minLeftNode.parent;
                    }

                    //设置移动节点 的左孩子
                    minLeftNode.leftChild = node.leftChild;
                    node.leftChild.parent = minLeftNode;

                    //设置移动节点 的右孩子
                    minLeftNode.rightChild = node.rightChild;
                    node.rightChild.parent = minLeftNode;

                    if (parent == null) {//要删除的节点是根节点
                        //设置为根节点
                        root = minLeftNode;
                        root.parent = null;
                    } else {
                        if (parent.leftChild == node) {   //要删除的节点是自己父亲节点的左节点
                            parent.leftChild = minLeftNode;
                            minLeftNode.parent = parent;
                        } else { //要删除的节点是自己父亲节点的右节点
                            parent.rightChild = minLeftNode;
                            minLeftNode.parent = parent;
                        }
                    }

                    node.leftChild = null;
                    node.rightChild = null;
                    node.parent = null;
                }
            }
        }
    }

    /**
     * 获取一个二叉排序树中最小的节点
     */
    private TreeNode getMinLeftTreeNode(TreeNode node) {
        if (node == null) {
            return null;
        } else {
            TreeNode curNode = node;
            while (curNode.leftChild != null) {
                curNode = curNode.leftChild;
            }
            return curNode;
        }
    }

完整代码：

/**
 * <p>Description  : 二叉排序树</p>
 * 或者是一颗空树，或者是一颗具有如下性质的树：
 * 1）若左子树不为空，那么左子树上面的所有节点的关键字值都比根节点的关键字值小
 * 2）若右子树不为空，那么右子树上面的所有节点的关键字值都比根节点的关键字值大
 * 3）左右子树都为二叉树
 * 4）没有重复值
 */
public class SearchBinaryTree {
    //根节点
    public TreeNode root;

   /**
     * 树中的节点
     */
    public static class TreeNode {
        int data;          //本例中以 int 型数据为例
        TreeNode leftChild;
        TreeNode rightChild;
        TreeNode parent;

        public TreeNode(int data) {
            this.data = data;
        }
    }

    /**
     * 添加节点
     */
    public TreeNode put(int data) {
        if (root == null) {  //空树
            TreeNode node = new TreeNode(data);
            root = node;
            return node;
        }

        TreeNode node = root;
        TreeNode parent = null;
        while (node != null) {
            parent = node;
            if (data < node.data) {
                node = node.leftChild;
            } else if (data > node.data) {
                node = node.rightChild;
            } else {  // 插入节点重复，直接返回
                return node;
            }
        }

        TreeNode newNode = new TreeNode(data);
        if (data < parent.data) {
            parent.leftChild = newNode;
        } else {
            parent.rightChild = newNode;
        }
        //切记别忘了（有点类似于双向链表的那种）
        newNode.parent = parent;

        return newNode;
    }

    /**
     * 中序遍历 非递归形式
     */
    public void midOrderTraverse(TreeNode root){
        if (root == null) return;

        /**
         * Stack 出站的顺序即 中序遍历 的顺序
         */
        Stack stack = new Stack();

        TreeNode target = root;
        while (target != null){
            stack.push(target);
            target = target.leftChild;
        }

        while (!stack.isEmpty()){
            TreeNode node = (TreeNode) stack.pop();

            System.out.print(node.data + " ");

            TreeNode tmp = node.rightChild;
            while (tmp != null){
                stack.push(tmp);
                tmp = tmp.leftChild;
            }
        }
    }

    /**
     * 查找一个节点
     */
    public TreeNode searchNode(int data) {
        if (root == null) {
            return null;
        }
        TreeNode node = root;
        while (node != null) {
            if (node.data == data) {
                return node;
            } else if (data > node.data) {
                node = node.rightChild;
            } else if (data < node.data) {
                node = node.leftChild;
            }
        }
        return null;
    }

    /**
     * 删除一个结点：参考TreeMap的方法，值复制，效率高。
     * <p>
     * 这样的代码写起来精简，稍微不易读。每种条件判断排列组合以后，覆盖了所有情况。
     *
     * @param p 要删除的节点。
     *             使用 ：
     *             TreeNode node = searchNode(3);
     *             tree.delNodeNew(node);
     */
    public void delNode(TreeNode p) {
        if(p == null) throw new NoSuchElementException();

        //左右孩子都存在的情况
        if (p.leftChild != null && p.rightChild != null) {
            TreeNode s = successor(p);
            p.data = s.data;
            p = s;
        }

        TreeNode replacement = p.leftChild != null ? p.leftChild : p.rightChild;
        if (replacement != null) {
            replacement.parent = p.parent;

            if(p.parent == null){
                root = replacement;
            } else if (p.parent.leftChild == p) {
                p.parent.leftChild = replacement;
            } else if (p.parent.rightChild == p) {
                p.parent.rightChild = replacement;
            }

            //注意这样写法
            p.leftChild = p.rightChild = p.parent = null;

        } else if (p.parent == null) {
            root = null;
        } else {
            if (p.parent.leftChild == p) {
                p.parent.leftChild = null;
            } else {
                p.parent.rightChild = null;
            }
        }

    }

    //寻找一个节点的后继节点
    private TreeNode successor(TreeNode t) {
        if (t == null) {
            return null;
        } else if (t.rightChild != null) {
            TreeNode p = t.rightChild;
            while (p.leftChild != null) {
                p = p.leftChild;
            }
            return p;
        } else {
            TreeNode p = t.parent;
            TreeNode ch = t;
            while (p != null && ch == p.rightChild) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }
}