数据结构二叉树怎么画_线索二叉树的画法口诀

前言

  目前本专栏正在进行优惠活动，在博主主页添加博主好友（好友位没有满的话），可以获取 付费专栏优惠券。

  我们知道，「 顺序表 」 可以 「 快速索引 」 数据，而 「 链表 」 则可以快速的进行数据的「 插入 和 删除 」。那么，有没有一种数据结构，可以快速的实现 「 增 」「 删 」「 改 」「 查 」 呢？
  本文，我们就来聊一下一种 「 树形 」 的数据结构，它既有链表的快速插入与删除的特点，又有顺序表快速查找的优势。它就是：

「 二叉搜索树 」








二叉树的查找





二叉搜索树的删除





二叉搜索树的插入



点击我跳转末尾 获取
粉丝专属 《算法和数据结构》源码，以及获取博主的联系方式。

一、二叉树的概念

  在学习二叉搜索树之前，我们首先需要了解下什么是二叉树。

1、二叉树的性质

  二叉树是一种树，它有如下几个特征：
    1）每个结点最多 2 棵子树，即每个结点的孩子结点个数为 0、1、2；
    2）这两棵子树是有顺序的，分别叫：左子树 和 右子树；
    3）如果只有一棵子树的情况，也需要区分顺序，如图所示：

  $b$ 为 $a$ 的左子树；

  $c$ 为 $a$ 的右子树；

2、特殊二叉树

1）斜树

  所有结点都只有左子树的二叉树被称为左斜树。

  所有结点都只有右子树的二叉树被称为右斜树。

  斜树有点类似线性表，所以线性表可以理解为一种特殊形式的树。

2）满二叉树

  对于一棵二叉树，如果它的所有根结点和内部结点都存在左右子树，且所有叶子结点都在同一层，这样的树就是满二叉树。

  满二叉树有如下几个特点：
    1）叶子结点一定在最后一层；
    2）非叶子结点的度为 2；
    3）深度相同的二叉树，满二叉树的结点个数最多，为 $2^h-1$（其中 $h$ 代表深度）。

3）完全二叉树

  对一棵具有 $n$ 个结点的二叉树按照层序进行编号，如果编号 $i$ 的结点和同样深度的满二叉树中的编号 $i$ 的结点在二叉树中位置完全相同，则被称为 完全二叉树。

  满二叉树一定是完全二叉树，而完全二叉树则不一定是满二叉树。
  完全二叉树有如下几个特点：
    1）叶子结点只能出现在最下面两层。
    2）最下层的叶子结点一定是集中在左边的连续位置；倒数第二层如果有叶子结点，一定集中在右边的连续位置。
    3）如果某个结点度为 1，则只有左子树，即 不存在只有右子树 的情况。
    4）同样结点数的二叉树，完全二叉树的深度最小。

  如下图所示，就不是一棵完全二叉树，因为 5 号结点没有右子树，但是 6 号结点是有左子树的，不满足上述第 2 点。

3、二叉树的性质

  接下来我们来看下，二叉树有哪些重要的性质。

1）性质1

  【性质1】二叉树的第 $i(i\ge 1)$ 层上至多有 $2^{i-1}$ 个结点。

  既然是至多，就只需要考虑满二叉树的情况，对于满二叉树而言，当前层的结点数是上一层的两倍，第一层的结点数为 1，所以第 $i$ 的结点数可以通过等比数列公式计算出来，为 $2^{i-1}$。

2）性质2

  【性质2】深度为 $h$ 的二叉树至多有$2^h-1$ 个结点。

  对于任意一个深度为 $h$ 的二叉树，满二叉树的结点数一定是最多的，所以我们可以拿满二叉树进行计算，它的每一层的结点数为 $1$、$2$、$4$、$8$、…、$2^{h-1}$。
  利用等比数列求和公式，得到总的结点数为：
$$1+2+4+...+2^{h-1}=2^h-1$$

3）性质3

  【性质3】对于任意一棵二叉树 $T$，如果叶子结点数为 $x_0$，度为 2 的结点数为 $x_2$，则$$x_0=x_2+1$$

  令 $x_1$ 代表度 为 1 的结点数，总的结点数为 $n$，则有：
$$n=x_0+x_1+x_2$$
  任意一个结点到它孩子结点的连线我们称为这棵树的一条边，对于任意一个非空树而言，边数等于结点数减一，令边数为 $e$，则有：
$$e=n-1$$

  对于度为 1 的结点，可以提供 1 条边，如图中的黄色结点；对于度为 2 的结点，可以提供 2 条边，如图中的红色结点。所以边数又可以通过度为 1 和 2 的结点数计算得出：$$e=x_1+2x_2$$  联立上述三个等式，得到：$$e=n-1=x_0+x_1+x_2-1=x_1+2x_2$$  化简后，得证：
$$x_0=x_2+1$$

4）性质4

  【性质4】具有 $n$ 个结点的完全二叉树的深度为 $\lfloor lo{g}_{2}n\rfloor +1$。

  由【性质2】可得，深度为 $h$ 的二叉树至多有$2^h-1$ 个结点。所以，假设一棵树的深度为 $h$，它的结点数为 $n$，则必然满足：
$$n\le 2^h-1$$  由于是完全二叉树，它一定比深度为 $h-1$ 的结点数要多，即：
$$2^{h-1}-1<n$$  将上述两个不等式，稍加整理，得到：
$$2^{h-1}\le n<2^h$$  然后，对不等式两边取以2为底的对数，得到： $$h-1\le lo{g}_{2}n<h$$  这里，由于 $h$ 一定是整数，所以有：$$h=\lfloor lo{g}_{2}n\rfloor +1$$

二、二叉树的存储

1、顺序表存储

  二叉树的顺序存储就是指利用数组对二叉树进行存储。结点的存储位置即数组下标，能够体现结点之间的逻辑关系，比如父结点和孩子结点之间的关系，左右兄弟结点之间的关系 等等。

1）完全二叉树

  来看一棵完全二叉树，我们对它进行如下存储。

  编号代表了数组下标的绝对位置，映射后如下：

2）非完全二叉树

  对于非完全二叉树，只需要将对应不存在的结点设置为空即可。

  编号代表了数组下标的绝对位置，映射后如下：

3）稀疏二叉树

  对于较为稀疏的二叉树，就会有如下情况出现，这时候如果用这种方式进行存储，就比较浪费内存了。

  编号代表了数组下标的绝对位置，映射后如下：

2、链表存储

  二叉树每个结点至多有两个孩子结点，所以对于每个结点，设置一个 数据域 和 两个 指针域 即可，指针域 分别指向 左孩子结点 和 右孩子结点。

typedef struct TreeNode { 
   
    DataType data;
    struct TreeNode *left;   // (1)
    struct TreeNode *right;  // (2)
}TreeNode;

• $(1)$ left指向左孩子结点；
• $(2)$ right指向右孩子结点；
  

三、二叉树的遍历

  二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点访问一次且仅被访问一次。
  对于线性表的遍历，要么从头到尾，要么从尾到头，遍历方式较为单纯，但是树不一样，它的每个结点都有可能有两个孩子结点，所以遍历的顺序面临着不同的选择。
  二叉树的常用遍历方法有以下四种：前序遍历、中序遍历、后序遍历、层序遍历。
  我们用 void visit(TreeNode *root)这个函数代表访问某个结点，这里为了简化问题，访问结点的过程就是打印对应数据域的过程。如下代码所示：

void visit(TreeNode *root) { 
   
    printf("%c", root->data);
}

1、 前序遍历

1）算法描述

  【前序遍历】如果二叉树为空，则直接返回。否则，先访问根结点，再递归前序遍历左子树，再递归前序遍历右子树。

  前序遍历的结果如下：$abdghcefi$。

2）源码详解

void preorder(TreeNode *root) { 
   
    if(root == NULL) { 
   
        return ;            // (1)
    }
    visit(root);            // (2)
    preorder(root->left);   // (3)
    preorder(root->right);  // (4)
}

• $(1)$ 待访问结点为空时，直接返回；
• $(2)$ 先访问当前树的根；
• $(3)$ 再前序遍历左子树；
• $(4)$ 最后前序遍历右子树；

2、 中序遍历

1）算法描述

  【中序遍历】如果二叉树为空，则直接返回。否则，先递归中序遍历左子树，再访问根结点，再递归中序遍历右子树。

  中序遍历的结果如下：$gdhbaecif$。

2）源码详解

void inorder(TreeNode *root) { 
   
    if(root == NULL) { 
   
        return ;            // (1)
    }
    inorder(root->left);    // (2)
    visit(root);            // (3)
    inorder(root->right);   // (4)
}

• $(1)$ 待访问结点为空时，直接返回；
• $(2)$ 先中序遍历左子树；
• $(3)$ 再访问当前树的根；
• $(4)$ 最后中序遍历右子树；

3、 后序遍历

1）算法描述

  【后序遍历】如果二叉树为空，则直接返回。否则，先递归后遍历左子树，再递归后序遍历右子树，再访问根结点。

  后序遍历的结果如下：$ghdbeifca$。

2）源码详解

void postorder(TreeNode *root) { 
   
    if(root == NULL) { 
   
        return ;            // (1)
    }
    postorder(root->left);  // (2)
    postorder(root->right); // (3)
    visit(root);            // (4)
}

• $(1)$ 待访问结点为空时，直接返回；
• $(2)$ 先后序遍历左子树；
• $(3)$ 再后序遍历右子树；
• $(4)$ 再访问当前树的根；

四、二叉搜索树的概念

1、定义

  二叉搜索树，又称为二叉排序树，二叉查找树，它满足如下四点性质：
    1）空树是二叉搜索树；
    2）若它的左子树不为空，则左子树上所有结点的值均小于它根结点的值；
    3）若它的右子树不为空，则右子树上所有结点的值均大于它根结点的值；
    4）它的左右子树均为二叉搜索树；

  如图所示，对于任何一棵子树而言，它的根结点的值一定大于左子树所有结点的值，且一定小于右子树所有结点的值。

2、用途

  从二叉搜索树的定义可知，它的前提是二叉树，并且采用了递归的方式进行定义，它的结点间满足一个偏序关系，左子树根结点的值一定比父结点小，右子树根结点的值一定比父结点大。
  正如它的名字所说，构造这样一棵树的目的是为了提高搜索的速度，如果对二叉搜索树进行中序遍历，我们可以发现，得到的序列是一个递增序列。

3、数据结构

  我们用孩子表示法来定义一棵二叉搜索树的结点。如下：

struct TreeNode { 
   
    int val;                 // (1)
    struct TreeNode *left;   // (2)
    struct TreeNode *right;  // (3)
};

• $(1)$ 二叉搜索树结点的值，注意，这里的类型其实可以是任意类型，只要这种类型支持 关系运算符 的比较即可，本文为了把问题简单话，一律采用整数进行讲解。
• $(2)$ 二叉搜索树结点的左儿子结点的指针，没有左儿子结点时，值为NULL；
• $(3)$ 二叉搜索树结点的右儿子结点的指针，没有右儿子结点时，置为NULL；

4、结点创建

  结点创建就是给结点分配一块内存，并且填充它的数据域和指针域，然后返回这个结点。C语言实现如下：

 struct TreeNode* createNode(int val) { 
    
     struct TreeNode* node = (struct TreeNode*) malloc( sizeof(struct TreeNode) );
     node->val = val;
     node->left = NULL;
     node->right = NULL;
     return node;
 }

五、二叉搜索树的操作

1、查找

  二叉搜索树的查找指的是：在树上查找某个数是否存在，存在返回true，不存在返回false。

1）算法原理

  对于要查找的数val，从根结点出发，总共四种情况依次判断：
    1）若为空树，直接返回false；
    2）val的值 等于 树根结点的值，则直接返回true；
    3）val的值 小于 树根结点的值，说明val对应的结点不在根结点，也不在右子树上，则递归返回左子树的 查找 结果；
    4）val的值 大于 树根结点的值，说明val对应的结点不在根结点，也不在左子树上，则递归返回右子树的 查找 结果；

2）动图演示

  如图所示，代表的是从一个二叉搜索树中查找一个值为 3 的结点。一开始， 3 比根结点 5 小，于是递归访问左子树；还是比子树的根结点 4 小，于是继续递归访问左子树；这时候比根结点 2 大，于是递归访问右子树，正好找到值为 3 的结点，回溯结束查找。

3）源码详解

bool BSTFind(struct TreeNode* root, int val) { 
       // (1) 
    if(root == NULL) { 
   
        return false;                             // (2) 
    }
    if(root->val == val) { 
   
        return true;                              // (3) 
    } 
    if(val < root->val) { 
   
        return BSTFind(root->left, val);          // (4)
    }else { 
   
        return BSTFind(root->right, val);         // (5)
    }
}

• $(1)$ BSTFind这个函数用于查找以now为根结点的树中是否存在值为val这个结点；
• $(2)$ 空树是不可能存在值为val的结点的，直接返回false；
• $(3)$ 一旦发现有值为val的结点，直接返回true；
• $(4)$ val的值 小于 树根结点的值，说明val对应的结点不在根结点，也不在右子树上，则递归返回左子树的 查找 结果；
• $(5)$ val的值 大于 树根结点的值，说明val对应的结点不在根结点，也不在左子树上，则递归返回右子树的 查找 结果；

2、插入

  二叉搜索树的插入指的是：将给定的值生成结点后，插入到树上的某个位置，并且保持这棵树还是二叉搜索树。

1）算法原理

  对于要插入的数val，从根结点出发，总共四种情况依次判断：
    1）若为空树，则创建一个值为val的结点并且返回；
    2）val的值 等于 树根结点的值，无须执行插入，直接返回根结点；
    3）val的值 小于 树根结点的值，那么插入位置一定在 左子树，递归执行插入左子树的过程，并且返回插入结果作为新的左子树；
    4）val的值 大于 树根结点的值，那么插入位置一定在 右子树，递归执行插入右子树的过程，并且返回插入结果作为新的右子树；

2）动图演示

  如图所示，代表的是将一个值为 3 的结点插入到一个二叉搜索树中。一开始， 3 比根结点 5 小，于是递归插入左子树；还是比子树的根结点 4 小，于是继续递归插入左子树；这时候比根结点 2 大，于是递归插入右子树，右子树为空，则直接生成一个值为 3 的结点，回溯结束插入。

3）源码详解

struct TreeNode* BSTInsert(struct TreeNode* root, int val){ 
    // (1)
    if(root == NULL) { 
                                 
        return createNode(val);                             // (2)
    }
    if(val == root->val) { 
   
        return root;                                        // (3)
    }
    if(val < root->val) { 
                                      // (4)
        root->left = BSTInsert(root->left, val);  
    }else { 
                                                    // (5)
        root->right = BSTInsert(root->right, val);          
    }
    return root;
}

• $(1)$ BSTInsert函数用于将值为val的结点插入到以root为根结点的子树中；
• $(2)$ 如果是空树，则创建一个值为val的结点并且返回；
• $(3)$ val的值 等于 树根结点的值，无须执行插入，直接返回根结点；
• $(4)$ val的值 小于 树根结点的值，那么插入位置一定在 左子树，递归执行插入左子树的过程，并且返回插入结果作为新的左子树；
• $(5)$ val的值 大于 树根结点的值，那么插入位置一定在 右子树，递归执行插入右子树的过程，并且返回插入结果作为新的右子树；

3、删除

  二叉搜索树的删除指的是：在树上删除给定值的结点。

1）算法原理

  删除值为val的结点的过程，从根结点出发，总共四种情况依次判断：
    1）空树，不存在结点直接返回空树；
    2）val的值 小于 树根结点的值，则需要删除的结点一定不在右子树上，递归调用删除左子树的对应结点；
    3）val的值 大于 树根结点的值，则需要删除的结点一定不在左子树上，递归调用删除右子树的对应结点；
    4）val的值 等于 树根结点的值，相当于是要删除根结点，这时候又要分三种情况：
      4.1）当前树只有左子树，则直接将左子树返回，并且释放当前树根结点的空间；
      4.2）当前树只有右子树，则直接将右子树返回，并且释放当前树根结点的空间；
      4.3）当左右子树都存在时，需要在右子树上找到一个值最小的结点，替换新的树根，而其它结点组成的树作为它的子树，并且在子树中删掉这个最小的结点，而这一步删除的过程正是继续递归调用结点删除的过程；

2）动图演示

  如图所示，下图展示的是，从这棵树删除根结点 5 的过程。首先，由于它有左右儿子结点，所以这个过程，根结点并不是真正的删除。而是从右子树中找到最小的结点 6，替换根结点，并且从根结点为 7 的子树中删除 6 的过程。由于 6 没有子结点所以这个过程就直接结束了。

3）源码详解

3.1）接口简介
  在介绍二叉搜索树的结点删除算法前，我们首先需要知道以下四个接口：

int BSTFindMin(struct TreeNode* root);                       // (2)
struct TreeNode* BSTDelete(struct TreeNode* root, int val);  // (3)
struct TreeNode* Delete(struct TreeNode* root);              // (4)

• $(1)$ BSTFindMin：查找root为根的树中，值最小的那个结点的值，根据二叉搜索树的性质，如果左子树存在，则必然存在更小的值，递归搜索左子树；如果左子树不存在，则根结点的值必然最小，直接返回，具体实现见下文；
• $(2)$ BSTDelete：在root为根的树中，删除值为val的结点，是我们需要实现的删除接口，具体实现见下文；
• $(3)$ Delete：在root为根的树中，将根结点删除，并且使得剩下的树还是二叉搜索树，具体实现见下文；

3.2）查找最小结点

int BSTFindMin(struct TreeNode* root) { 
   
    if(root->left)
        return BSTFindMin(root->left);  // (1)
    return root->val;                   // (2)
}

• $(1)$ 如果左子树存在，则递归调用左子树的查找最小结点接口；
• $(2)$ 如果左子树不存在，则当前根结点的值一定是最小的，直接返回接口；

3.3）删除给定结点

struct TreeNode* BSTDelete(struct TreeNode* root, int val){ 
   
    if(NULL == root) { 
   
        return NULL;                                  // (1)
    }
    if(val == root->val) { 
   
        return Delete(root);                          // (2)
    }
    else if(val < root->val) { 
   
        root->left = BSTDelete(root->left, val);      // (3)
    }else if(val > root->val) { 
   
        root->right = BSTDelete(root->right, val);    // (4)
    }
    return root;                                      // (5)
}

• $(1)$ 如果为空树，则直接返回空结点；
• $(2)$ 如果需要删除的结点，是这棵树的根结点，则直接调用接口Delete，下文会介绍它的实现；
• $(3)$ 如果需要删除的结点的值 小于 树根结点的值，则需要删除的结点必定在左子树上，递归调用左子树的删除，并且将返回值作为新的左子树的根结点；
• $(4)$ 如果需要删除的结点的值 大于 树根结点的值，则需要删除的结点必定在右子树上，递归调用右子树的删除，并且将返回值作为新的右子树的根结点；
• $(5)$ 最后，返回当前树的根结点；

3.4）删除给定二叉搜索树的根结点，并且返回新的树根

struct TreeNode* Delete(struct TreeNode* root) { 
   
    struct TreeNode *delNode, *retNode;
    if(root->left == NULL) { 
             // (1)
        delNode = root, retNode = root->right, free(delNode);
    }else if(root->right == NULL) { 
      // (2)
        delNode = root, retNode = root->left, free(delNode);
    }else { 
                              // (3)
        retNode = (struct TreeNode*) malloc (sizeof(struct TreeNode));
        retNode->val = BSTFindMin(root->right);
        retNode->right = BSTDelete(root->right, retNode->val);
        retNode->left = root->left;
    }
    return retNode;
}

• $(1)$ 如果左子树为空，则用右子树做为新的树根；
• $(2)$ 如果右子树为空，则用左子树作为新的树根；
• $(3)$ 否则，当左右子树都为非空时，利用BSTFindMin，从右子树上找出最小的结点，作为新的根，并且在右子树中删除对应的结点，删除过程就是递归调用BSTDelete的过程；

4、构造

  二叉搜索树的构造就是：给定一个数组序列，构造出一个棵二叉搜索树。

1）算法原理

  原理比较简单，一开始是一棵空树，然后遍历数组，对每个元素生成一个结点，不断执行插入操作，并且返回新的树根，就完成了构造的过程。

2）源码详解

struct TreeNode* BSTConstruct(int *vals, int valSize) { 
   
    int i;
    struct TreeNode* root = NULL;         // (1)
    for(i = 0; i < valSize; ++i) { 
   
        root = BSTInsert(root, vals[i]);  // (2)
    }
    return root;
}

• $(1)$ 初始化空树；
• $(2)$ 根据数组给定顺序执行插入树的操作；

  插入过程需要明确一点，就是如果给定的数组是严格递增，或者严格递减，就会导致每次插入都要遍历树的所有结点，这样就使得整个插入过程的时间复杂度变成了 $O(n^2)$，改善的方法有几种：
  方法1：随机将数组打乱顺序，再执行插入；
  方法2：每次插入后，变换成平衡树，对于平衡树相关内容，下篇文章会详细讲解；

六、二叉搜索树的遍历

1、先序遍历

  给定一个某个二叉搜索树的先序遍历序列，构造出一棵二叉搜索树，方法如下：
  1）首先，考虑先序遍历的特点：先访问根结点，再依次访问左右子树；所以，第一个结点一定是根结点；
  2）然后，数组往后遍历的过程中，遇到的所有小于当前根结点的结点，都必然是左子树上的结点，后面的结点必然是右子树的（当然，如果检测到后面的结点有比这个根结点小的，则这个序列无法构造出一棵二叉搜索树）；
  3）遍历找到左右子树的分界点后，就可以进行左右子树递归计算了，注意递归时返回构造完的子树的根结点。

2、中序遍历

  二叉搜索树的中序遍历是最常用的，一棵二叉搜索树的中序遍历是一个递增序列。
  递增序列是存在单调性的，所以可以利用这个特性，在有效的时间内找出这棵树的第 $k$ 大结点。

3、后序遍历

  给定一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果，方法如下：
  1）从后序遍历的定义出发，先左子树，再右子树，最后根结点。所以，这个序列的最后一个元素，一定是根结点，且所有小于它的元素作为左子树，所有大于它的元素作为右子树。
  2）如果能够分成这样两部分，则递归计算左右子树；
  3）否则，在出现第一个大于 最后一个元素的情况下，又出现小于 最后一个元素的情况，则表示这是一种非法情况，直接返回false。

七、二叉搜索树的总结

  纵观二叉搜索树的查找、插入 和 删除。完全取决于二叉搜索树的形状，如果是完全二叉树或者接近完全二叉树，则这三个过程都是 $O(lo{g}_{2}n)$ 的，如果是斜树，则三个过程近似操作线性表，为 $O(n)$。

  有关 🌳 二叉搜索树 🌳 的的内容到这里就完全结束了，如果还有什么疑问，可以添加作者微信咨询。
  有关🌳《画解数据结构》🌳的源码均开源，链接如下：《画解数据结构》