数据结构 - 二叉树学习笔记

树（Tree）是一种很有趣的数据结构，它既能像链表那样快速的插入和删除，又能像有序数组那样快速查找。树的种类很多，本节将记录一种特殊的树————二叉树（Binary Tree）。二叉树的每个节点最多只能有两个子节点，通常称为左子节点和右子节点。如果一个二叉树的每个节点的左子节点的关键字值小于该节点，右子节点的关键字值大于等于该节点，那么这种二叉树也称为二叉搜索树（Binary Search Tree,BST），本节主要关注BST。

相关术语

查看一个BST例子：

• 路径：从一个节点走到另一个节点，经过的节点顺序就称为路径；
• 根：树的顶端节点称为根，一个数只能有一个根节点，并且从根节点到任意子节点只能有一条路径；
• 父节点：每个节点（除了根）都有一条边向上连接到另一个节点，这个节点就是下面节点的父节点；
• 子节点：每个节点（除了叶子节点）都有一条或两条边向下连接其他节点，下面这些节点就是当前节点的子节点。子节点分为左子节点和右子节点；
• 叶节点：没有子节点的节点称为叶子节点，或叶节点；
• 关键字：节点中的数据，比如上图中的数值。

操作BST

在操作BST前，我们先用代码定义一个BST的骨架：

/** BST */
public class BinarySearchTree {

   /** 根节点 */
    private Node root;
    /** 节点 */
    static class Node {
        /** 关键字 */
        int key;
        /** 额外携带的数据 */
        String value;
        /** 左子节点 */
        Node leftChild;
        /** 右子节点 */
        Node rightChild;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }
}

下面的这些操作都以这个BST为例：

插入

假如我们需要插入一个key为88的节点，需要经过如下步骤：

1. 从根节点出发，88比72大，所以走右子节点82路径；
2. 88比82大，所以走右子节点90路径；
3. 88比90小，所以走左子节点87路径；
4. 88比87大，并且87的右子节点为空，所以我们最终把88作为87的右子节点插入树中。

当key重复时，可以选择覆盖或者忽略，这由业务决定。

上述过程动态图如下所示：

Java代码实现如下：

/** BST */
public class BinarySearchTree {

   /** 根节点 */
    private Node root;
    /** 节点 */
    static class Node {
        /** 关键字 */
        int key;
        /** 额外携带的数据 */
        String value;
        /** 左子节点 */
        Node leftChild;
        /** 右子节点 */
        Node rightChild;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    /** 插入 */
    public void insert(int key, String value) {
        // 创建一个新节点
        Node newNode = new Node(key, value);
        if (this.root == null) {
            // 如果根为null，则这个新节点就是根
            root = newNode;
        } else {
            // 如果跟不为null，则从根开始搜索插入位置
            Node currentNode = root;
            // 用于暂存父节点
            Node parentNode;
            while (true) {
                // 父节点设置为当前节点
                parentNode = currentNode;
                if (key < currentNode.key) {
                    currentNode = currentNode.leftChild;
                    if (currentNode == null) {
                        // 如果key小于当前节点key，并且当前节点的左子节点为空，则将新节点
                        // 设置为当前节点（父节点暂存对象）的左子节点，退出循环
                        parentNode.leftChild = newNode;
                        return;
                    }
                } else if (key > currentNode.key) {
                    currentNode = currentNode.rightChild;
                    if (currentNode == null) {
                        // 如果key大于当前节点key，并且当前节点的右子节点为空，则将新节点
                        // 设置为当前节点（父节点暂存对象）的又子节点，退出循环
                        parentNode.rightChild = newNode;
                        return;
                    }
                } else {
                    // 如果key等于当前节点key，则将value覆盖当前节点value
                    currentNode.value = newNode.value;
                    return;
                }
            }
        }
    }
}

编写测试程序：

public class BinarySearchTreeTest {

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        Arrays.asList(72, 57, 82, 30, 63, 79, 90, 27, 40, 62, 67, 80, 87, 48).forEach(key -> {
            String value = "我是key为" + key + "的value";
            bst.insert(key, value);
        });
    }
}

以debug的方式运行程序，查看bst结构：

bst结构和上图一致，有兴趣可以自己验证。

查找

假如我们需要查找key为67的节点，需要经过如下步骤：

1. 从根节点出发，67比72小，所以走左子节点57路径；
2. 67比57大，所以走右子节点63路径；
3. 67比63大，所以走右子节点67路径；
4. 67等于67，找到目标节点，退出；
5. 如果搜索直到叶子节点都没找到，则返回空。

上述过程动态图如下所示：

Java代码实现如下：

/** BST */
public class BinarySearchTree {

   /** 根节点 */
    private Node root;
    /** 节点 */
    static class Node {
        /** 关键字 */
        int key;
        /** 额外携带的数据 */
        String value;
        /** 左子节点 */
        Node leftChild;
        /** 右子节点 */
        Node rightChild;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    /** 查找 */
    public Node find(int key) {
        // 从根节点开始查找
        Node currentNode = root;
        // 当前节点的key不等于被查找的key时
        while (currentNode.key != key) {
            if (key < currentNode.key) {
                // 如果key值小于当前节点key，则查找左子节点
                currentNode = currentNode.leftChild;
            } else {
                // 如果key值大于等于当前节点key，则查找右子节点
                currentNode = currentNode.rightChild;
            }
            // 如果当前节点为null，说明查到叶子节点了，仍没查到目标key，则直接返回null
            if (currentNode == null) {
                return null;
            }
        }
        // 返回当前节点（退出while循环要么key相等，要么没找到，结果为null）
        return currentNode;
    }
}

编写测试程序：

public class BinarySearchTreeTest {

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        Arrays.asList(72, 57, 82, 30, 63, 79, 90, 27, 40, 62, 67, 80, 87, 48).forEach(key -> {
            String value = "我是key为" + key + "的value";
            bst.insert(key, value);
        });
        System.out.println(bst.find(87).value);
        bst.insert(87, "hello world");
        System.out.println(bst.find(87).value);
    }
}

输出如下：

我是key为87的value
hello world

最大最小值

在BST里查找最大值和最小值是非常容易的一件事，根据BST特性，小的值都分布在左节点，大的值都分布在右节点，所以最小值查找方法为：从根节点出发，一直往下查找左子节点，当该节点不再有左子节点时，该节点就是最小节点；最大值查找方法为：从根节点出发，一直往下查找右子节点，当该节点不再有右子节点时，该节点就是最大节点。

查找最小值图示：

查找最大值图示：

Java代码实现如下：

/** BST */
public class BinarySearchTree {

   /** 根节点 */
    private Node root;
    /** 节点 */
    static class Node {
        /** 关键字 */
        int key;
        /** 额外携带的数据 */
        String value;
        /** 左子节点 */
        Node leftChild;
        /** 右子节点 */
        Node rightChild;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    /**
     * 最小值
     */
    public Node min() {
        Node currentNode = root;
        while (currentNode.leftChild != null) {
            currentNode = currentNode.leftChild;
        }
        return currentNode;
    }

    /**
     * 最大值
     */
    public Node max() {
        Node currentNode = root;
        while (currentNode.rightChild != null) {
            currentNode = currentNode.rightChild;
        }
        return currentNode;
    }
}

编写测试程序：

public class BinarySearchTreeTest {

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        Arrays.asList(72, 57, 82, 30, 63, 79, 90, 27, 40, 62, 67, 80, 87, 48).forEach(key -> {
            String value = "我是key为" + key + "的value";
            bst.insert(key, value);
        });
        System.out.println(bst.min().value);
        System.out.println(bst.max().value);
    }
}

输出如下所示：

我是key为27的value
我是key为90的value

删除

删除是BST操作里最复杂的一个，因为需要考虑的因素比较多：

1. 被删除的节点是叶子节点；
2. 被删除的节点只有一个子节点；
3. 被删除的节点有两个子节点。

下面我们逐个分析：

被删除的节点是叶子节点

这种情况最为简单，删除节点前需要先找到该节点，过程和上面的查找类似。找到需要删除的节点后，如果是叶子节点，则将该节点的父节点引用置为null，被删除的节点没了引用，后续由GC自动回收。

假如我们需要删除key为48的节点，需要经过如下步骤：

1. 从根节点出发，48比72小，所以走左子节点57路径；
2. 48比57小，所以走左子节点30路径；
3. 48比30大，所以走右子节点40路径；
4. 48比40大，所以走右子节点48路径；
5. 48等于48，所以当前节点就是需要被删除节点；
6. 48没有子节点，为叶子节点，所以直接将40的右子节点引用设置为null即可。

该过程如下图所示：

Java代码实现如下：

/** BST */
public class BinarySearchTree {

   /** 根节点 */
    private Node root;
    /** 节点 */
    static class Node {
        /** 关键字 */
        int key;
        /** 额外携带的数据 */
        String value;
        /** 左子节点 */
        Node leftChild;
        /** 右子节点 */
        Node rightChild;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    /** 删除 */
    public boolean delete(int key) {

        /* --------- 查找需要被删除的节点以及它的父节点 ------- */
        // 从根节点开始查找
        Node deleteNode = root;
        // 暂存需要被删除节点的父节点
        Node parentNode = root;
        // 标识被删除的节点时父节点的左子节点还是右子节点
        boolean isLeftChild = false;
        // 下面这个过程和查找一致，只不过加了isLeftChild标识
        while (deleteNode.key != key) {
            parentNode = deleteNode;
            if (key < deleteNode.key) {
                isLeftChild = true;
                deleteNode = deleteNode.leftChild;
            } else {
                isLeftChild = false;
                deleteNode = deleteNode.rightChild;
            }
            // 如果目标key对应的节点为空，则不需要删除，直接返回false
            if (deleteNode == null) {
                return false;
            }
        }

        /* --------- 情况1：被删除的节点是叶子节点 ------- */
        if (deleteNode.leftChild == null
                && deleteNode.rightChild == null) {
            if (deleteNode == root) {
                // 如果要删除的节点为root，则直接将root节点设置为null
                root = null;
            } else if (isLeftChild) {
                // 如果要删除的叶子节点为父节点的左子节点，则将父节点的左子节点关联置为null
                parentNode.leftChild = null;
            } else {
                // 如果要删除的叶子节点为父节点的右子节点，则将父节点的右子节点关联置为null
                parentNode.rightChild = null;
            }
        }
        return true;
    }
}

编写测试程序：

public class BinarySearchTreeTest {

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        Arrays.asList(72, 57, 82, 30, 63, 79, 90, 27, 40, 62, 67, 80, 87, 48).forEach(key -> {
            String value = "我是key为" + key + "的value";
            bst.insert(key, value);
        });
        System.out.println(bst.delete(49));
        System.out.println(bst.delete(48));
    }
}

false
true

可以看到40的右子节点已经被删除。

被删除的节点只有一个子节点

这种情况也比较简单，只需要将被删除节点的子节点和其父节点建立连接关系即可。

假如我们需要删除key为79的节点，需要经过如下步骤：

1. 从根节点出发，79比72大，所以走右子节点82路径；
2. 79比82小，所以走左子节点79路径；
3. 79等于79，所以当前节点就是需要被删除节点；
4. 79只有一个右子节点，因为79是82的左子节点，所以直接将80设置为82的左子节点即可。

该过程如下图所示：

Java代码实现如下：

/** BST */
public class BinarySearchTree {

   /** 根节点 */
    private Node root;
    /** 节点 */
    static class Node {
        /** 关键字 */
        int key;
        /** 额外携带的数据 */
        String value;
        /** 左子节点 */
        Node leftChild;
        /** 右子节点 */
        Node rightChild;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    /**
     * 删除
     */
    public boolean delete(int key) {

        /* --------- 查找需要被删除的节点以及它的父节点 ------- */
        // 从根节点开始查找
        Node deleteNode = root;
        // 暂存需要被删除节点的父节点
        Node parentNode = root;
        // 标识被删除的节点时父节点的左子节点还是右子节点
        boolean isLeftChild = false;
        // 下面这个过程和查找一致，只不过加了isLeftChild标识
        while (deleteNode.key != key) {
            parentNode = deleteNode;
            if (key < deleteNode.key) {
                isLeftChild = true;
                deleteNode = deleteNode.leftChild;
            } else {
                isLeftChild = false;
                deleteNode = deleteNode.rightChild;
            }
            // 如果目标key对应的节点为空，则不需要删除，直接返回false
            if (deleteNode == null) {
                return false;
            }
        }

        /* --------- 情况1：被删除的节点是叶子节点 ------- */
        if (deleteNode.leftChild == null
                && deleteNode.rightChild == null) {
            if (deleteNode == root) {
                // 如果要删除的节点为root，则直接将root节点设置为null
                root = null;
            } else if (isLeftChild) {
                // 如果要删除的叶子节点为父节点的左子节点，则将父节点的左子节点关联置为null
                parentNode.leftChild = null;
            } else {
                // 如果要删除的叶子节点为父节点的右子节点，则将父节点的右子节点关联置为null
                parentNode.rightChild = null;
            }
        } else if (deleteNode.leftChild != null
                && deleteNode.rightChild != null) {
            /* --------- 情况3：被删除的节点有两个子节点 ------- */

        } else {
            /* --------- 情况2：被删除的节点只有一个子节点 ------- */
            // 获取被删除节点的唯一子节点
            Node deleteNodeChild = deleteNode.leftChild == null ?
                    deleteNode.rightChild : deleteNode.leftChild;
            if (deleteNode == root) {
                // 如果被删除节点就是root，那么将其唯一子节点设置为root
                root = deleteNodeChild;
            } else if (isLeftChild) {
                // 如果要删除的叶子节点为父节点的左子节点，则将父节点的左子节点关联置为被删除节点的唯一子节点
                parentNode.leftChild = deleteNodeChild;
            } else {
                // 如果要删除的叶子节点为父节点的右子节点，则将父节点的右子节点关联置为被删除节点的唯一子节点
                parentNode.rightChild = deleteNodeChild;
            }
        }
        return true;
    }
}

编写测试程序：

public class BinarySearchTreeTest {

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        Arrays.asList(72, 57, 82, 30, 63, 79, 90, 27, 40, 62, 67, 80, 87, 48).forEach(key -> {
            String value = "我是key为" + key + "的value";
            bst.insert(key, value);
        });
        System.out.println(bst.delete(79));
        System.out.println(bst.find(82).leftChild.value);
    }
}

程序输出：

true
我是key为80的value

被删除的节点有两个子节点

这种情况比较复杂，删除的节点不能用删除节点的某个子节点来代替。比如现在需要删除上述BST的57节点，假如用57节点的右子节点63代替该节点，那么63的左子节点既不能是62，也不能是57的左子节点30。

这种情况下需要找到被删除节点的中序后继节点（successor）来代替它。所谓的中序后继节点就是：整个树中关键字值比被删除节点大，并且比被删除节点右子节点小的那部分节点中的关键字值最小的节点。

根据中序后继节点的定义来看，要找到它也很简单：

1. 从被删除节点的右子节点出发，一直往下找左子节点，当该节点不再有左子节点时，该节点就是中序后继节点；
2. 如果被删除节点的右子节点没有左子节点，那么它就是要找的中序后继节点。

举个例子，比如现在需要删除上述BST的57节点，那么它的中序后继节点为62；假如要删除的节点为63，那么它的中序后继为67：

1. 当删除的节点为57时，过程如下所示：

   

2. 当删除的节点为63时，过程如下所示：

   

编写查找中序后继节点的方法：

/** BST */
public class BinarySearchTree {

   /** 根节点 */
    private Node root;
    /** 节点 */
    static class Node {
        /** 关键字 */
        int key;
        /** 额外携带的数据 */
        String value;
        /** 左子节点 */
        Node leftChild;
        /** 右子节点 */
        Node rightChild;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }
    /**
     * 查找中序后继节点
     */
    private Node getSuccessor(Node deleteNode) {
        // 暂存中序后继节点的父节点
        Node successorParent = deleteNode;
        // 暂存中序后继节点
        Node successor = deleteNode;
        // 先从删除节点的右子节点开始查找
        Node currentNode = deleteNode.rightChild;
        while (currentNode != null) {
            successorParent = successor;
            successor = currentNode;
            // 一直往下查找当前节点的左子节点，直到为空
            currentNode = currentNode.leftChild;
        }
        // 如上面文章所说，中序后继节点和删除节点有两种可能性，
        // 当中序后继节点不是删除节点的右子节点时，需要做如下额外操作
        if (successor != deleteNode.rightChild) {
            // 如果中序后继节点的右子节点不为空的话，将其和中序后继节点父节点的左子节点挂钩
            if (successor.rightChild != null) {
                successorParent.leftChild = successor.rightChild;
            }
            // 中序后继节点的右子节点和删除节点的右子节点挂钩
            successor.rightChild = deleteNode.rightChild;
        }
        // 中序后继节点的左子节点和删除节点的左子节点挂钩
        successor.leftChild = deleteNode.leftChild;
        // 剩下的删除节点的父节点和中序后继节点的连接关系在删除方法里处理，
        // 因为这个方法内无法获取删除节点的父节点对象
        return successor;
    }
}

完成删除方法的最后一个部分：

/** BST */
public class BinarySearchTree {

   /** 根节点 */
    private Node root;
    /** 节点 */
    static class Node {
        /** 关键字 */
        int key;
        /** 额外携带的数据 */
        String value;
        /** 左子节点 */
        Node leftChild;
        /** 右子节点 */
        Node rightChild;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    /**
     * 删除
     */
    public boolean delete(int key) {
        /* --------- 查找需要被删除的节点已经它的父节点 ------- */
        // 从根节点开始查找
        Node deleteNode = root;
        // 暂存需要被删除节点的父节点
        Node parentNode = root;
        // 标识被删除的节点时父节点的左子节点还是右子节点
        boolean isLeftChild = false;
        // 下面这个过程和查找一致，只不过加了isLeftChild标识
        while (deleteNode.key != key) {
            parentNode = deleteNode;
            if (key < deleteNode.key) {
                isLeftChild = true;
                deleteNode = deleteNode.leftChild;
            } else {
                isLeftChild = false;
                deleteNode = deleteNode.rightChild;
            }
            // 如果目标key对应的节点为空，则不需要删除，直接返回false
            if (deleteNode == null) {
                return false;
            }
        }
        /* --------- 情况1：被删除的节点是叶子节点 ------- */
        if (deleteNode.leftChild == null
                && deleteNode.rightChild == null) {
            if (deleteNode == root) {
                // 如果要删除的节点为root，则直接将root节点设置为null
                root = null;
            } else if (isLeftChild) {
                // 如果要删除的叶子节点为父节点的左子节点，则将父节点的左子节点关联置为null
                parentNode.leftChild = null;
            } else {
                // 如果要删除的叶子节点为父节点的右子节点，则将父节点的右子节点关联置为null
                parentNode.rightChild = null;
            }
        } else if (deleteNode.leftChild != null
                && deleteNode.rightChild != null) {
            /* --------- 情况3：被删除的节点有两个子节点 ------- */
            // 获取删除节点的中序后继节点
            Node successor = getSuccessor(deleteNode);
            // 如果伤处节点就是根节点的话，中序后继节点直接成为新的根
            if (deleteNode == root) {
                root = successor;
            } else if (isLeftChild) {
                // 如果删除节点是父节点的左子节点，则将父节点的左子节点和中序后继节点挂钩
                parentNode.leftChild = successor;
            } else {
                // 如果删除节点是父节点的右子节点，则将父节点的右子节点和中序后继节点挂钩
                parentNode.rightChild = successor;
            }
        } else {
            /* --------- 情况2：被删除的节点只有一个子节点 ------- */
            // 获取被删除节点的唯一子节点
            Node deleteNodeChild = deleteNode.leftChild == null ?
                    deleteNode.rightChild : deleteNode.leftChild;
            if (deleteNode == root) {
                // 如果被删除节点就是root，那么将其唯一子节点设置为root
                root = deleteNodeChild;
            } else if (isLeftChild) {
                // 如果要删除的叶子节点为父节点的左子节点，则将父节点的左子节点关联置为被删除节点的唯一子节点
                parentNode.leftChild = deleteNodeChild;
            } else {
                // 如果要删除的叶子节点为父节点的右子节点，则将父节点的右子节点关联置为被删除节点的唯一子节点
                parentNode.rightChild = deleteNodeChild;
            }
        }
        return true;
    }
}

编写测试程序测试一下：

当删除的节点为57时：

public class BinarySearchTreeTest {

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        Arrays.asList(72, 57, 82, 30, 63, 79, 90, 27, 40, 62, 67, 80, 87, 48).forEach(key -> {
            String value = "我是key为" + key + "的value";
            bst.insert(key, value);
        });
        System.out.println("删除57节点: " + bst.delete(57));
        System.out.println("72节点的左子节点为: " + bst.find(72).leftChild.key);
        BinarySearchTree.Node node62 = bst.find(62);
        System.out.println("62节点的左子节点为: " + node62.leftChild.key);
        System.out.println("62节点的右子节点为: " + node62.rightChild.key);
    }
}

输出如下：

删除57节点: true
72节点的左子节点为: 62
62节点的左子节点为: 30
62节点的右子节点为: 63

当删除的节点为63时：

public class BinarySearchTreeTest {

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        Arrays.asList(72, 57, 82, 30, 63, 79, 90, 27, 40, 62, 67, 80, 87, 48).forEach(key -> {
            String value = "我是key为" + key + "的value";
            bst.insert(key, value);
        });
        System.out.println("删除63节点: " + bst.delete(63));
        System.out.println("57节点的右子节点为: " + bst.find(57).rightChild.key);
        BinarySearchTree.Node node67 = bst.find(67);
        System.out.println("67节点的左子节点为: " + node67.leftChild.key);
        System.out.println("67节点的右子节点为: " + (node67.rightChild == null ? null : node67.rightChild.key));
    }
}

输出如下：

删除63节点: true
57节点的右子节点为: 67
67节点的左子节点为: 62
67节点的右子节点为: null

遍历

遍历树指的是以一种特定顺序访问树的每一个节点，这个顺序分为：中序、前序和后序。

中序遍历

中序遍历的步骤为：

1. 递归遍历目标节点的左子节点；
2. 访问目标节点本身；
3. 递归遍历目标节点的右子节点。

Java实现如下：

/** BST */
public class BinarySearchTree {

    /** 根节点 */
    private Node root;

    /** 遍历需要从根开始遍历，所以添加根的get方法 */
    public Node getRoot() {
        return root;
    }

    /** 节点 */
    static class Node {
        /** 关键字 */
        int key;
        /** 额外携带的数据 */
        String value;
        /** 左子节点 */
        Node leftChild;
        /** 右子节点 */
        Node rightChild;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    /** 中序遍历 */
    public void inOrder(Node targetNode) {
        if (targetNode != null) {
            // 递归遍历目标节点的左子节点
            inOrder(targetNode.leftChild);
            // 访问目标节点本身
            System.out.print(targetNode.key + " ");
            // 递归遍历目标节点的右子节点
            inOrder(targetNode.rightChild);
        }
    }
}

编写测试程序：

public class BinarySearchTreeTest {

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        Arrays.asList(72, 57, 82, 30, 63, 79, 90, 27, 40, 62, 67, 80, 87, 48).forEach(key -> {
            String value = "我是key为" + key + "的value";
            bst.insert(key, value);
        });
        bst.inOrder(bst.getRoot());
    }
}

输出如下：

27 30 40 48 57 62 63 67 72 79 80 82 87 90

这个过程如下动图所示：

前序遍历

前序遍历的步骤为：

1. 访问目标节点本身；
2. 递归遍历目标节点的左子节点；
3. 递归遍历目标节点的右子节点。

Java实现如下：

/** BST */
public class BinarySearchTree {

    /** 根节点 */
    private Node root;

    /** 遍历需要从根开始遍历，所以添加根的get方法 */
    public Node getRoot() {
        return root;
    }

    /** 节点 */
    static class Node {
        /** 关键字 */
        int key;
        /** 额外携带的数据 */
        String value;
        /** 左子节点 */
        Node leftChild;
        /** 右子节点 */
        Node rightChild;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    /** 前序遍历 */
    public void preOrder(Node targetNode) {
        if (targetNode != null) {
            // 访问目标节点本身
            System.out.print(targetNode.key + " ");
            // 递归遍历目标节点的左子节点
            preOrder(targetNode.leftChild);
            // 递归遍历目标节点的右子节点
            preOrder(targetNode.rightChild);
        }
    }
}

编写测试程序：

public class BinarySearchTreeTest {

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        Arrays.asList(72, 57, 82, 30, 63, 79, 90, 27, 40, 62, 67, 80, 87, 48).forEach(key -> {
            String value = "我是key为" + key + "的value";
            bst.insert(key, value);
        });
        bst.preOrder(bst.getRoot());
    }
}

输出如下：

72 57 30 27 40 48 63 62 67 82 79 80 90 87

这个过程如下动图所示：

后序遍历

前序遍历的步骤为：

1. 递归遍历目标节点的左子节点；
2. 递归遍历目标节点的右子节点；
3. 访问目标节点本身。

Java实现如下：

/** BST */
public class BinarySearchTree {

    /** 根节点 */
    private Node root;

    /** 遍历需要从根开始遍历，所以添加根的get方法 */
    public Node getRoot() {
        return root;
    }

    /** 节点 */
    static class Node {
        /** 关键字 */
        int key;
        /** 额外携带的数据 */
        String value;
        /** 左子节点 */
        Node leftChild;
        /** 右子节点 */
        Node rightChild;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    /** 后续遍历 */
    public void postOrder(Node targetNode) {
        if (targetNode != null) {
            // 递归遍历目标节点的左子节点
            postOrder(targetNode.leftChild);
            // 递归遍历目标节点的右子节点
            postOrder(targetNode.rightChild);
            // 访问目标节点本身
            System.out.print(targetNode.key + " ");
        }
    }
}

编写测试程序：

public class BinarySearchTreeTest {

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        Arrays.asList(72, 57, 82, 30, 63, 79, 90, 27, 40, 62, 67, 80, 87, 48).forEach(key -> {
            String value = "我是key为" + key + "的value";
            bst.insert(key, value);
        });
        bst.postOrder(bst.getRoot());
    }
}

输出如下：

27 48 40 30 62 67 63 57 80 79 87 90 82 72

这个过程如下动图所示：

完整代码

/**
 * BST
 */
public class BinarySearchTree {
    /**
     * 根节点
     */
    private Node root;

    /**
     * 遍历需要从根开始遍历，所以添加根的get方法
     */
    public Node getRoot() {
        return root;
    }

    /**
     * 插入
     */
    public void insert(int key, String value) {
        // 创建一个新节点
        Node newNode = new Node(key, value);
        if (this.root == null) {
            // 如果根为null，则这个新节点就是根
            root = newNode;
        } else {
            // 如果跟不为null，则从根开始搜索插入位置
            Node currentNode = root;
            // 用于暂存父节点
            Node parentNode;
            while (true) {
                // 父节点设置为当前节点
                parentNode = currentNode;
                if (key < currentNode.key) {
                    currentNode = currentNode.leftChild;
                    if (currentNode == null) {
                        // 如果key小于当前节点key，并且当前节点的左子节点为空，则将新节点
                        // 设置为当前节点（父节点暂存对象）的左子节点，退出循环
                        parentNode.leftChild = newNode;
                        return;
                    }
                } else if (key > currentNode.key) {
                    currentNode = currentNode.rightChild;
                    if (currentNode == null) {
                        // 如果key大于当前节点key，并且当前节点的右子节点为空，则将新节点
                        // 设置为当前节点（父节点暂存对象）的又子节点，退出循环
                        parentNode.rightChild = newNode;
                        return;
                    }
                } else {
                    // 如果key等于当前节点key，则将value覆盖当前节点value
                    currentNode.value = newNode.value;
                    return;
                }
            }
        }
    }

    /**
     * 查找
     */
    public Node find(int key) {
        // 从根节点开始查找
        Node currentNode = root;
        // 当前节点的key不等于被查找的key时
        while (currentNode.key != key) {
            if (key < currentNode.key) {
                // 如果key值小于当前节点key，则查找左子节点
                currentNode = currentNode.leftChild;
            } else {
                // 如果key值大于等于当前节点key，则查找右子节点
                currentNode = currentNode.rightChild;
            }
            // 如果当前节点为null，说明查到叶子节点了，仍没查到目标key，则直接返回null
            if (currentNode == null) {
                return null;
            }
        }
        // 返回当前节点（退出while循环要么key相等，要么没找到，结果为null）
        return currentNode;
    }

    /**
     * 最小值
     */
    public Node min() {
        Node currentNode = root;
        while (currentNode.leftChild != null) {
            currentNode = currentNode.leftChild;
        }
        return currentNode;
    }

    /**
     * 最大值
     */
    public Node max() {
        Node currentNode = root;
        while (currentNode.rightChild != null) {
            currentNode = currentNode.rightChild;
        }
        return currentNode;
    }

    /**
     * 删除
     */
    public boolean delete(int key) {
        /* --------- 查找需要被删除的节点已经它的父节点 ------- */
        // 从根节点开始查找
        Node deleteNode = root;
        // 暂存需要被删除节点的父节点
        Node parentNode = root;
        // 标识被删除的节点时父节点的左子节点还是右子节点
        boolean isLeftChild = false;
        // 下面这个过程和查找一致，只不过加了isLeftChild标识
        while (deleteNode.key != key) {
            parentNode = deleteNode;
            if (key < deleteNode.key) {
                isLeftChild = true;
                deleteNode = deleteNode.leftChild;
            } else {
                isLeftChild = false;
                deleteNode = deleteNode.rightChild;
            }
            // 如果目标key对应的节点为空，则不需要删除，直接返回false
            if (deleteNode == null) {
                return false;
            }
        }
        /* --------- 情况1：被删除的节点是叶子节点 ------- */
        if (deleteNode.leftChild == null
                && deleteNode.rightChild == null) {
            if (deleteNode == root) {
                // 如果要删除的节点为root，则直接将root节点设置为null
                root = null;
            } else if (isLeftChild) {
                // 如果要删除的叶子节点为父节点的左子节点，则将父节点的左子节点关联置为null
                parentNode.leftChild = null;
            } else {
                // 如果要删除的叶子节点为父节点的右子节点，则将父节点的右子节点关联置为null
                parentNode.rightChild = null;
            }
        } else if (deleteNode.leftChild != null
                && deleteNode.rightChild != null) {
            /* --------- 情况3：被删除的节点有两个子节点 ------- */
            // 获取删除节点的中序后继节点
            Node successor = getSuccessor(deleteNode);
            // 如果伤处节点就是根节点的话，中序后继节点直接成为新的根
            if (deleteNode == root) {
                root = successor;
            } else if (isLeftChild) {
                // 如果删除节点是父节点的左子节点，则将父节点的左子节点和中序后继节点挂钩
                parentNode.leftChild = successor;
            } else {
                // 如果删除节点是父节点的右子节点，则将父节点的右子节点和中序后继节点挂钩
                parentNode.rightChild = successor;
            }
        } else {
            /* --------- 情况2：被删除的节点只有一个子节点 ------- */
            // 获取被删除节点的唯一子节点
            Node deleteNodeChild = deleteNode.leftChild == null ?
                    deleteNode.rightChild : deleteNode.leftChild;
            if (deleteNode == root) {
                // 如果被删除节点就是root，那么将其唯一子节点设置为root
                root = deleteNodeChild;
            } else if (isLeftChild) {
                // 如果要删除的叶子节点为父节点的左子节点，则将父节点的左子节点关联置为被删除节点的唯一子节点
                parentNode.leftChild = deleteNodeChild;
            } else {
                // 如果要删除的叶子节点为父节点的右子节点，则将父节点的右子节点关联置为被删除节点的唯一子节点
                parentNode.rightChild = deleteNodeChild;
            }
        }
        return true;
    }

    /** 中序遍历 */
    public void inOrder(Node targetNode) {
        if (targetNode != null) {
            // 递归遍历目标节点的左子节点
            inOrder(targetNode.leftChild);
            // 访问目标节点本身
            System.out.print(targetNode.key + " ");
            // 递归遍历目标节点的右子节点
            inOrder(targetNode.rightChild);
        }
    }

    /** 前序遍历 */
    public void preOrder(Node targetNode) {
        if (targetNode != null) {
            // 访问目标节点本身
            System.out.print(targetNode.key + " ");
            // 递归遍历目标节点的左子节点
            preOrder(targetNode.leftChild);
            // 递归遍历目标节点的右子节点
            preOrder(targetNode.rightChild);
        }
    }

    /** 后续遍历 */
    public void postOrder(Node targetNode) {
        if (targetNode != null) {
            // 递归遍历目标节点的左子节点
            postOrder(targetNode.leftChild);
            // 递归遍历目标节点的右子节点
            postOrder(targetNode.rightChild);
            // 访问目标节点本身
            System.out.print(targetNode.key + " ");
        }
    }

    /**
     * 查找中序后继节点
     */
    private Node getSuccessor(Node deleteNode) {
        // 暂存中序后继节点的父节点
        Node successorParent = deleteNode;
        // 暂存中序后继节点
        Node successor = deleteNode;
        // 先从删除节点的右子节点开始查找
        Node currentNode = deleteNode.rightChild;
        while (currentNode != null) {
            successorParent = successor;
            successor = currentNode;
            // 一直往下查找当前节点的左子节点，直到为空
            currentNode = currentNode.leftChild;
        }
        // 如上面文章所说，中序后继节点和删除节点有两种可能性，
        // 当中序后继节点不是删除节点的右子节点时，需要做如下额外操作
        if (successor != deleteNode.rightChild) {
            // 如果中序后继节点的右子节点不为空的话，将其和中序后继节点父节点的左子节点挂钩
            if (successor.rightChild != null) {
                successorParent.leftChild = successor.rightChild;
            }
            // 中序后继节点的右子节点和删除节点的右子节点挂钩
            successor.rightChild = deleteNode.rightChild;
        }
        // 中序后继节点的左子节点和删除节点的左子节点挂钩
        successor.leftChild = deleteNode.leftChild;
        // 剩下的删除节点的父节点和中序后继节点的连接关系在删除方法里处理，
        // 因为这个方法内无法获取删除节点的父节点对象
        return successor;
    }


    /**
     * 节点
     */
    static class Node {
        /**
         * 关键字
         */
        int key;
        /**
         * 额外携带的数据
         */
        String value;
        /**
         * 左子节点
         */
        Node leftChild;
        /**
         * 右子节点
         */
        Node rightChild;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }
}

BST效率

节点的查找需要从根节点开始一层一层往下找，树节点数和层数的关系如下表所示：

节点数	层数
1	1
3	2
7	3
15	4
31	5
…	…
1023	10
…	…
32767	15
…	…
1048575	20
…	…
33554432	25
…	…
1073741824	30

假设节点数为N，层数为L，那么不难看出它们的关系为：N=2^(L-1)，所以L=log2(N+1)，大约为log2N，大O表示法为O(logN)。

红黑树

BST的缺陷

虽然BST结合了数组和链表的优势，但它也不是完美的，当BST不平衡的时候，查找操作效率急剧下降。举个比较极端的例子：

假如插入的数据是升序数据：2，4，6，8，10，12…，这时候BST如下所示：

这时候BST实际上就是一个链表结构了，搜索效率为O(N)。一个BST完全平衡和完全不平衡的情况比较少见，就概率来说，BST的搜索效率介于O(N)与O(logN)之间。

红黑树规则

为了解决非平衡树搜索效率下降的问题，人们又提出了红黑树的概念。在红黑树中，每个节点要么是红色的要么是黑色的，红黑树在插入和删除的过程中，需要遵循某些特定的规则，遵循这些规则可以确保数始终是趋于平衡的。

红黑树除了遵循基本的BST规则外，还需遵循以下4个规则：

1. 每一个节点不是红色就是黑色；
2. 根节点一定是黑色的；
3. 如果节点时红色的，那么它的子节点必须都是黑色的；
4. 从根节点到叶子节点或空子节点的每条路径，必须包含相同数目的黑色节点。

在数据插入和删除过程中，如果违背了上述4个规则，则树会执行以下操作进行修正，以重新满足上述4个规则：

1. 改变节点的颜色；
2. 执行旋转操作。

红黑树演示

下面通过一个动图演示红黑树如何处理升序数据：2，4，6，8，10，12的插入，使得树趋于平衡：

参考自《Java数据结构与算法（第二版）》，上述BST图片均来自http://btv.melezinek.cz/binary-search-tree.html网站，红黑树示例来自https://www.wztlink1013.com/visualization/RedBlack.html。