数据结构|《画解数据结构》三张动图，三十张彩图，画解二叉搜索树 (建议收藏) 树|二叉树|二叉搜索树|算法

本文已收录于专栏 《画解数据结构》
前言

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

「二叉搜索树」

文章图片

二叉树的查找
二叉搜索树的删除
二叉搜索树的插入
点击我跳转末尾 获取粉丝专属《算法和数据结构》源码，以及获取博主的联系方式。

文章目录

前言
一、二叉树的概念
- 1、二叉树的性质
- 2、特殊二叉树
- - 1）斜树
  - 2）满二叉树
  - 3）完全二叉树
- 3、二叉树的性质
- - 1）性质1
  - 2）性质2
  - 3）性质3
  - 4）性质4
二、二叉树的存储
- 1、顺序表存储
- - 1）完全二叉树
  - 2）非完全二叉树
  - 3）稀疏二叉树
- 2、链表存储
三、二叉树的遍历
- 1、前序遍历
- - 1）算法描述
  - 2）源码详解
- 2、中序遍历
- - 1）算法描述
  - 2）源码详解
- 3、后序遍历
- - 1）算法描述
  - 2）源码详解
四、二叉搜索树的概念
- 1、定义
- 2、用途
- 3、数据结构
- 4、结点创建
五、二叉搜索树的操作
- 1、查找
- - 1）算法原理
  - 2）动图演示
  - 3）源码详解
- 2、插入
- - 1）算法原理
  - 2）动图演示
  - 3）源码详解
- 3、删除
- - 1）算法原理
  - 2）动图演示
  - 3）源码详解
- 4、构造
- - 1）算法原理
  - 2）源码详解
六、二叉搜索树的遍历
- 1、先序遍历
- 2、中序遍历
- 3、后序遍历
七、二叉搜索树的总结
粉丝专属福利

一、二叉树的概念 ??在学习二叉搜索树之前，我们首先需要了解下什么是二叉树。
1、二叉树的性质 ??二叉树是一种树，它有如下几个特征：
????1）每个结点最多 2 棵子树，即每个结点的孩子结点个数为 0、1、2；
????2）这两棵子树是有顺序的，分别叫：左子树和右子树；
????3）如果只有一棵子树的情况，也需要区分顺序，如图所示：

文章图片

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

文章图片

?? c c c 为a a a 的右子树；
2、特殊二叉树 1）斜树
??所有结点都只有左子树的二叉树被称为左斜树。

文章图片

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

文章图片

??斜树有点类似线性表，所以线性表可以理解为一种特殊形式的树。
2）满二叉树
??对于一棵二叉树，如果它的所有根结点和内部结点都存在左右子树，且所有叶子结点都在同一层，这样的树就是满二叉树。

文章图片

??满二叉树有如下几个特点：
????1）叶子结点一定在最后一层；
????2）非叶子结点的度为 2；
????3）深度相同的二叉树，满二叉树的结点个数最多，为2 h ? 1 2^h-1 2h?1（其中h h h 代表深度）。
3）完全二叉树
??对一棵具有n n n 个结点的二叉树按照层序进行编号，如果编号i i i 的结点和同样深度的满二叉树中的编号i i i 的结点在二叉树中位置完全相同，则被称为完全二叉树。

文章图片

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

文章图片

3、二叉树的性质 ??接下来我们来看下，二叉树有哪些重要的性质。
1）性质1

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

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

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

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

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

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

文章图片

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

??【性质4】具有n n n 个结点的完全二叉树的深度为? l o g 2 n ? + 1 \lfloor log_2n \rfloor + 1 ?log2?n?+1。

??由【性质2】可得，深度为h h h 的二叉树至多有 2 h ? 1 2^{h}-1 2h?1 个结点。所以，假设一棵树的深度为h h h，它的结点数为n n n，则必然满足：
n ≤ 2 h ? 1 n \le 2^{h}-1 n≤2h?1??由于是完全二叉树，它一定比深度为h ? 1 h-1 h?1 的结点数要多，即：
2 h ? 1 ? 1 < n 2^{h-1}-1 \lt n 2h?1?12 h ? 1 ≤ n < 2 h 2^{h-1} \le n \lt 2^h 2h?1≤n<2h??然后，对不等式两边取以2为底的对数，得到：h ? 1 ≤ l o g 2 n < h h-1 \le log_2n \lt h h?1≤log2?n 二、二叉树的存储 1、顺序表存储 ??二叉树的顺序存储就是指利用数组对二叉树进行存储。结点的存储位置即数组下标，能够体现结点之间的逻辑关系，比如父结点和孩子结点之间的关系，左右兄弟结点之间的关系等等。
1）完全二叉树
??来看一棵完全二叉树，我们对它进行如下存储。

文章图片

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

下标	0	1	2	3	4	5	6	7	8	9	10	11	12
d a t a data data	? - ?	a a a	b b b	c c c	d d d	e e e	f f f	g g g	h h h	i i i	j j j	k k k	l l l

??这里为了方便，我们把数组下标为 0 的位置给留空了。这样一来，当知道某个结点的下标x x x，就可以知道它左右儿子的下标分别为2 x 2x 2x 和2 x + 1 2x+1 2x+1；反之，当知道某个结点的下标x x x，也能知道它父结点的下标为? x 2 ? \lfloor \frac x 2 \rfloor ?2x??。
2）非完全二叉树
??对于非完全二叉树，只需要将对应不存在的结点设置为空即可。

文章图片

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

下标	0	1	2	3	4	5	6	7	8	9	10	11	12
d a t a data data	? - ?	a a a	b b b	c c c	d d d	e e e	f f f	g g g	? - ?	? - ?	? - ?	k k k	l l l

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

文章图片

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

下标	0	1	2	3	4	5	6	7	8	9	10	11	12
d a t a data data	? - ?	a a a	b b b	c c c	d d d	? - ?	? - ?	g g g	h h h	? - ?	? - ?	? - ?	? - ?

??于是，我们可以采取链表进行存储。
2、链表存储 ??二叉树每个结点至多有两个孩子结点，所以对于每个结点，设置一个数据域和两个指针域即可，指针域分别指向左孩子结点和右孩子结点。

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

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

文章图片

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

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

1、前序遍历 1）算法描述

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

文章图片

??前序遍历的结果如下： a b d g h c e f i abdghcefi abdghcefi。

2）源码详解

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

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

2、中序遍历 1）算法描述

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

文章图片

??中序遍历的结果如下： g d h b a e c i f gdhbaecif gdhbaecif。

2）源码详解

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

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

3、后序遍历 1）算法描述

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

文章图片

??后序遍历的结果如下： g h d b e i f c a ghdbeifca ghdbeifca。

2）源码详解

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

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

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

文章图片

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

文章图片

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

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

( 1 ) (1) (1) 二叉搜索树结点的值，注意，这里的类型其实可以是任意类型，只要这种类型支持关系运算符的比较即可，本文为了把问题简单话，一律采用整数进行讲解。
( 2 ) (2) (2) 二叉搜索树结点的左儿子结点的指针，没有左儿子结点时，值为NULL；
( 3 ) (3) (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 ) (1) (1) BSTFind这个函数用于查找以now为根结点的树中是否存在值为val这个结点；
( 2 ) (2) (2) 空树是不可能存在值为val的结点的，直接返回false；
( 3 ) (3) (3) 一旦发现有值为val的结点，直接返回true；
( 4 ) (4) (4) val的值小于树根结点的值，说明val对应的结点不在根结点，也不在右子树上，则递归返回左子树的查找结果；
( 5 ) (5) (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 ) (1) (1) BSTInsert函数用于将值为val的结点插入到以root为根结点的子树中；
( 2 ) (2) (2) 如果是空树，则创建一个值为val的结点并且返回；
( 3 ) (3) (3) val的值等于树根结点的值，无须执行插入，直接返回根结点；
( 4 ) (4) (4) val的值小于树根结点的值，那么插入位置一定在左子树，递归执行插入左子树的过程，并且返回插入结果作为新的左子树；
( 5 ) (5) (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 ) (1) (1) BSTFindMin：查找root为根的树中，值最小的那个结点的值，根据二叉搜索树的性质，如果左子树存在，则必然存在更小的值，递归搜索左子树；如果左子树不存在，则根结点的值必然最小，直接返回，具体实现见下文；
( 2 ) (2) (2) BSTDelete：在root为根的树中，删除值为val的结点，是我们需要实现的删除接口，具体实现见下文；
( 3 ) (3) (3) Delete：在root为根的树中，将根结点删除，并且使得剩下的树还是二叉搜索树，具体实现见下文；

3.2）查找最小结点

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

( 1 ) (1) (1) 如果左子树存在，则递归调用左子树的查找最小结点接口；
( 2 ) (2) (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 ) (1) (1) 如果为空树，则直接返回空结点；
( 2 ) (2) (2) 如果需要删除的结点，是这棵树的根结点，则直接调用接口Delete，下文会介绍它的实现；
( 3 ) (3) (3) 如果需要删除的结点的值小于树根结点的值，则需要删除的结点必定在左子树上，递归调用左子树的删除，并且将返回值作为新的左子树的根结点；
( 4 ) (4) (4) 如果需要删除的结点的值大于树根结点的值，则需要删除的结点必定在右子树上，递归调用右子树的删除，并且将返回值作为新的右子树的根结点；
( 5 ) (5) (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 ) (1) (1) 如果左子树为空，则用右子树做为新的树根；
( 2 ) (2) (2) 如果右子树为空，则用左子树作为新的树根；
( 3 ) (3) (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 ) (1) (1) 初始化空树；
( 2 ) (2) (2) 根据数组给定顺序执行插入树的操作；

??插入过程需要明确一点，就是如果给定的数组是严格递增，或者严格递减，就会导致每次插入都要遍历树的所有结点，这样就使得整个插入过程的时间复杂度变成了O ( n 2 ) O(n^2) O(n2)，改善的方法有几种：
??方法1：随机将数组打乱顺序，再执行插入；
??方法2：每次插入后，变换成平衡树，对于平衡树相关内容，下篇文章会详细讲解；
六、二叉搜索树的遍历 1、先序遍历 ??给定一个某个二叉搜索树的先序遍历序列，构造出一棵二叉搜索树，方法如下：
??1）首先，考虑先序遍历的特点：先访问根结点，再依次访问左右子树；所以，第一个结点一定是根结点；
??2）然后，数组往后遍历的过程中，遇到的所有小于当前根结点的结点，都必然是左子树上的结点，后面的结点必然是右子树的（当然，如果检测到后面的结点有比这个根结点小的，则这个序列无法构造出一棵二叉搜索树）；
??3）遍历找到左右子树的分界点后，就可以进行左右子树递归计算了，注意递归时返回构造完的子树的根结点。
2、中序遍历 ??二叉搜索树的中序遍历是最常用的，一棵二叉搜索树的中序遍历是一个递增序列。
??递增序列是存在单调性的，所以可以利用这个特性，在有效的时间内找出这棵树的第k k k 大结点。
3、后序遍历 ??给定一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果，方法如下：
??1）从后序遍历的定义出发，先左子树，再右子树，最后根结点。所以，这个序列的最后一个元素，一定是根结点，且所有小于它的元素作为左子树，所有大于它的元素作为右子树。
??2）如果能够分成这样两部分，则递归计算左右子树；
??3）否则，在出现第一个大于最后一个元素的情况下，又出现小于最后一个元素的情况，则表示这是一种非法情况，直接返回false。
七、二叉搜索树的总结 ??纵观二叉搜索树的查找、插入和删除。完全取决于二叉搜索树的形状，如果是完全二叉树或者接近完全二叉树，则这三个过程都是O ( l o g 2 n ) O(log_2n) O(log2?n) 的，如果是斜树，则三个过程近似操作线性表，为O ( n ) O(n) O(n)。

文章图片

文章图片

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

??给自己树立一个「目标」是非常重要的，有「目标」才会有「方向」，有「目标」才会有「动力」，有「目标」才会有「人生的意义」。有了「目标」，再做一定的「规划」，并且「坚持」做下去，我相信，「成功的一天终会到来」。
??说了这么多，只是想建立一个「愿景」。这个「愿景」就是 —— 「群人皆佬，共赴大厂」。
??光有「愿景」是不够的，我们需要「付诸实际行动」，任何一项大工程都不是「一朝一夕」能够完成的，「制定计划」 是尤为重要的事情。例如，想要学好算法，至少需要掌握一门语言，可以是 C、C++、Python、Java。这里强烈推荐 C语言，因为俗话说得好：

「学好C语言，走遍天下都不怕」
??为了 「督促大家」更好的学习，所以我建立了一些团队供各位 「技术交流」之用，因为团队大了不好带，所以初期就把团队分好组，这样每个团队都能有很好的照顾，比一下子吃成胖子要好得多，当然每个团队我都会挑选一些 「精英人员」作为领袖，以便更好的来达成我们共同的 「愿景」。
??这主要是提供给各位志想同道合之士交流沟通的一个桥梁，起到 「媒介」的作用。让同样和我 「志同道合」的人积极投身到这个事业中来，将祖国的 「算法」发扬光大，背靠祖国，面向国际，强我国威，壮我河山！
??用 「算法」改变世界， 「让天下没有难学的算法」。
??我不希望你是以粉丝的身份加入我的团队，我更希望我们是 「合伙人」，只是没有任何利益上的输送，我也不会在里面做任何产品的推销，所以， 「广告商勿扰」。
??大多都是正在上大学的学生，我不想赚学生的钱，毕竟能上学已属不易。而且，很多大学生的激情， 「引燃」了我自己的 「青春」，所以我很喜欢和大学生交流，有时候也会给他们一些面试以及职场上的建议，久而久之，就成了 「无话不谈」的好朋友。
??正是这一点，让我激发了认识更多的人的欲望，毕竟， 「活到老学到老」， 「靠近优秀的人，使自己变得更加优秀」，始终保持一个学习的态度，多沟通交流，让自己 「更加强大」！
??各位成员是有明确共同目标的，这样才能共同成长，大致特征如下：
?? ( 1 ) (1) (1) 有强烈欲望「想要学好C语言」的人
?? ( 2 ) (2) (2) 有强烈欲望「想要学好C++ 」的人
?? ( 3 ) (3) (3) 有强烈欲望「想要学好数据结构」的人
?? ( 4 ) (4) (4) 有强烈欲望「想学好算法」的人
?? ( 5 ) (5) (5) 有强烈欲望「想进大厂」的人
??如果你满足以上任意一点，那么，我们就是志同道合的人啦！请通过 「博主的CSDN主页」 找到联系方式，联系博主。

文章图片

让天下没有难学的算法
C语言免费动漫教程，和我一起打卡！ 《光天化日学C语言》
入门级C语言真题汇总 《C语言入门100例》
几张动图学会一种数据结构 《画解数据结构》
组团学习，抱团生长 《算法入门指引》
竞赛选手金典图文教程 《夜深人静写算法》 ??这篇文章的主要目的是讲解二叉搜索树的一些基础概念，以及和二叉搜索树相关的一些经典算法。但是实际学习过程还是需要看个人的毅力和坚持。下图代表的是 LeetCode 经典的二叉搜索树的题集，其中树是很重要的一个章节，涉及了诸多算法，希望可以供读者参考和学习。
文章图片