精华内容
下载资源
问答
  • 二叉搜索树 定义 二叉搜索树,就是二叉查找树、二叉排序树,说白了就是一个思想: 用一棵树存储一些元素值,其中我们保证左子树结点均小于根节点,右子树结点均大于根节点。 直接从之前的博客中嫖了一张图: 这颗树...

    二叉搜索树

    定义

    二叉搜索树,就是二叉查找树、二叉排序树,说白了就是一个思想:
    用一棵树存储一些元素值,其中我们保证左子树结点均小于根节点,右子树结点均大于根节点。
    直接从之前的博客中嫖了一张图:
    在这里插入图片描述
    这颗树有很多很好的性质:

    • 首先中序遍历的结果是从小到大递增的,可以用于排序
    • 在查找的过程中,我们只需要从根节点出发,和跟结点对比即可,如果树的构建比较好,那么我们就可以保证O(logn)的查找效率
    • 这棵树还有一种形式,将每一个单分支结点和叶子节点都补上结点,构成一种新的树。
      在这里插入图片描述
      我们可以看出,新补充的结点都是叶子节点,他们不属于某一个特定的数值,而是一个范围,查找失败的范围。

    如何构建最优二叉搜索树

    所以接下来我们的任务就是按照搜索的特点构建一个最优的二叉搜索树。
    这个搜索的特点可能让人有点懵,其实和哈夫曼树差不多,这里的搜索是有一个概率的,不论是搜索成功还是失败(到达叶子节点)。

    输入

    • 大小为n的数组(1-n),存储的是每一个非叶子结点的数值信息;
    • 大小为n的数组(1-n),存储非叶子结点的查找概率p
    • 大小为n+1的数组(0-n),存储叶子结点的查找概率q

    输出
    查找代价最低的二叉搜索树

    代价?
    这里我们要知道,每一次搜索的时候都需要和根节点比较,每一次比较都有一个代价。
    如果将一个查找率很高的结点放在下面,那么代价就会很大。

    叶子结点是非叶子节点+1,因为每一个非叶子节点都有两个孩子节点,这个就不需要我再证明了吧。

    分析一下,子问题就不用说了,我们都是树结构了,子问题也是重叠的。
    然后证明最优子结构,这个……就自己脑补一下,如果有一个子问题不是最优的,那整体也不可能是最优的。

    实现

    我们先放一下存储结构,因为不太好想。
    先给出几个定义吧,首先是E[i][j],表示从第i个到第j个结点的最小二叉搜索树。

    如果j = i-1,说明只有一个叶子节点 i-1
    E[i][j] = qi-1
    如果j =>i,
    E[i][j] = min{ E[i][r-1]+E[r+1][j]+pr+a },其中i <= r <= j

    (j = i-1可能有一点费解,这是因为我们加入了叶子结点的原因,这是表示只有一个叶子节点)

    如果是只有一个叶子节点,说白了就是查找失败,那么就只需要有叶子节点的代价即可;
    但如果是多个结点(包括一个结点),我们需要将其拆分成两个树,从i到r-1和r+1到j,然后将r作为根节点,查找次数为1,代价为pr,这也是前三项的由来。
    这里我们有一个a,是因为我们将两棵树都增高了一层,所以我们需要加上多的这部分的代价,我们简写成a,可以看出a的代价就是两棵子树的所有结点对应的概率*1,再算上pr,其实就是E[i][j] = E[i][r-1]+E[r+1][j]+Σi到j的所有节点的概率,我们将这个概率记为W[i][j]。

    所以我们在计算E[i][j]不但需要两个子树的代价,还需要W[i][j]的代价。那么我们先来计算W[i][j]的代价。

    W[i][i-1] = qi-1,是因为只有一个叶子节点
    W[i][j] = W[i][j-1]+pj+qj,即在原来的基础上加一个叶子节点再加一个j结点(两个非叶子结点之间一定是有一个叶子节点的,并且这个叶子节点的下标应该和后一个非叶子结点相同,因为叶子节点下标从0开始,非叶子节点从2开始)

    其实写成这样,我们的存储格式也就很明显了,就是在一个二维方阵中,行数和列数都是元素个数加一,不过这个格式也有点绕。

    行数准确来说是叶子节点的个数,因为需要存储W[i][i-1]这样的结点,所以列数要比元素个数多一个,更好行数和列数就相同了。我们用n=4来举例吧。

    W10W11W12W13W14
    W21W22W23W24
    W32W33W34
    W43W44
    W54

    我们填入的方式是这样的,首先将主对角线进行填充,按照定义对角线分别为q0-4,然后接下来还是按照对角线填充,按照我们的定义来就行了。

    在得到了W矩阵之后,我们就可以开始进行E矩阵的计算了。
    此时我们的定义是这样的:

    E[i][i-1] = qi-1
    E[i][j] = min{ E[i][r-1]+E[r+1][j]+W[i][j] },其中i<=r<=j

    伪代码

    伪代码是同时实现的W、E矩阵,
    另外我们还是采用矩阵链乘法的对角线遍历方式来实现循环的,

    Optimal-BST(p, q, n)
    //初始化
    For  i=1  To  n+1   Do
          E(i, i-1) = qi-1;
          W(i, i-1) = qi-1;
          
    For  l=1  To  n   Do				//对角线为l
    	For   i=1   To   n-l+1   Do		//对角线上元素的横坐标i
    	    j=i+l-1;					//按照l和i计算纵坐标j
    		E(i, j) =;
            W(i, j)=W(i, j-1)+pj+qj;
            For  r=i  To  j   Do
            	temp=E(i, r-1)+E(r+1, j)+W(i, j);
                If	temp<E(i, j)
                	E(i, j)=t;  
                	//Root(i, j)=r;
    Return  E and  Root   
    

    其中的root矩阵是我们用来记录二叉搜索树的根节点位置的矩阵。
    在调用的过程中我们还是采取递归的方式,首先调用函数,传递参数i = 1,j = n,在函数内部我们先查看j是否等于i,如果是则直接打印这个结点,否则在矩阵中查找root[i][j]的值,确定两个子树分别调用函数,最后记得补上叶子节点即可。

    习题——堆石子

    在一条直线上有 n 堆石子,每堆有一定的数量,每次可以将两堆相邻的石子合并,合并
    后放在两堆的中间位置,合并的费用为两堆石子的总数。求把所有石子合并成一堆的最
    小花费(定义 dp[i][j]为第 i 堆石子到第 j 堆合并的最小花费)。

    这里我们只给出递推方程,只要有了方程,剩下的实现问题都不大。
    首先,如果是只有一堆石子(dp[i][i]),不需要合并,代价为0
    否则dp[i][j] = min{ dp[i][k] + dp[k+1][j] +Σm[i…j] },即两个子问题的代价和,再加上涉及到的所有石子堆的代价和。

    得到了方程,确定为二维的n阶方阵,先填入临界值然后按照定义即可。(和矩阵链乘法相似,在之前的博客中有涉及)

    习题——LCS 的优化

    滚动数组

    LCS就是我们之前提到的最长公共子序列,我们之前还提到了有一个叫滚动数组的概念,是用来进行dp问题的优化的。那么我们就来看一下。
    之前我们定义的矩阵大小是m行n列的,但是我们的C[i][j]只和左上角、左边和上面的元素有关,剩下的元素都不是直接作用的,那么我们是否可以在这上面动手脚?

    首先,我们只创建一个两行n列的二维数组,先在第一行进行初始化,还有第一列。
    然后我们就可以通过这些来进行第二行的创建了。
    在两行都填满了之后,我们就不再需要第一行的内容了,那么我们就可以让数组滚动起来,用第一行接着存储第三行的内容。(这样会特别不好实现,所以还是将第二行向上移动一下比较舒服)

    当然了,我们也可以只使用两列来实现。

    其他的呢

    首先,我们的矩阵链乘法和比较类似的堆式子问题,都是需要对角线填值(还有二叉搜索树),很明显需要的不只是几行或者几列,我们的零一背包问题则可以考虑。

    所以,我们也算是得到了一个小结论,如果是需要多项对比来填值的(一般为对角线方式填值)不能使用滚动数组,但是如果是只需要几项比较(固定在上下行或者是左右列的那种),可以考虑一下。

    B数组的问题

    这里再说一下B的问题吧,其实也不是真的需要,在我们得到了C矩阵后,从最后按照B的定义来回溯,也能正确的找到最长公共子序列,而且时间复杂度为O(m+n)。
    最快max{m,n}就能找到(尽量走对角线)
    最慢也是m+n的代价(没有相同的,即没有走对角线的那种情况)

    习题——找硬币问题

    这个应该是在leecode上都有的。

    题目描述:
    给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以
    凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,
    返回-1。(提示:你可以认为每种硬币的数量是无限的)。
    示例 1:
    输入: coins = [1, 2, 5], amount = 11
    输出: 3
    解释: 11 = 5 + 5 + 1
    示例 2:
    输入: coins = [2], amount = 3
    输出: -1

    这个题就是使用一个一维数组将每一个金额对应的最小硬币数目都存起来,
    然后A[amount] = min{ A[amount-coins[i] ] +1 },也就是先用一个硬币找零,看看剩下的金额中的最少需要几个。
    比如找25元,我们可以先找1元,然后看看24应该怎么找钱,然后再试试先找5元,看看二十怎么办。

    初始值就是刚好为硬币金额的为1,小于最小硬币金额的为0,然后从左到右一个个找过去就行了。

    习题——01背包问题中背包的内容

    我们在解决了01背包问题后,还没有好好看一下怎么进行回溯最优解,这次我们补上。
    首先,我们不能为每一个矩阵的每一个点都构建一个数组来存储01串吧,明显不合适,
    另外我们之前都是使用递归的方式,从最后到问题的最开始(初始值)找回去的,
    所以我的想法还是要利用递归的方式,一步步回溯出整体来。

    实际上我们的M[i][j]只有两种可能,要么内容和M[i+1][j]相同,要么是m[i+1][j-wi]+vi,
    所以我们先采用一个额外的数组B,来进行存储(这样看起来比较显然,随后我们会去掉这个数组)我们这个值的由来,如果是(i+1,j)就记录j,否则记录j-wi的值,
    这样在回溯的过程中,如果记录的值和当前相同,说明这个东西没有被放进去,我们就在下一行继续;否则就是放进去了,先打印这个东西,然后就需要从m[i+1][j-wi]位置处继续了。
    当我们到达了最后一行,就直接通过该处的值是否为0判断有没有放回去即可。

    //M为dp数组,B为刚才的记录矩阵,n为物品个数,ij为下标
    zero_one_knapsack(M,B,n,i,j)	//初始调用为M、B、n、1、C
    if(n == i)						//到达最后一行
    	if(M[i][j])					//最后一个物品放进去了
    		printf n
    else
    	if(M[i][j] == j)			//没放进去,直接调用函数
    		zero_one_knapsack(M,B,i+1,j);
    	else 						//放进去了,需要打印一下
    		zero_one_knapsack(M,B,i+1,M[i][j]);
    		printf i
    

    当然了,我们在LCS中可以放弃B数组,在这里一样可以,不过这时需要我们自己去判断从哪里来的了。
    如果是放不放是一样的,那么我们在打印过程中就无所谓了,找一种就行了。

    展开全文
  • 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大(如果有相同的值...

    一、二叉排序树概述

    二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小右子节点的值比当前节点的值大(如果有相同的值,则该节点放在左子节点或右子节点都可)。在一般情况下,二叉排序树的查询效率比链表结构要高。

    如下图所示就是一个二叉排序树:

    在这里插入图片描述

    二、二叉排序树的基本操作

    2.1 创建和遍历二叉排序树

    【案例描述】

    给定如下数组:

    arr = {7, 3, 10, 12, 5, 1, 9}
    

    其二叉排序树如下图所示:

    在这里插入图片描述

    要求:

    1. 创建二叉排序树
    2. 中序遍历二叉排序树

    【代码实现】

    /**
     * @Description 创建和遍历二叉排序树
     */
    public class No1_BinarySortTree {
        public static void main(String[] args) {
            int[] arr = {7, 3, 10, 12, 5, 1, 9};
            BinarySortTree tree = new BinarySortTree(null);
            for (int item : arr){
                tree.addNode(tree.new Node(item));  // 添加节点
            }
            tree.preOrder();  // 前序遍历
        }
    }
    
    class BinarySortTree{
        private Node root;  // 根节点
    
        public BinarySortTree(Node node){
            this.root = node;
        }
        // 添加节点到二叉排序树中
        public void addNode(Node node){
            if (root == null){
                root = node;
            }else{
                root.addNode(node);
            }
        }
        // 中序遍历:左根右
        public void preOrder(){
            if (root != null){
                root.preOrder();
            }
        }
    
        /**
         * 内部类:节点
         */
        class Node{
            int value;
            Node left;  // 指向左子节点
            Node right; // 指向右子节点
    
            public Node(int value){
                this.value = value;
            }
            // 添加节点到二叉排序树中
            public void addNode(Node node){
                if (node != null){
                    if (node.value >= this.value){ // 如果大于当前节点的值
                        if (this.right != null){    // 如果当前节点存在右子节点
                            this.right.addNode(node);	// 右子节点递归添加
                        }else{
                            this.right = node;
                        }
                    }else{
                        if (this.left != null){ // 如果小于当前节点的值
                            this.left.addNode(node);
                        }else{
                            this.left = node;
                        }
                    }
                }
            }
            // 中序遍历:根左右
            public void preOrder(){
                System.out.println(this);   // 根
                if (this.left != null){     // 左子节点
                    this.left.preOrder();
                }
                if (this.right != null){    // 右子节点
                    this.right.preOrder();
                }
            }
            @Override
            public String toString() {
                return "Node{" +
                        "value=" + value +
                        '}';
            }
        }
    }
    

    2.2 删除二叉排序树节点

    【案例描述】

    删除二叉排序树中的指定节点,要求删除节点后仍是一个二叉排序树。

    【思路分析】

    考虑待删除节点有三种情况,每种情况下对节点的删除的具体操作是不同的。下面将分别介绍删除这三种节点的思路:

    1. 待删除节点为叶子节点。

      在这里插入图片描述

      这种情况下的节点删除最简单,只需要找到目标节点以及它的父节点,然后借助父节点删除目标节点即可。

    2. 待删除节点为只有一棵子树的节点。

      在这里插入图片描述

      如果目标节点只有一个子节点,要想删除目标节点之后依然是一个二叉排序树。只需要让目标节点的父节点原来指向目标节点的指针指向目标节点的子节点即可(例如:上图目标节点 3 是节点 7 的左子节点,只需要让节点 7 的左指针改为指向目标节点的子节点 5 即可实现删除目标节点)。

      在实际操作的过程中,需要注意判断下面两点:

      • 目标节点是父节点的左子节点还是右子节点;
      • 目标节点的唯一子节点是左子节点还是右子节点。
    3. 待删除节点为有两棵子树的节点。

      在这里插入图片描述

      如果目标节点有两个子树,则将目标节点的右子树中的最小的节点的信息拷贝至目标节点,然后将最小节点删除,即可实现删除目标节点(例如:上图目标节点为的值 3,它的右子树中最小节点的值为 4,则将目标节点的值修改为 4,然后删除最小节点即可)。

      在实际操作过程中,要注意一点:通过目标节点的右子树中最小节点的父节点才能删除最小节点,因此还需要找到最小节点的父节点。

    【代码实现】

    class BinarySortTree{
    
        private Node root;  // 根节点
    
        public BinarySortTree(Node node){
            this.root = node;
        }
        // 删除指定节点
        public void deleteBST(int key){
            if (root != null){
                if (root.value == key){ // 如果目标节点是根节点,直接删除
                    root = null;
                }else{  // 如果不是根节点,就调用删除方法
                    root.deleteBST(key);
                }
            }
        }
    
        /**
         * 内部类:节点
         */
        class Node{
            int value;  // 节点的值
            Node left;  // 指向左子节点
            Node right; // 指向右子节点
    
            public Node(int value){
                this.value = value;
            }
    
            /**
             * 查找指定节点
             * @param key   指定节点的值
             */
            public Node searchNode(int key) {
                if (this.value == key) {    // 首先判断是否是本节点
                    return this;
                } else {
                    if (this.value > key) { // 如果小于本节点,向左递归
                        if (this.left != null) {    // 如果左节点存在才递归
                            return this.left.searchNode(key);
                        }
                    }else{  // 不是小于,就是大于本节点,向右递归
                        if (this.right != null) {   // 右节点存在才递归
                            return this.right.searchNode(key);
                        }
                    }
                    return null;
                }
            }
    
            /**
             * 查找指定节点的父节点
             * @param key   指定节点的值
             */
            public Node searchParentNode(int key){
                if ((this.left !=null && this.left.value == key) || 
                    (this.right != null && this.right.value == key)){ // 如果当前节点的某个子节点是目标节点
                    return this;    // 返回当前节点
                }else{
                    if (key < this.value && this.left != null){  // 如果目标值小于当前节点
                        return this.left.searchParentNode(key);
                    }else if (key > this.value && this.right != null){  // 如果目标值大于当前节点
                        return this.right.searchParentNode(key);
                    }else{
                        return null;
                    }
                }
            }
    
            /**
             * 删除节点
             * @param key 待删除节点的值
             */
            public boolean deleteBST(int key){
                if (this.value == key){ // 如果等于当前节点,就执行删除节点操作
                    deleteNode(root, key);  // 执行删除操作
                    return true;
                }else{
                    if (key < this.value && this.left != null){  // 如果目标值小于当前节点,就向左子树递归查找
                        return this.left.deleteBST(key);
                    }else if (key > this.value && this.right != null){  // 如果大于当前节点,就向右子树递归查找
                        return this.right.deleteBST(key);
                    }else{
                        return false;
                    }
                }
            }
    
            /**
             * 删除节点的操作过程
             * @param root  根节点
             * @param key   待删除节点的值
             */
            public void deleteNode(Node root, int key){
                Node targetNode = root.searchNode(key);  // 首先找到要删除的节点
                if (targetNode != null){
                    Node parentNode = root.searchParentNode(key);   // 找到待删除节点的父节点
                    if (targetNode.left == null &&  targetNode.right == null){  // 情况一:目标是一个叶子节点
                        if (parentNode.left.value == key){  // 判断目标节点是父节点的左子节点还是右子节点
                            parentNode.left = null; // 直接删除即可
                        }else{
                            parentNode.right = null;
                        }
                    }else if (targetNode.left != null && 
                              targetNode.right != null){ // 情况三:目标节点有两个子树
                        /* 找出目标节点右子树中的最小值 */
                        Node rightTreeNode = targetNode.right;  // 获取目标节点的右子节点
                        if (rightTreeNode.left == null){       // 如果右子节点没有左子树,说明右子节点就是最小节点
                            targetNode.value = rightTreeNode.value; // 将最小节点复制到目标结点
                            targetNode.right = null;    // 删除最小节点
                        }else{  // 如果目标节点的右子节点有左子树,就往下找
                            while (rightTreeNode.left.left != null){    // 要删除最小节点,所以找最小节点的父节点
                                rightTreeNode = rightTreeNode.left;
                            }
                            targetNode.value = rightTreeNode.left.value;
                            rightTreeNode.left = null;
                        }
                    }else{  // 情况二:目标节点只有一个子树
                        if (targetNode.left != null){   // 如果目标节点只有左子树
                            if (parentNode.left != null && parentNode.left.value == key){  // 如果目标节点是父节点的左子树
                                parentNode.left = targetNode.left;  // 让父节点的左指针指向目标节点的左子树
                            }else if (parentNode.right != null && parentNode.right.value == key){  // 如果目标节点是父节点的右子树
                                parentNode.right = targetNode.left; // 让父节点的右指针指向目标节点左子树
                            }
                        }else{  // 如果目标节点只有右子树
                            if (parentNode.left != null && parentNode.left.value == key){  // 如果目标节点是父节点的左子树
                                parentNode.left = targetNode.right;
                            }else if (parentNode.right != null && parentNode.right.value == key){  // 如果目标节点是父节点的右子树
                                parentNode.right = targetNode.right;
                            }
                        }
                    }
                }
            }
            @Override
            public String toString() {
                return "Node{" +
                        "value=" + value +
                        '}';
            }
        }
    }
    

    【附】

    二叉排序树的完整代码请访问我的 Gitee 仓库

    展开全文
  • 二叉搜索树最小绝对差写在前面一、题目简介二、思路三、具体实现五、总结 写在前面   本题正好是关于二叉搜索树,正巧最近看了二叉树的相关知识,故来总结。 一、题目简介   给你一棵所有节点为非负值的二叉...

    力扣easy530.二叉搜索树的最小绝对差

    写在前面

      本题正好是关于二叉搜索树,正巧最近看了二叉树的相关知识,故来总结。

    一、题目简介

      给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。

    输入:
    
       1
        \
         3
        /
       2
    
    输出:
    1
    
    解释:
    最小绝对差为 1,其中 2 和 1 的差的绝对值为 1(或者 2 和 3)。
    

      具体题目点击👉二叉搜索树的最小绝对差 - 力扣

    二、思路

      二叉搜索树的中序遍历为单调不减序列,故思路为中序”+“移动搜索

    三、具体实现

    class Solution {
    public:
    vector<int> vec;
        void inParse(TreeNode* u) {
            //递归结束条件
            if(!u) {
                return;
            }
            inParse(u->left);
            vec.push_back(u->val);
            inParse(u->right);
        }
    
        int getMinimumDifference(TreeNode* root) {
            //中序+移动搜索
            int ans = INT_MAX;
            inParse(root);
            for(int i = 0; i < vec.size() - 1; i++)
                ans = min(ans, vec[i + 1] - vec[i]);
            return ans;
        }
    };
    

      注意:对于vec的定义一定放在类定义内部,不然力扣系统在执行多个例子的时候,会互相干扰(第一次错误提交就是因为把vec定义为了全局变量)。

    五、总结

      这个题简单,没什么可写的,就作此总结。

    展开全文
  • 二叉树与二叉搜索树

    2021-07-15 14:50:16
    本文将从二叉树、二叉搜索树的定义和性质入手,通过代码实现深度认识二分搜索树。 什么是二叉树? 在我们的现实场景中,比如图书馆我们可以根据分类快速找到我们想要找到的书籍。比如我们要找一本叫做《Java编程思想...

    本文将从二叉树、二叉搜索树的定义和性质入手,通过代码实现深度认识二分搜索树。

    什么是二叉树?

    在我们的现实场景中,比如图书馆我们可以根据分类快速找到我们想要找到的书籍。比如我们要找一本叫做《Java编程思想》这本书,我们只需要根据理工科 —> 计算机 —>Java语言分区就可以快速找到我们想要的这本书。这样我们就不需要像数组或者链表这种结构,我们需要遍历一遍才能找到我们想要的东西。再比如,我们所使用的电脑的文件夹目录本身也是一种树的结构。

    从上面的描述我们可知,树这种结构具备天然的高效性可以巧妙的避开我们不关心的东西,只需要根据我们的线索快速去定位我们的目标。所以说树代表着一种高效。

    二叉树定义

    二叉树也是一种动态的数据结构。每个节点只有两个叉,也就是两个孩子节点,分别叫做左孩子,右孩子,而没有一个孩子的节点叫做叶子节点。每个节点最多有一个父亲节点,最多有两个孩子节点(也可以没有孩子节点或者只有一个孩子节点)。

    • 由一个个节点组成,每个节点最多有两个子节点(左右孩子节点没有大小之分)
    • 有且只有一个根节点
    • 每个子树也都是一个二叉树

    大体来说,一个二叉树长这样的:

    file

    然后其中的每个节点用Java代码描述的话大致长这样的:

    class Node<E>{
      E e;
      Node left;
      Node right;
    }
    

    其中E是一个泛型,用来表示我们的节点存储的元素的类型;然后我们用e这个字段来存储元素。其中left和right用来存储我们的左右两个子节点。

    注意点:

    • 一个值为null的变量也可以看做是二叉树。
    • 一个链表可以看做是特殊的二叉树。
    • 一个二叉树可能很“平均”,每个节点的左边的所有节点的数量和右边的所有节点的数量一样多;也可能和畸形,像链表一样。
    • 二叉树具有天然的递归行。

    二叉树的类型

    根据二叉树的节点分布大概可以分为以下三种二叉树:完全二叉树,满二叉树,平衡二叉树。

    满二叉树:从根节点到每一个叶子节点所经过的节点数都是相同的。

    file

    完全二叉树:除去最后一层叶子节点,就是一颗完全二叉树,并且最后一层的节点只能集中在左侧。

    file

    平衡二叉树:平衡二叉树又被称为AVL树(区别于AVL算法),它是一棵二叉树,又是一棵二分搜索树,平衡二叉树的任意一个节点的左右两个子树的高度差的绝对值不超过1,即左右两个子树都是一棵平衡二叉树。

    file

    什么是二分搜索树?

    • 首先它是一颗二叉树,满足上面所说二叉树所有规则和性质;
    • 对于每一个节点:它的值大于左子树任意一个节点的值,并且小于其右子树任意一个节点的值;
    • 存储的元素必须有可比较性;

    二分搜索树大致长这样的:

    file

    也可以是这样的:

    file

    总之,满足上面这个规则的二叉树就是一个二分搜索树。

    二分搜索树的实现

    本文我们的重点是实现一个二分搜索树,那我们规定该二分搜索树应该具备以下功能:使用泛型,并要求该泛型必须实现Comparable接口;基本的增删改查操作。

    基本结构

    通过上面的分析我们可知,如果我们要实现一个二分搜索树,我们需要我们的节点有左右两个孩子节点。

    /**
     * 二分搜索树-存储的数据需具有可比较性,所以泛型需继承Comparable接口
     **/
    public class BinarySearchTree<E extends Comparable<E>> {
    	/**
         * 二分搜索树节点的结构
         */
        private class Node {
            E e;
            Node left, right;
    
            public Node() {
                this(null, null, null);
            }
    
            public Node(E e) {
                this(e, null, null);
            }
    
            public Node(E e, Node left, Node right) {
                this.e = e;
                this.left = left;
                this.right = right;
            }
        }
        /**
         * 根节点
         */
        private Node root;
        /**
         * 表示树里存储的元素个数
         */
        private int size;
        /**
         * 获取树里的元素个数
         * @return 元素个数
         */
        public int size() {
            return size;
        }
        /**
         * 树是否为空
         * @return 为空返回true,否则返回false
         */
        public boolean isEmpty() {
            return size == 0;
        }
    }
    

    添加元素

    在插入元素之前,我们需要明确一件事,那就是是否允许二分搜索树中存在重复元素(含重复元素的话,只需要改变定义为:左子树小于等于节点;或者右子树大于等于节点)。这里我就按照不允许重复元素的情况来处理了。如果在插入过程中,发现了重复元素,那么我们就放弃这次插入。

    基于下面二分搜索树,假设我们希望把31这个元素插入到节点中。那么我们会通过根节点一层一层来到32这个点。我们发现31的值比32小,同时32的左子树为null,所以我们就该把31插入到32的左节点就行了。

    a

    二分搜索树添加元素的非递归写法,和链表很像,只不过链表中不需要与节点进行比较,而树则需要比较后决定是添加到左子树还是右子树。

    具体的实现代码如下:

    /**
     * 向二分搜索树中添加一个新元素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
     */
    private void add(Node node, E e) {
        // 递归的终止条件
        if (e.equals(node.e)) {
            // 不存储重复元素
            return;
        } else if (e.compareTo(node.e) < 0 && node.left == null) {
            // 元素e小于node节点的元素,并且node节点的左孩子为空,所以成为node节点的左孩子
            node.left = new Node(e);
            size++;
            return;
        } else if (e.compareTo(node.e) > 0 && node.right == null) {
            // 元素e大于node节点的元素,并且node节点的右孩子为空,所以成为node节点的右孩子
            node.right = new Node(e);
            size++;
            return;
        }
    
        if (e.compareTo(node.e) < 0) {
            // 元素e小于node节点的元素,往左子树走
            add(node.left, e);
        } else {
            // 元素e大于node节点的元素,往右子树走
            add(node.right, e);
        }
    }
    

    改进添加操作:深入理解递归终止条件

    上面所实现的往二叉树里添加元素的代码虽然是没问题的,但是还有优化的空间。一是在add(E e)方法中对根节点做了判空处理,与后面的方法在逻辑上有些不统一,实际上可以放在后面的方法中统一处理;二是add(Node node, E e)方法中递归的终止条件比较臃肿,可以简化。

    优化后的实现代码如下:

    /**
     * 向二分搜索树中添加一个新元素e
     *
     * @param e 新元素
     */
    public void add2(E e) {
        root = add2(root, e);
    }
    
    /**
     * 向以node为根的二分搜索树中插入元素e,精简后的递归实现
     *
     * @param node
     * @param e
     * @return 返回插入新节点后二分搜索树的根节点
     */
    private Node add2(Node node, E e) {
        // 递归的终止条件
        if (node == null) {
            // node为空时必然是可以插入新节点的
            size++;
            return new Node(e);
        }
    
        if (e.compareTo(node.e) < 0) {
            // 元素e小于node节点的元素,往左子树走
            node.left = add2(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            // 元素e大于node节点的元素,往右子树走
            node.right = add2(node.right, e);
        }
        
        // 相等什么也不做
        return node;
    }
    

    修改递归的终止条件后,我们只需要在节点为空时,统一插入新节点,不需要再判断左右子节点是否为空。这样选择合适的终止条件后,多递归了一层但减少很多不必要的代码

    查找元素

    二分搜索树的核心竞争力就是能够使用二分查找法来查询元素,假设我们要在一颗二分搜索树中查询某一个值是否存在,那么我们只需要从根节点开始:

    • 如果根节点的值就是我们要寻找的值,那么直接返回该节点就行了;
    • 如果根节点的子比我们的目标节点的值大,我们就递归的向左子树查找;
    • 如果根节点的子比我们的目标节点的值小,我们就递归的向右子树查找;

    基本查询操作

    a

    假设我们希望在这个二分搜索树中查找值为32的节点是否存在

    1. 先查看根节点,发现根节点的值是41,大于我们的目标值,那么我们就可以根据二分搜索树的性质直接排除掉根节点右侧的所有的节点,目标值只有可能存在于根节点的左侧。
    2. 然后我们来到41的左节点,也就是20这个节点。我们发现这个节点的值小于32,所有目标值只有可能存在于20的右边。于是我们来到的29这个节点。
    3. 同理我们对29这个节点完成上面的操作,来到了32这个节点。
    /**
     * 查看二分搜索树中是否包含元素e
     */
    public boolean contains(E e) {
        return contains(root, e);
    }
    
    /**
     * 查看以node为根节点的二分搜索树中是否包含元素e,递归实现
     */
    private boolean contains(Node node, E e) {
        if (node == null) {
            return false;
        }
    
        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);
    }
    

    什么是遍历操作?

    ​ 遍历操作就是把所有节点都访问一遍,使得可以对所有节点元素进行操作。在线性结构下,遍历是极其容易的,一个循环就解决了。但是在树结构下就稍微有些麻烦了,因为对于树的遍历操作,两棵子树都要顾及

    二叉树的遍历方式主要有这么几种:前序遍历、中序遍历、后序遍历以及层序遍历

    前序遍历

    前序遍历,所谓前序遍历就是先遍历根节点,然后再遍历左子树和右子树。前序遍历是最自然、最常用的遍历方式。

    前序遍历使用递归实现起来非常的简单,代码如下:

    /**
     * 二分搜索树的前序遍历
     */
    public void preOrder() {
        preOrder(root);
    }
    
    /**
     * 前序遍历以node为根的二分搜索树,递归实现
     */
    private void preOrder(Node node) {
        if (node == null) {
            return;
        }
    
        // 先遍历根节点
        System.out.println(node.e);
    
        // 然后遍历左子树和右子树
        preOrder(node.left);
        preOrder(node.right);
    }
    

    中序遍历

    中序遍历就是先遍历左子树,然后遍历根节点,再遍历右子树。

    具体的实现代码如下:

    /**
     * 二分搜索树的中序遍历
     */
    public void inOrder() {
        inOrder(root);
    }
    
    /**
     * 中序遍历以node为根的二分搜索树,递归实现
     */
    private void inOrder(Node node) {
        if (node == null) {
            return;
        }
    
        // 先遍历左子树
        inOrder(node.left);
        // 然后遍历根节点
        System.out.println(node.e);
        // 最后遍历右子树
        inOrder(node.right);
    }
    

    二分搜索树的中序遍历的特性是可以按照元素从小到大的顺序访问节点,将遍历过程输出就可以看到是有序的。

    后序遍历

    同样的,后序遍历也是换了个顺序,是先遍历左子树,然后遍历右子树,再遍历根节点。

    具体的实现代码如下:

    /**
     * 二分搜索树的后序遍历
     */
    public void postOrder() {
        postOrder(root);
    }
    
    /**
     * 后序遍历以node为根的二分搜索树,递归实现
     */
    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
    
        // 先遍历左子树
        postOrder(node.left);
        // 然后遍历右子树
        postOrder(node.right);
        // 最后遍历根节点
        System.out.println(node.e);
    }
    

    后序遍历通常用于需要先处理左右子树,最后再处理根节点的场景,例如为二分搜索树释放内存(C++)。

    二分搜索树的层序遍历

    了解了前中后序遍历,接下来我们看看二分搜索树的层序遍历。所谓层序遍历就是按照树的层级自根节点开始从上往下遍历,通常根节点所在的层级称为第0层或第1层,我这里习惯称之为第1层。如下图所示:
    file

    当遍历第1层时,访问到的是28这个根节点;遍历第2层时,访问到的是16以及30这个两个节点;遍历第3层时,则访问到的是13、22、29及42这四个节点。

    可以看出层序遍历与前中后序遍历不太一样,前中后序遍历都是先将其中一颗子树遍历到底,然后再返回来遍历另一颗子树,其实这也就是所谓的深度优先遍历,而层序遍历也就是所谓的广度优先遍历

    通常层序遍历会使用非递归的实现,并且会使用一个队列容器作为辅助,所以代码写起来与之前的非递归实现前序遍历非常类似,只不过容器由栈换成了队列。具体的代码实现如下:

    /**
     * 二分搜索树的层序遍历实现
     */
    public void levelOrder() {
        Queue<Node> queue = new LinkedList<>();
        // 根节点入队
        queue.add(root);
        while (!queue.isEmpty()) {
            // 将当前要访问的节点出队
            Node cur = queue.remove();
            System.out.println(cur.e);
    
            // 左右节点入队
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
    }
    

    以上面的那棵树为例,我们也来分析下层序遍历代码的执行过程:

    首先根节点入队
    进入循环,队头元素出队,输出28
    当前出队元素的左节点不为空,将左节点16入队
    当前出队元素的右节点不为空,将右节点30入队
    此时队列不为空,继续循环,队头元素出队,输出16(先进先出)
    当前出队元素的左节点不为空,将左节点13入队
    当前出队元素的右节点不为空,将右节点22入队
    继续循环,队头元素出队,输出30
    当前出队元素的左节点不为空,将左节点29入队
    当前出队元素的右节点不为空,将右节点42入队
    继续循环,队头元素出队,输出13
    当前出队元素的左节点为空,什么都不做
    当前出队元素的右节点为空,什么都不做
    继续循环,队头元素出队,输出22
    重复第12、13步
    继续循环,队头元素出队,输出29
    重复第12、13步
    继续循环,队头元素出队,输出42
    重复第12、13步
    此时栈中没有元素了,为空,跳出循环
    最终的输出为:28 16 30 13 22 29 42
    

    广度优先遍历的意义:

    • 更快的找到问题的解
    • 常用于算法设计中:最短路径

    前序遍历非递归实现

    虽然使用递归实现对树的遍历会比较简单,但通常在实际开发中并不会太多的去使用递归,一是怕数据量大时递归深度太深导致栈溢出,二是为了减少递归函数调用的开销。中序遍历和后序遍历的非递归实现,实际应用不广,所以本小节主要实现前序遍历的非递归实现。

    前序遍历的非递归实现思路有好几种,这里主要介绍一种递归算法转非递归实现的比较通用的思路。理解这种思路后我们也可以将其应用到其他的递归转非递归实现的场景上,这种方法就是自己用额外的容器模拟一下系统栈。具体的代码实现如下:

    /**
     * 二分搜索树的非递归前序遍历实现
     */
    public void preOrderNR() {
        // 使用 java.util.Stack 来模拟系统栈
        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);
            }
        }
    }
    

    以这样一颗树为例,简单描述下以上代码的执行过程:
    file

    首先根节点28入栈
    进入循环,栈顶元素出栈,输出28
    当前出栈元素的右节点不为空,将右节点30压入栈中
    当前出栈元素的左节点不为空,将左节点16压入栈中
    此时栈不为空,继续循环,栈顶元素出栈,输出16(后进先出)
    当前出栈元素的右节点不为空,将右节点22压入栈中
    当前出栈元素的左节点不为空,将左节点13压入栈中
    继续循环,栈顶元素出栈,输出13
    当前出栈元素的右节点为空,什么都不做
    当前出栈元素的左节点为空,什么都不做
    继续循环,栈顶元素出栈,输出22
    重复第9、10步
    继续循环,栈顶元素出栈,输出30
    当前出栈元素的右节点不为空,将右节点42压入栈中
    当前出栈元素的左节点不为空,将左节点29压入栈中
    继续循环,栈顶元素出栈,输出29
    重复第9、10步
    继续循环,栈顶元素出栈,输出42
    重复第9、10步
    此时栈中没有元素了,为空,跳出循环
    最终的输出为:28 16 13 22 30 29 42
    

    删除元素

    删除最大元素和最小元素

    二分搜索树的删除操作是相对比较复杂的,所以我们先来解决一个相对简单的任务,就是删除二分搜索树中的最大元素和最小元素。由于二分搜索树的特性,其最小值就是最左边的那个节点,而最大元素则是最右边的那个节点。

    以下面这棵二分搜索树为例,看其最左和最右的两个节点,就能知道最小元素是13,最大元素是42:

    file

    再来看一种情况,以下这棵二分搜索树,往最左边走只能走到16这个节点,往最右边走只能走到30这个节点,所以最大最小元素不一定会是叶子节点:
    file

    • 在这种情况下,删除最大最小元素时,由于还有子树,所以需要将其子树挂载到被删除的节点上

    我们先来看看如何找到二分搜索树的最大元素和最小元素。代码如下:

    /**
     * 获取二分搜索树的最小元素
     */
    public E minimum() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty!");
        }
    
        return minimum(root).e;
    }
    
    /**
     * 返回以node为根的二分搜索树的最小元素所在节点
     */
    private Node minimum(Node node) {
        if (node.left == null) {
            return node;
        }
    
        return minimum(node.left);
    }
    
    /**
     * 获取二分搜索树的最大元素
     */
    public E maximum() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty!");
        }
        return maximum(root).e;
    }
    
    /**
     * 返回以node为根的二分搜索树的最大元素所在节点
     */
    private Node maximum(Node node) {
        if (node.right == null) {
            return node;
        }
    
        return maximum(node.right);
    }
    

    然后再来实现删除操作,代码如下:

    /**
     * 删除二分搜索树中的最大元素所在节点,并返回该元素
     */
    public E removeMax() {
        E ret = maximum();
        root = removeMax(root);
        return ret;
    }
    
    /**
     * 删除以node为根的二分搜索树中的最大节点
     * 返回删除节点后新的二分搜索树的根
     */
    private Node removeMax(Node node) {
        if (node.right == null) {
            // 如果有左子树,需要将其挂到被删除的节点上
            Node leftNode = node.left;
            node.left = null;
            size--;
    
            return leftNode;
        }
    
        node.right = removeMax(node.right);
        return node;
    }
    
    /**
     * 删除二分搜索树中的最小元素所在节点,并返回该元素
     */
    public E removeMin() {
        E ret = minimum();
        root = removeMin(root);
        return ret;
    }
    
    /**
     * 删除以node为根的二分搜索树中的最小节点
     * 返回删除节点后新的二分搜索树的根
     */
    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;
    }
    

    删除任意元素

    有了上面的基础后,就应该对实现删除二分搜索树的任意元素有一定的思路了。首先,我们来看看在实现过程中会遇到的一些情况,

    第一种情况就是要删除的目标节点只有一个左子树,例如删除下图中的58:
    file

    ​ 在这种情况下,只需要将左子树挂到被删除的目标节点上即可,与删除最大元素的基本逻辑类似

    第二种情况与第一种情况相反,就是要删除的目标节点只有一个右子树:

    file

    ​ 同样的,把右子树挂到被删除的目标节点上即可,与删除最小元素的基本逻辑类似

    第三种情况是要删除的目标节点是一个叶子节点,这种情况直接复用以上任意一种情况的处理逻辑即可,因为我们也可以将叶子节点视为有左子树或右子树,只不过为空而已。

    比较复杂的是第四种情况,也就是要删除的目标节点有左右两个子节点,如下图所示:

    file

    对于这种情况,我们得把58这个节点下的左右两颗子树融合在一起,此时就可以采用1962年,Hibbard提出的Hibbard Deletion方法解决。

    首先,我们将要删除的这个节点称之为 dd,第一步是从 dd 的右子树中找到最小的节点 ss,这个 ss 就是 dd 的后继了。第二步要做的事情就很简单了,将 ss 从原来的树上摘除并将 ss 的右子树指向这个删除后的右子树,然后再将 ss 的左子树指向 dd 的左子树,最后让 dd 的父节点指向 ss,此时就完成了对目标节点 dd 的删除操作。如下图:
    file

    具体的实现代码如下:

    /**
     * 从二分搜索树中删除元素为e的节点
     */
    public void remove(E e) {
        root = remove(root, e);
    }
    
    /**
     * 删除以node为根的二分搜索树中值为e的节点,递归实现
     * 返回删除节点后新的二分搜索树的根
     */
    private Node remove(Node node, E e) {
        if (node == null) {
            return null;
        }
    
        if (e.compareTo(node.e) < 0) {
            // 要删除的节点在左子树中
            node.left = remove(node.left, e);
            return node;
        } else if (e.compareTo(node.e) > 0) {
            // 要删除的节点在右子树中
            node.right = remove(node.right, e);
            return node;
        }
    
        // 找到了要删除的节点
        // 待删除的节点左子树为空的情况
        if (node.left == null) {
            // 如果有右子树,需要将其挂到被删除的节点上
            Node rightNode = node.right;
            node.right = null;
            size--;
    
            return rightNode;
        }
    
        // 待删除的节点右子树为空的情况
        if (node.right == null) {
            // 如果有左子树,需要将其挂到被删除的节点上
            Node leftNode = node.left;
            node.left = null;
            size--;
    
            return leftNode;
        }
    
        // 待删除的节点左右子树均不为空的情况
        // 找到比待删除节点大的最小节点,即待删除节点右子树的最小节点
        Node successor = minimum(node.right);
        // 用这个节点替换待删除节点的位置
        // 由于removeMin里已经维护过一次size了,所以这里就不需要维护一次了
        successor.right = removeMin(node.right);
        successor.left = node.left;
        return successor;
    }
    
    展开全文
  • 算法思想:动态规划实际问题:最优二叉搜索树编写语言:Java问题描述二叉搜索树的定义:满足以下任意两个条件的一个,就可称这棵树为二叉搜索树:它是一棵空树该树是一颗二叉树,非空,且满足下列两个条件:若它的左...
  • 本题要求实现给定二叉搜索树的5种常用操作。 函数接口定义: BinTree Insert( BinTree BST, ElementType X ); BinTree Delete( BinTree BST, ElementType X ); Position Find( BinTree BST, ElementType X ); ...
  • 详解动态规划之“最优二叉搜索树”之前两篇分别讲了动态规划的“钢管切割”和“矩阵链乘法”,感觉到了这一篇,也可以算是收官之作了。其实根据前两篇,到这里,也可以进行一些总结的,我们可以找到一些规律性的东西...
  • 本文实例讲述了Java删除二叉搜索树的任意元素的方法。分享给大家供大家参考,具体如下:一.删除思路分析在删除二叉搜索树的任意元素时,会有三种情况:1.1 删除只有左孩子的节点节点删除之后,将左孩子所在的二叉树...
  • 二叉搜索树的图文详解

    千次阅读 2021-05-14 15:17:46
    二叉搜索树的实现 二叉搜索树的结构 二叉搜素树具备以下性质: 左子树不为空,则左子树上所有节点值都小于根结点值 右子树不为空,则右子树上所有节点值都大于根结点值 左右子树依然具备二叉树的以上性质 ...
  • ​ 二叉查找树 / 二叉搜索树(Binary Search Tree, BST)是一种特殊的二叉树:对于每个父节点,其左子节点的值小于等于父结点的值,其右子节点的值大于等于父结点的值。因此对于一个二叉查找树,我们可以在 O(nlogn)...
  • 最优二叉搜索树

    2021-03-07 23:56:53
    给定N个权值作为N个叶子结点,构造一棵二叉搜索树,若该树的带权路径长度达到最小,称这样的二叉搜索树为最优二叉搜索树。 最优二叉搜索树和最优二叉树的区别,体现在石子归并问题中就是,如果石子是无序的,那就是...
  • 二叉搜索树

    2021-06-09 15:26:07
    什么是二叉搜索树 二叉搜索树对于任何节点x,其左子树中的关键字最大不超过x的关键字。其右子树中的关键字最小不低于x的关键字。如图所示:
  • 我们经常需要查找一个存储在二叉搜索树中的关键字。查找我们使用下面的过程在一棵二叉搜索树中查找一个具有给定关键字的结点。输入一个指向树根的指针和一个关键字kkk,如果这个结点存在,tree_search(x, k)返回一个...
  • 二叉搜索树创建和删除二叉搜索树二叉搜索树的创建二叉搜索树的删除 二叉搜索树 也叫二叉排序树,它的递归定义为: 1.如果树T的左子树非空,则左子树中的所有结点的值小于T的根节点的值; 2.如果树T的右子树非空,则...
  • 给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。 注意:本题与 530题相同 示例 1: 输入:root = [4,2,6,1,3] 输出:1 示例 2: 输入:root = [1,0,48,null,null,12,49] 输出:1 ...
  • 文章目录一、 二叉搜索树概念二、二叉搜索树操作2.1 查找2.2 插入2.3 删除2.4 验证三、 二叉搜索树的应用四、二叉搜索树的性能分析 一、 二叉搜索树概念 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有...
  • 最优二叉搜索树 最优二叉搜索树 问题描述 问题分析 代码 问题描述 二叉搜索树我们都知道,左子树结点的值都小于根结点,右子树结点的值都大于根节点。如果某个结点没有左子树或右子树,那么在对应的位置上加一个虚...
  • 这是我的第一篇 算法导论(Introduction to Algorithms, Third Edition) 读书笔记. 旨在记录重点, 强化自己对算法的学习效果. ...二叉搜索树 可以使用一个 链表数据结构(linked data structure ) 表
  • 二叉搜索树,首先上定义: 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 而二叉搜索树最有用的性质就是,对其中序遍历可以得到一个...
  • 给定一个有序整数数组,元素各不相同且按升序排列,编写一个算法,创建一棵高度最小二叉搜索树。 示例 给定有序数组: [-10,-3,0,5,9],一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个平衡二叉搜索树...
  • 二叉搜索树的实现3.1 结构3.2 销毁二叉搜索树(析构函数)3.3 查找3.4 插入3.4.1 代码实现3.4.2 补充说明 一. 二叉搜索树的概念 二叉搜索树也称为二叉排序树。它或者是一个空树或者是有如下性质的二叉树: 左子树...
  • 二叉搜索树 参考:https://blog.csdn.net/qq_35644234/article/details/64516551 (这位大佬真的强啊,很喜欢他的风格) 4.1 二叉搜索树定义 二叉搜索树(BST,Binary Search Tree),也称为二叉查找树或二叉排序树 ...
  • 二叉搜索树 二叉搜索树(BST,Binary Search Tree)也称二叉排序树或二叉查找树 ①非空左子树的所有键值小于其根结点的键值 ②非空右子树的所有键值大于其根结点的键值 ③左、右子树都是二叉搜索树 二叉搜索树的...
  • 给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。 预备知识: 二叉搜索树具有如下性质: 结点的左子树只包含小于当前结点的数。 结点的右子树只...
  • Java二叉搜索树

    2021-03-01 20:56:25
    Java二叉搜索树二叉搜索树的概念原理结构性质时间复杂度二叉搜索树的操作查找插入删除(难点)性能分析算法实现 二叉搜索树的概念 二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空...
  • 二叉搜索树的最近公共祖先450. 删除二叉搜索树中的节点669. 修剪二叉搜索树700. 二叉搜索树中的搜索701. 二叉搜索树中的插入操作基于中序遍历类题目 基本操作类题目 235. 二叉搜索树的最近公共祖先 给定一个二叉...
  • 一、二叉搜索树的定义 二叉搜索树 (BST) 递归定义为具有以下属性的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 35,396
精华内容 14,158
关键字:

最小二叉搜索树