【面试题精选】二叉搜索树详解

r囧r小猫 2022-03-07 00:54 211阅读 0赞

## 一、二叉搜索树的概念及特点 ##

二叉搜索树（BLT）：Binary Search Tree，又名二叉排序树，二叉查找树，是一种常见的二叉树类型。它是一棵空树或具有以下特点的二叉树：

1.  若任意结点的左子树不为空，那么左子树的任意结点的值均小于当前节点的值。
2.  若任意结点的右子树不为空，那么右子树的任意结点的值均大于当前节点的值。
3.  它的左右子树也均为二叉搜索树。
4.  中序遍历可以得到一个有序序列。

树的物理结构如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzk4NjYx_size_16_color_FFFFFF_t_70]  
二叉搜索树，顾名思义，是一种方便查找和插入的二叉树，它的查找和插入操作的时间复杂度均为 O(logn)。  
我们给出二叉树结点（为了方便讲解，这里的树结点的key值均为Integer类型），代码如下：

public class TreeNode { 
        Integer key;
        TreeNode leftChild;
        TreeNode rightChild;
    
        public TreeNode(Integer key, TreeNode leftChild, TreeNode rightChild) { 
            this.key = key;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }
    
        public TreeNode() { 
        }
    }

--------------------

## 二、二叉搜索树的相关操作 ##

介绍完二叉搜索树的概念及性质，再来看看二叉搜索树的相关操作。

--------------------

##### 1、二叉搜索树的查找 #####

如果我们要在二叉搜索树中查找一个值为 value 的结点应该如何去做？此时我们就要充分利用到二叉搜索树的1，2两条特点。

**基本思想：**  
拿 value 跟 根节点 root 比较，如果value小于 root，就从 root 的左子树查找，如果value大于 root 就从 root 的右子树查找。

从上面的思想我们就能看出这里要用到递归或者迭代（本文采用迭代），具体步骤我们在代码中讲解：

// 二叉搜索树的查找操作
        public TreeNode search(Integer key) { 
            // 如果为一颗空树，则没有查询到，直接返回空
            if (root == null) { 
                return null;
            }
            // 创建一个移动的指针
            TreeNode temp = root;
            // 遍历该二叉搜索树
            while (true) { 
                // 如果查找的值小于当前指针位置的值，就移动到当前结点的左子树
                if (key < temp.key) { 
                    if (temp.leftChild != null) { 
                        temp = temp.leftChild;
                    // 如果左子树为空，查找失败，返回null
                    } else { 
                        return null;
                    }
                // 如果查找的值大于当前指针位置的值，就移动到当前结点的右子树
                } else if (key > temp.key) { 
                    if (temp.rightChild != null) { 
                        temp = temp.rightChild;
                    // 如果右子树为空，查找失败，返回null
                    } else { 
                        return null;
                    }
                // 如果要查找的值等于当前结点的值，查找成功，直接返回当前节点
                } else { 
                    return temp;
                }
            }
        }

--------------------

##### 2、二叉搜索树的插入操作 #####

![图片来源于网络][2019031520200035.gif]  
通过上面的动图，我们可以明显的看到，二叉搜索树在插入结点时，一定是在当前树的叶子节点插入。基本思想如下：

*  拿要插入的结点的值value与根节点key比较，如果value小于key，且根节点的左孩子为空，那就插入为根节点的左孩子；如果根节点的左孩子不为空，指针移动到根节点的左孩子，重复进行此操作。
 *  拿要插入的结点的值value与根节点key比较，如果value大于key，且根节点的右孩子为空，那就插入为根节点的右孩子；如果根节点的有孩子不为空，指针移动到根节点的右孩子，重复进行此次操作。

下面来看代码详解：

// 二叉搜索树的插入操作
        public boolean insertNode(TreeNode node) { 
            // 如果根节点为null，那么此树为一棵空树，直接返回false
            if (root == null) { 
                root = node;
                return true;
            }
            TreeNode temp = root;
            while (true) { 
                // 如果要插入的结点的值比当前节点小，就去当前结点的左子树插入，如果左子树为空，直接插入，如果左子树不为空，指针移动到此节点的左子树，继续进行此步骤，直至插入成功。
                if (node.key < temp.key) { 
                    if (temp.leftChild != null) { 
                        // 左子树不为空，移动到左子树的根节点
                        temp = temp.leftChild;
                    } else { 
                        // 左子树为空，插入成功
                        temp.leftChild = node;
                        return true;
                    }
                    // 如果要插入的结点的值比当前节点大，就去当前结点的右子树插入，如果右子树为空，直接插入，如果右子树不为空，指针移动到此节点的右子树，继续进行此步骤，直至插入成功。
                } else { 
                    if (temp.rightChild != null) { 
                        // 右子树不为空，移动到右子树的根节点
                        temp = temp.rightChild;
                    } else { 
                        // 右子树为空，插入成功
                        temp.rightChild = node;
                        return true;
                    }
                }
            }
        }

--------------------

##### 3、判断二叉搜索树中是否存在值为value的节点 #####

直接上代码：

// 在一个搜索树中查找某个值是否存在
        public boolean contains(int value, TreeNode root) { 
            // 循环直到root为空，则没找到，返回false
            while (root != null) { 
                // 如果 要查找的值比当前结点的值大，去当前结点的右子树查找
                if (root.key < value) { 
                    root = root.rightChild;
                // 如果 要查找的值比当前节点的值小，去当前结点的左子树查找
                } else if (root.key > value) { 
                    root = root.leftChild;
                // 如果相等，就找到，返回true
               } else { 
                    return true;
                }
            }
            return false;
        }

--------------------

##### 4、查找二叉搜索树中的最大最小值的结点 #####

根据二叉搜索树的性质我们可以知道，二叉搜索树中的最小值在树的最左边，最大值在树的最右边，来看代码：

// 查找树中值最大的结点
        public TreeNode getMax(TreeNode root){ 
            // 思路：一直往右找，直到右孩子为空，返回当前结点
            while (root.rightChild != null) { 
                root = root.rightChild;
            }
            return root;
        }
    
    // 查找树中值最小的结点
        private TreeNode getMin(TreeNode root){ 
            // 思路：一直往左找，直到左孩子为空，返回当前结点
            while (root.leftChild != null) { 
                root = root.leftChild;
            }
            return root;
        }

--------------------

##### 5、删除二叉搜索树的最大最小结点 #####

删除最大最小结点分为两种情况：

1.  最小结点为叶子节点，即左右子树均为空。此种情况直接删除结点即可。如下图情况：

![在这里插入图片描述][20190315204527346.png]  
此时的最小值为25，此节点没有右子树，为叶子节点，直接删除即可

1.  最小节点为非叶子结点，存在右子树。此种情况要将此节点的左子树连接到此节点的父节点的左子树上。如下图：  
    （为什么没有左子树呢，因为上面提到过，最小值的结点一定在最左边，最左边的意思就是到一个没有左子树的结点。）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzk4NjYx_size_16_color_FFFFFF_t_70 1]  
    上图的二叉搜索树的最小结点的值为 3，但是此节点存在右子树，不能直接删除，因此要把 值为3的结点的右子树连接到 值为6的结点的左子树上。删除完毕如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzk4NjYx_size_16_color_FFFFFF_t_70 2]  
    下面看代码详解：  
    这里的与父节点的连接采取的是返回值的形式。

public void removeMin(){ 
            root = removeMin(root);
        }
    
        // 删除查找树中最小的结点
         public TreeNode removeMin(TreeNode root) { 
            // 如果左子树为空，则此结点为最小值，记下它的右子树，并把它的右子树置为null，删除，返回他的右子树
            if (root.leftChild == null) { 
                TreeNode rightChild = root.rightChild;
                root.rightChild = null;
                return rightChild;
            }
            // 如果左子树不为空，递归查找root的左子树是否为最小值
            root.leftChild = removeMin(root.leftChild);
            return  root;
        }
    
        public void removeMax(){ 
            root = removeMax(root);
        }
    
        // 删除查找树中最大的结点
        private TreeNode removeMax(TreeNode root) { 
            // 如果左子树为空，则此结点为最小值，记下它的右子树，并把它的右子树置为null，删除，返回他的右子树
            if (root.rightChild == null) { 
                TreeNode leftChild = root.leftChild;
                root.leftChild = null;
                return leftChild;
            }
            // 如果左子树不为空，递归查找root的左子树是否为最小值
            root.rightChild = removeMin(root.rightChild);
            return  root;
        }

--------------------

##### 6、删除二叉搜索树中的任意值为value的结点 #####

随机删除可能会出现如下四种情况：

1.  删除的结点为叶子结点，直接删除
2.  删除的结点只有左子树而没有右子树，和删除最小值一样，返回左子树的根节点。
3.  删除的结点只有右子树而没有左子树，和删除最大值一样，返回右子树的根节点。
4.  删除的结点既有左子树，又有右子树。此种情况较为复杂，基本思路是找出此节点的右子树的值最小的结点代替此节点称为根节点。可能比较难理解，我们依然先画图表示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzk4NjYx_size_16_color_FFFFFF_t_70 3]  
还是刚才那棵树，比如我们要删除值为8的那个结点，此节点既有左子树又有右子树，按照我们刚才的思路，要先找到此节点的右子树中值最大的结点，即为值为11的结点，然后值为9的结点代替8作为当前树的根节点，注意要把值最小的结点从右子树中删除掉，可调用我们之前的removeMin的方法，结果如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzk4NjYx_size_16_color_FFFFFF_t_70 4]

接下来我们来看代码详解：

// 删除查找树中任意值为value的结点
        private TreeNode remove(TreeNode root, Integer value) { 
            // 如果是空树，直接返回null
            if (root == null) { 
                return null;
            }
            // 如果要查找的value值比root的key值小，那么去左子树递归删除
            if (value < root.key) { 
                root.leftChild = remove(root.leftChild,value);
                return root;
            // 如果查找的value值比root的key值大，那么去右子树递归删除
            } else if (value > root.key) { 
                root.leftChild = remove(root.rightChild, value);
                return root;
            // 如果刚好相等，即找到了结点。
            } else { 
                // 如果该节点的左子树为空，右子树不为空，则记下右子树，删除该节点，并返回右子树的根节点
                if (root.leftChild == null && root.rightChild != null) { 
                    // 记下右子树的根节点
                    TreeNode rightChild = root.rightChild;
                    // 删除此节点
                    root.rightChild = null;
                    // 返回右子树的根节点
                    return rightChild;
                }
                // 如果该节点的右子树为空，左子树不为空，则记下左子树，删除该结点，并返回左子树的根节点
                if (root.rightChild == null && root.leftChild != null) { 
                    // 记下左子树的根节点
                    TreeNode leftChild = root.leftChild;
                    // 删除此节点
                    root.leftChild = null;
                    // 返回左子树的根节点
                    return leftChild;
                }
                // 如果此结点既有左子树，又有右子树，那么要从右子树中查找出一个最小值，替换当前节点作为当前自述的根节点
    
                // 记下当前节点的右子树的最小值结点作为新的根节点
                TreeNode rightMin = getMin(root.rightChild);
                // 从右子树中删除该节点，并将右子树新的根节点与新根节点连接
                rightMin.rightChild = removeMin(root.rightChild);
                // 新的根节点与左子树连接
                rightMin.leftChild = root.leftChild;
                // 删除旧的根节点
                root.leftChild = root.rightChild = null;
                // 返回新的根节点
                return rightMin;
            }
        }
    
        public void remove(Integer value) { 
            root = remove(root,value);
        }

## 注意： ##

由于时间原因，部分代码未测试，如代码有误，欢迎指正。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzk4NjYx_size_16_color_FFFFFF_t_70]: /images/20220307/501e6ddd247146748d6497b1f157ef09.png
[2019031520200035.gif]: /images/20220307/0af385ea9d664e5999913641c211043f.png
[20190315204527346.png]: /images/20220307/4228ec016de44c00a927258252e1e20f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzk4NjYx_size_16_color_FFFFFF_t_70 1]: /images/20220307/bb120db744e04c078269aeef96d0f268.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzk4NjYx_size_16_color_FFFFFF_t_70 2]: /images/20220307/5bd5acb1551e49c1a8cee2aa0b54b1b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzk4NjYx_size_16_color_FFFFFF_t_70 3]: /images/20220307/3a81bc140a584cc7ae0565aa590203b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzk4NjYx_size_16_color_FFFFFF_t_70 4]: /images/20220307/6fd621f486de404fb311f0b4a647fc5b.png