二分搜索树详解

一、为什么要研究树结构

树结构是计算机世界中非常高效的一种数据结构，也是应用非常广泛的数据结构。

1. 什么是树结构？

2. 树结构的应用场景

以上这些应用场景都是树型结构的使用场景，树结构的特点就是层次清晰，高效。

3. 树结构常用的类型都有什么？

二分搜索树、平衡二叉树、线段树、Trie等都是很常用的树型数据结构。

二、二分搜索树基础

二分搜索树是树型结构中的一种，要了解二分搜索树需要先说一下二叉树结构。

1. 什么是二叉树？

二叉树和链表是一样，都是动态数据结构，所以我们在创建二叉树的数据就不需要指定容量。

2. 二叉树的组成图示

• 根节点：二叉树具有一个唯一的根节点
• 左右节点：二叉树每个节点最多有两个节点(左节点和右节点)
• 父节点：二叉树每个节点最多有一个父节点

3. 二叉树具有天然递归结构

为什么说二叉树具有天然的递归结构呢？因为对于一个父节点来说，下边的每个节点(左节点和右节点)又是一个新的二叉树。

4. 二叉树不一定都是满的

在介绍非满二叉树前，先来介绍一下满二叉树：

所谓的满二叉树就是指，每个节点都有左右两个节点，直到叶子节点为止。

有时候一个节点甚至是空也是一个二叉树。

5. 二分搜索树

在介绍完二叉树以后我们来看一下二分搜索树：

二分搜索树的定义：

二分搜索树是二叉树的一种，二分搜索树的特点是每个节点的值都大于左子树的所有节点，每个节点的值都小于右子树中所有节点的值，然后每个父节点下边的子树也是一个二分搜索树，同时二分搜索树每个节点的值必须满足可比较性。

二分搜索树既然是二叉树的一种，也就意味着二分搜索树也不一定都是满的，更多的时候应该是不满的情况：

三、代码实现一个二分搜索树

package com.mufeng.binarySearchTree;

/**
 * Created by wb-yxk397023 on 2018/6/30.
 */
public class BST<E extends Comparable<E>> {

    private class Node{
        public E e;
        public Node left, right;

        public Node(E e){
            this.e = e;
            this.left = null;
            this.right = null;
        }
    }

    private Node root;
    private int size;

    public BST(){
        root = null;
        size = 0;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }
}

四、向二分搜索树中添加元素

1. 添加新元素图示

当向一个树中添加元素的时候如果这个树为空，那么第一个添加的元素将会变成这个树的root节点。

向一个有元素的树结构中添加一个新元素的时候，将会通过对比找到新添加元素的位置(比根节点小的元素放在左子树中，反之放在右子树中)。

继续通过对比找到新添加元素的位置。

通过图示不难发现，向树中添加元素是一个比较的操作，通过对比将新添加的元素放在合适的位置上边。

补充：

我们的添加操作是不包含重复操作的；但是如果想要包含重复元素的只需要改变一个对比的条件就可以了，比如左子树可以放置小于或者等于根节点的元素或者右子树中放置大于或者等于根的元素即可。

2. 代码实现

/**
 * 向二分搜索树中添加新的元素e
 * @param e
 */
public void add(E e){
    if (root == null){
        root = new Node(e);
        size++;
    }else {
        add(root, e);
    }
}

/**
 * 向以node为根的二分搜索树中插入元素e，递归算法
 * @param node
 * @param e
 */
public void add(Node node, E e){
    // 递归的终止条件
    if (e.equals(node.e)){
        return;
    }else if (e.compareTo(node.e) < 0 && node.left == null){
        node.left = new Node(e);
        size++;
        return;
    }else if (e.compareTo(node.e) > 0 && node.right == null){
        node.right = new Node(e);
        size++;
        return;
    }

    // 递归调用
    if (e.compareTo(node.e) < 0){
        add(node.left, e);
    }
    add(node.right, e);
}

由于二分搜索树的结构非常适合使用递归的操作，所以我们的添加操作直接使用递归的方式进行实现，但是上边的代码递归的终止条件显得有些臃肿，所以我们需要对添加操作的代码逻辑进行优化：

/**
 * 向二分搜索树中添加新的元素e
 * @param e
 */
public void add(E e){
    root = add(root, e);
}

/**
 * 向以node为根的二分搜索树中插入元素e，递归算法
 * 返回插入新节点后二分搜索树的根
 * @param node
 * @param e
 * @return
 */
public Node add(Node node, E e){
    // 递归的终止条件
    if (node == null){
        size++;
        return new Node(e);
    }

    // 递归调用
    if (e.compareTo(node.e) < 0){
        node.left = add(node.left, e);
    }else if (e.compareTo(node.e) > 0){
        node.right = add(node.right, e);
    }

    return node;
}

五、二分搜索树的查询操作

如果大家理解了二分搜索树的添加操作，那么就可以很容易的理解二分搜索树的查询操作。

/**
 * 二分搜索树中是否包含元素e
 * @param e
 * @return
 */
public boolean contains(E e){
    return contains(root, e);
}

/**
 * 查询以node为节点的二分搜索树中是否包含元素e
 * @param node
 * @param e
 * @return
 */
private boolean contains(Node node, E e){
    if (node == null){
        return false;
    }else if (e.compareTo(node.e) == 0){
        return true;
    }else if (e.compareTo(node.e) < 0){
        return contains(node.left, e);
    }
    return contains(node.right, e);
}

六、二分搜索树的遍历

1. 前序遍历

前序遍历就是在遍历左右子树之前先遍历当前节点，对于二分搜索树来说，前序遍历是最自然的遍历方式也是最常用的遍历方式。

遍历操作的意思就是把所有节点都访问一遍，遍历操作的原因可能是基于业务的相关的，在线性结构下，遍历是极其容易的但是在树结构下可能有点不太一样，这是因为在执行遍历二分搜索树的时候左右两个子树也需要进行遍历。

/**
 * 二叉树的前序遍历
 */
public void preOrder(){
    preOrder(root);
}

/**
 * 前序遍历以node为根的二分搜索树，递归算法
 * @param node
 */
private void preOrder(Node node){
    if (node == null){
        return;
    }

    System.out.println(node.e);
    preOrder(node.left);
    preOrder(node.right);
}

重写toString：

/**
 * 以前序遍历的方式重写toString
 * @return
 */
@Override
public String toString(){
    StringBuilder res = new StringBuilder();
    generateBSTString(root, 0, res);
    return res.toString();
}

/**
 * 生成以node为根节点，深度为depth的描述二叉树的字符串
 * @param node
 * @param depth
 * @param res
 */
private void generateBSTString(Node node, int depth, StringBuilder res){
    if (node == null){
        res.append(generateDepthString(depth) + "null\n");
        return;
    }
    res.append(generateDepthString(depth) + node.e + "\n");
    generateBSTString(node.left, depth + 1, res);
    generateBSTString(node.right, depth + 1, res);
}

private String generateDepthString(int depth){
    StringBuilder res = new StringBuilder();

    for (int i = 0; i < depth; i++){
        res.append("--");
    }
    return res.toString();
}

2. 中序遍历

既然有前序遍历自然就有中序遍历，只需要改变遍历的顺序即可实现中序遍历，中序遍历的顺序为先遍历左子树，然后遍历当前节点最后遍历右子树即可。

/**
 * 二分搜索树的中序遍历
 */
public void inOrder(){
    inOrder(root);
}

/**
 * 中序遍历以node为根的二分搜索树，递归算法
 * @param node
 */
private void inOrder(Node node){
    if (node == null){
        return;
    }
    inOrder(node.left);
    System.out.println(node.e);
    inOrder(node.right);
}

3. 后序遍历

后序遍历的原理在遍历当前节点之前先遍历左右子树，然后在遍历当前节，得到的结果就是后序遍历的结果。

后续遍历的适用场景：比如释放二分搜索树的内存这样的操作需要用到后序遍历，因为要释放内存肯定需要先释放左右子树在释放当前节点。

/**
 * 二分搜索树的后序遍历
 */
public void postOrder(){
    postOrder(root);
}

/**
 * 后续遍历以node为根的二分搜索树，递归算法
 * @param node
 */
private void postOrder(Node node){
    if (node == null){
        return;
    }
    postOrder(node.left);
    postOrder(node.right);
    System.out.println(node.e);
}

4. 深度优先遍历

非递归实现二分搜索树的前序遍历：

// 二分搜索树的非递归前序遍历
public void preOrderNR(){

    if(root == null)
        return;

    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while(!stack.isEmpty()){
        Node cur = stack.pop();
        System.out.println(cur.e);

        if(cur.right != null)
            stack.push(cur.right);
        if(cur.left != null)
            stack.push(cur.left);
    }
}

在二分搜索树这样的结构中，使用递归可以很简单的实现功能，但是非递归的话实现起来就会有一点困难，当使用非递归的方式实现前序遍历的话，需要借助栈来实现，这样的遍历方式也被称为深度优先遍历。

5. 广度优先遍历

// 二分搜索树的层序遍历
public void levelOrder(){

    if(root == null)
        return;

    Queue<Node> q = new LinkedList<>();
    q.add(root);
    while(!q.isEmpty()){
        Node cur = q.remove();
        System.out.println(cur.e);

        if(cur.left != null)
            q.add(cur.left);
        if(cur.right != null)
            q.add(cur.right);
    }
}

二分搜索树的层序遍历也叫做广度优先遍历；深度优先遍历以及广度优先遍历更多的是应用与算法中的，所以这里不做深入的说明。

七、二分搜索树中的删除操作

1. 删除二分搜索树中的最大值和最小值

在二分搜索树中执行删除操作是相对于其他操作来说比较麻烦的，我们先来一端图示分析一下。

以此图为例，如果要删除这个二分搜索树的最小以及最大节点，我们需要从根节点开始执行查询操作，如果要删除最小值的话，就需要一直向左进行查询，直到找到最小值即可，删除最大值也是一样的操作。

此处需要注意的是，如果我们在进行删除此树的最小值的话，则16将会被删除，22将作为此树根节点28的左子树的根节点。

需要注意的是，删除操作的前提是需要先找到待删除的树的最小值与最大值，所以我们需要先实现这个逻辑才能进行删除的操作。

/**
 * 寻找二分搜索树的最小元素
 * @return
 */
public E minimum(){
    if(size == 0)
        throw new IllegalArgumentException("BST is empty");

    Node miniNode = minimum(root);
    return miniNode.e;
}

/**
 * 返回以node为根的二分搜索树的最小值所在的节点
 * @param node
 * @return
 */
private Node minimum(Node node){
    if (node.left == null){
        return node;
    }

    return minimum(node.left);
}

/**
 * 寻找二分搜索树的最大元素
 * @return
 */
public E maxmum(){
    if (size == 0){
        throw new IllegalArgumentException("BST is empty");
    }

    Node maxNode = maxmum(root);
    return maxNode.e;
}

/**
 * 返回以node为根的二分搜索树的最大值所在的节点
 * @param node
 * @return
 */
private Node maxmum(Node node){
    if (node.right == null){
        return node;
    }

    return maxmum(node.right);
}

最大和最小的值都找到以后我们就可以进行删除的操作了，但是删除的时候我们需要考虑特殊的情况，比如如图所示：

比如这棵树中的最小值是13，我们找到后可以直接删除，因为13这个节点是一个叶子节点，删除之后没有影响。

如果此时在删除15也是一样的，15这个节点下边的也没有了节点，删除15对于我们来说也没有影响。

如果此时我们要删除22这个节点，但是22不是叶子节点，这个时候我们就需要一些处理才能删除，因为22这个节点下边还有元素，我们可以将22下边的整个右子树作为根节点的左子树即可。

对于删除二分搜索树中的最大节点也是一样的操作，这里就不再进行图示了。

/**
 * 从二分搜索树中删除最小值所在节点, 返回最小值
 * @return
 */
public E removemin(){
    E ret = minimum();
    root = removemin(root);
    return ret;
}

/**
 * 删除掉以node为根的二分搜索树中的最小节点
 * 返回删除节点后新的二分搜索树的根
 * @param node
 * @return
 */
private Node removemin(Node node){
    if (node.left == null){
        Node rightNode = node.right;
        node.right = null;
        size--;
        return rightNode;
    }

    node.left = removemin(node.left);
    return node;
}

/**
 * 从二分搜索树中删除最大值所在节点，返回最大值
 * @return
 */
public E removeMax(){
    E ret = maxmum();
    root = removeMax(root);
    return ret;
}

/**
 * 删除掉以node为根的二分搜索树中的最大节点
 * 返回删除节点后新的二分搜索树的根
 * @param node
 * @return
 */
private Node removeMax(Node node){
    if (node.right == null){
        Node leftNode = node.left;
        node.left = null;
        size--;
        return leftNode;
    }

    node.left = removeMax(node.right);
    return node;
}

2. 删除二分搜索树中的任意元素

删除二分搜索树中任意元素分以下几种情况：

1. 删除只有左子树的元素

2. 删除只有右子树的元素

3. 删除有左右子树的元素

第一种情况和第二种情况都比较简单，和我们删除最小值和最大值的逻辑基本一样，但是第三种情况则相对复杂一些，这里我们采取一种后继的做法，请看图示：

假设我们要删除58这个元素，但是这个元素有左右两个子树，我们采用后继的方式意思就是在58节点的右子树中找到一个距离58最近的元素来代替58。

在这个右子树中我们找到59这个元素。

将59这个元素取出并作为50和60两个节点的根节点。

删除掉58这个元素。

将59这个元素挂在在根元素下。

这样就完成了这个删除操作。

def remove(self, e):
    """
    从二分搜索树中删除元素为e的节点
    :param e: 要删除的元素
    """
    self.root = self._remove(self.root, e)

def _remove(self, node, e):
    """
    删除掉以node为根的二分搜索树中值为e的节点, 递归算法
    返回删除节点后新的二分搜索树的根
    :param node: 当前节点
    :param e: 要删除的元素
    :return: 删除节点后的新根节点
    """
    if node is None:
        return None

    if e < node.e:
        node.left = self._remove(node.left, e)
        return node
    elif e > node.e:
        node.right = self._remove(node.right, e)
        return node
    else:  # e == node.e
        # 待删除节点左子树为空的情况
        if node.left is None:
            self.remove_min(node)
        # 待删除节点右子树为空的情况
        if node.right is None:
            self.remove_max(node)
        # 待删除节点左右子树均不为空的情况
        # 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
        # 用这个节点顶替待删除节点的位置
        successor = self.minimum(node.right)
        successor.right = self.remove_min(node.right)
        successor.left = node.left
        node.left = node.right = None
        return successor

八、二分搜索树相关代码

from collections import deque

class BST:
    """二分搜索树"""

    class Node:
        """树节点类"""
        def __init__(self, e):
            self.e = e
            self.left = None
            self.right = None

    def __init__(self):
        """构造函数"""
        self.root = None
        self.size = 0

    def size(self):
        """获取树的大小"""
        return self.size

    def is_empty(self):
        """判断树是否为空"""
        return self.size == 0

    def add(self, e):
        """向二分搜索树中添加新的元素e"""
        self.root = self._add(self.root, e)

    def _add(self, node, e):
        """向以node为根的二分搜索树中插入元素e，递归算法
        返回插入新节点后二分搜索树的根"""
        # 递归的终止条件
        if node is None:
            self.size += 1
            return self.Node(e)

        # 递归调用
        if e < node.e:
            node.left = self._add(node.left, e)
        elif e > node.e:
            node.right = self._add(node.right, e)

        return node

    def contains(self, e):
        """二分搜索树中是否包含元素e"""
        return self._contains(self.root, e)

    def _contains(self, node, e):
        """查询以node为节点的二分搜索树中是否包含元素e"""
        if node is None:
            return False
        elif e == node.e:
            return True
        elif e < node.e:
            return self._contains(node.left, e)
        return self._contains(node.right, e)

    def pre_order(self):
        """二分搜索树的前序遍历"""
        self._pre_order(self.root)

    def _pre_order(self, node):
        """前序遍历以node为根的二分搜索树，递归算法"""
        if node is None:
            return

        print(node.e)
        self._pre_order(node.left)
        self._pre_order(node.right)

    def pre_order_nr(self):
        """二分搜索树的非递归前序遍历"""
        stack = []
        stack.append(self.root)
        while stack:
            cur = stack.pop()
            print(cur.e)

            if cur.right is not None:
                stack.append(cur.right)
            if cur.left is not None:
                stack.append(cur.left)

    def in_order(self):
        """二分搜索树的中序遍历"""
        self._in_order(self.root)

    def _in_order(self, node):
        """中序遍历以node为根的二分搜索树，递归算法"""
        if node is None:
            return
        self._in_order(node.left)
        print(node.e)
        self._in_order(node.right)

    def post_order(self):
        """二分搜索树的后序遍历"""
        self._post_order(self.root)

    def _post_order(self, node):
        """后续遍历以node为根的二分搜索树，递归算法"""
        if node is None:
            return
        self._post_order(node.left)
        self._post_order(node.right)
        print(node.e)

    def minimum(self):
        """寻找二分搜索树的最小元素"""
        if self.size == 0:
            raise Exception("BST is empty")

        mini_node = self._minimum(self.root)
        return mini_node.e

    def _minimum(self, node):
        """返回以node为根的二分搜索树的最小值所在的节点"""
        if node.left is None:
            return node

        return self._minimum(node.left)

    def maximum(self):
        """寻找二分搜索树的最大元素"""
        if self.size == 0:
            raise Exception("BST is empty")

        max_node = self._maximum(self.root)
        return max_node.e

    def _maximum(self, node):
        """返回以node为根的二分搜索树的最大值所在的节点"""
        if node.right is None:
            return node

        return self._maximum(node.right)

    def remove_min(self):
        """从二分搜索树中删除最小值所在节点, 返回最小值"""
        ret = self.minimum()
        self.root = self._remove_min(self.root)
        return ret

    def _remove_min(self, node):
        """删除掉以node为根的二分搜索树中的最小节点
        返回删除节点后新的二分搜索树的根"""
        if node.left is None:
            right_node = node.right
            node.right = None
            self.size -= 1
            return right_node

        node.left = self._remove_min(node.left)
        return node

    def remove_max(self):
        """从二分搜索树中删除最大值所在节点，返回最大值"""
        ret = self.maximum()
        self.root = self._remove_max(self.root)
        return ret

    def _remove_max(self, node):
        """删除掉以node为根的二分搜索树中的最大节点
        返回删除节点后新的二分搜索树的根"""
        if node.right is None:
            left_node = node.left
            node.left = None
            self.size -= 1
            return left_node

        node.left = self._remove_max(node.right)
        return node

    def level_order(self):
        """二分搜索树的层序遍历"""
        q = deque()
        q.append(self.root)
        while q:
            cur = q.popleft()
            print(cur.e)

            if cur.left is not None:
                q.append(cur.left)
            if cur.right is not None:
                q.append(cur.right)

    def remove(self, e):
        """从二分搜索树中删除元素为e的节点"""
        self.root = self._remove(self.root, e)

    def _remove(self, node, e):
        """删除掉以node为根的二分搜索树中值为e的节点, 递归算法
        返回删除节点后新的二分搜索树的根"""
        if node is None:
            return None

        if e < node.e:
            node.left = self._remove(node.left, e)
            return node
        elif e > node.e:
            node.right = self._remove(node.right, e)
            return node
        else:  # e == node.e

            # 待删除节点左子树为空的情况
            if node.left is None:
                self._remove_min(node)

            # 待删除节点右子树为空的情况
            if node.right is None:
                self._remove_max(node)

            # 待删除节点左右子树均不为空的情况

            # 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            # 用这个节点顶替待删除节点的位置
            successor = self._minimum(node.right)
            successor.right = self._remove_min(node.right)
            successor.left = node.left

            node.left = node.right = None

            return successor

    def __str__(self):
        """以前序遍历的方式重写toString"""
        res = []
        self._generate_bst_string(self.root, 0, res)
        return ''.join(res)

    def _generate_bst_string(self, node, depth, res):
        """生成以node为根节点，深度为depth的描述二叉树的字符串"""
        if node is None:
            res.append(self._generate_depth_string(depth) + "null\n")
            return
        res.append(self._generate_depth_string(depth) + str(node.e) + "\n")
        self._generate_bst_string(node.left, depth + 1, res)
        self._generate_bst_string(node.right, depth + 1, res)

    def _generate_depth_string(self, depth):
        """生成深度字符串"""
        res = []
        for i in range(depth):
            res.append("--")
        return ''.join(res)