树|??《画解数据结构》三十张彩图，画解二叉树?? C|二叉树

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

??「数据结构」 和 「算法」 是密不可分的，两者往往是「相辅相成」的存在，所以，在学习 「数据结构」 的过程中，不免会遇到各种「算法」。
??数据结构常用的操作一般为：「增」「删」「改」「查」。
??这篇文章，作者将用 「 30张彩图」 来阐述一种 「树形」 的数据结构

「二叉树」

文章图片

??这篇文章的主要目的是讲解二叉树的一些基础概念，以及和二叉树相关的一些经典遍历算法。但是实际学习过程还是需要看个人的毅力和坚持。下图代表的是 LeetCode 经典的二叉搜索树的题集，其中树是很重要的一个章节，涉及了诸多算法，希望可以供读者参考和学习。

文章图片

点击我跳转末尾 获取粉丝专属《算法和数据结构》源码。

文章目录

前言
一、树的概念
- 1、树的定义
- - 1）树
  - 2）空树
  - 3）子树
- 2、结点的定义
- - 1）根结点
  - 2）叶子结点
  - 3）内部结点
- 3、结点间关系
- - 1）孩子结点
  - 2）父结点
  - 3）兄弟结点
- 4、树的深度
- 5、森林的定义
二、树的表示法
- 1、父亲表示法
- - 1）存储方式
  - 2）源码详解
  - 3）图片剖析
  - 4）结构剖析
- 2、孩子表示法
- - 1）存储方式
  - 2）源码详解
  - 3）图片剖析
  - 4）结构剖析
- 3、左儿子右兄弟
- - 1）存储方式
  - 2）源码详解
  - 3）图片剖析
  - 4）结构剖析
三、二叉树的概念
- 1、二叉树的性质
- 2、特殊二叉树
- - 1）斜树
  - 2）满二叉树
  - 2）完全二叉树
- 3、二叉树的性质
- - 1）性质1
  - 2）性质2
  - 3）性质3
  - 4）性质4
四、二叉树的存储
- 1、顺序表存储
- - 1）完全二叉树
  - 2）非完全二叉树
  - 3）稀疏二叉树
- 2、链表存储
五、二叉树的遍历
- 1、前序遍历
- - 1）算法描述
  - 2）源码详解
- 2、中序遍历
- - 1）算法描述
  - 2）源码详解
- 3、后序遍历
- - 1）算法描述
  - 2）源码详解
- 4、层序遍历
- - 1）算法描述
粉丝专属福利

一、树的概念 1、树的定义 1）树
??树是n ( n ≥ 0 ) n(n \ge 0) n(n≥0) 个结点的有限集合。当n > 0 n \gt 0 n>0 时，它是一棵非空树，满足如下条件：
????1）有且仅有一个特定的结点，称为根结点R o o t Root Root；
????2）除根结点外，其余结点分为m m m 个互不相交的有限集合T 1 T_1 T1?、 T 2 T_2 T2?、 … … …… ……、 T m T_m Tm?，其中每一个T i ( 1 ≤ i ≤ m ) T_i (1 \le i \le m) Ti?(1≤i≤m) 又是一棵树，并且为根结点R o o t Root Root 的子树。如图所示，代表的是一棵以a a a 为根结点的树。

文章图片

2）空树
??当n = 0 n = 0 n=0，也就是0 0 0 个结点的情况也是树，它被称为空树。
3）子树
??树的定义用到了递归的思想。即树的定义中还是用到了树的概念，如图所示， T 1 T_1 T1? 和T 2 T_2 T2? 就是结点a a a 的子树。结点d d d、 g g g、 h h h、 i i i 组成的树又是结点b b b 的子树等等。

文章图片

??子树的个数没有限制，但是它们一定是互不相交的，如下图所示的就不是树。因为在这两个图中， a a a 的子树都有相交的边。

文章图片

2、结点的定义 ??树的结点包含一个数据域和m m m 个指针域用来指向它的子树。结点的种类分为：根结点、叶子结点、内部结点。结点拥有子树的个数被称为结点的度。树中各个结点度的最大值被称为树的度。
1）根结点
??一棵树的根结点只有一个。
2）叶子结点
??度为 0 的结点被称为叶子结点或者终端结点。叶子结点的不指向任何子树。
3）内部结点
??除了根结点和叶子结点以外的结点，被称为内部结点。

文章图片

??如上图所示，红色结点 为根结点，蓝色结点 为内部结点，黄色结点 为叶子结点。
3、结点间关系 1）孩子结点
??对于某个结点，它的子树的根结点，被称为该结点的孩子结点。

文章图片

??如上图所示，黄色结点 d 是 红色结点 b 的孩子结点。
2）父结点
??而该结点被称为孩子结点的父结点。

文章图片

??如上图所示，蓝色结点 a 是 红色结点 b 的父结点。
3）兄弟结点
??同一父结点下的孩子结点，互相称为兄弟结点。

文章图片

??如上图所示，绿色结点 c 和 红色结点 b 互为兄弟结点。
4、树的深度 ??结点的层次从根结点开始记为第 1 层，如果某结点在第i i i 层，则它的子树的根结点就在第i + 1 i+1 i+1 层，树中结点的最大层次称为树的深度。
??如下图所示，代表的是一棵深度为 4 的树。

文章图片

5、森林的定义 ??森林是m m m 棵互不相交的树的集合，对于树的每个结点而言，其子树集合就是森林。
??如图所示， b b b 和c c c 两棵子树组成的集合就是一个森林。

文章图片

二、树的表示法 1、父亲表示法 1）存储方式
??除了根结点以外，树上的每个结点都会有且仅有一个父结点。所以，我们可以将每个结点定义成结构体，总共两个成员：数据域和父结点域。并且把每个结点连续的存储到结构体数组中，父结点域指向的是数组下标，当没有父结点时，值为? 1 -1 ?1。
2）源码详解

#define MAXN 1024// (1) #define DataType int// (2) typedef struct{DataType data; // (3) int parent; // (4) }TreeNode; typedef struct{TreeNode nodes[MAXN]; // (5) int root; // (6) int n; // (7) }Tree;

( 1 ) (1) (1) MAXN代表了最多允许的结点数量；
( 2 ) (2) (2) DataType表示结点数据域的类型；
( 3 ) (3) (3) data代表了树结点TreeNode的数据域；
( 4 ) (4) (4) parent代表了树结点的父结点域，它是Tree这个结构体中nodes[]数组的下标；
( 5 ) (5) (5) nodes[MAXN]存储了树的所有结点，是一个数组，可以通过下标进行索引；
( 6 ) (6) (6) root代表了这棵树的根结点的下标；
( 7 ) (7) (7) n代表当前有多少树结点；

3）图片剖析
??下图代表了一棵完整的树，[0]代表第 0 号结点，它的数据域为a a a，其中 0 为数组下标；[1]代表第 1 号结点，它的数据域为b b b，以此类推。

文章图片

??结构体数组存储如下：

下标	data	parent
0	a a a	? 1 -1 ?1
1	b b b	0 0 0
2	c c c	0 0 0
3	d d d	1 1 1
4	e e e	2 2 2
5	f f f	2 2 2
6	g g g	3 3 3
7	h h h	3 3 3
8	i i i	3 3 3

4）结构剖析
??这种存储结构中，通过结点获取父结点的时间复杂度为O ( 1 ) O(1) O(1)。但是，如果想要知道某个结点有哪些孩子结点，则必须遍历整棵树才行。
2、孩子表示法 1）存储方式
??父亲表示法无法知道某个结点有哪些孩子结点，所以我们可以对它进行一个改进，将孩子结点存储下来，并且需要记录下每个结点有几个孩子结点。
??也就是说，我们可以对每个结点定义成结构体，总共四个成员：数据域、孩子结点数量域、孩子结点数组。
2）源码详解

typedef struct{DataType data; int childCount; // (1) int childs[MAXN]; // (2) }TreeNode;

( 1 ) (1) (1) childCount记录下当前这个结点有多少个孩子结点；
( 2 ) (2) (2) childs[i]则代表第i i i 个孩子结点在Tree的结点列表nodes[]中的下标；

3）图片剖析
??同样是这样一棵树，[0]代表第 0 号结点，它的数据域为a a a，其中 0 为数组下标；[1]代表第 1 号结点，它的数据域为b b b，以此类推。

文章图片

??得到的结构体数组如下：

下标	data	childCount	childs
0	a a a	2 2 2	[ 1 , 2 ] [1,2] [1,2]
1	b b b	1 1 1	[ 3 ] [3] [3]
2	c c c	2 2 2	[ 4 , 5 ] [4,5] [4,5]
3	d d d	3 3 3	[ 6 , 7 , 8 ] [6,7,8] [6,7,8]
4	e e e	0 0 0	[ ] [] []
5	f f f	0 0 0	[ ] [] []
6	g g g	0 0 0	[ ] [] []
7	h h h	0 0 0	[ ] [] []
8	i i i	0 0 0	[ ] [] []

4）结构剖析
??这种存储结构中，通过结点获取孩子结点的均摊时间复杂度为O ( 1 ) O(1) O(1)。但是，如果想要知道某个结点有的父结点是哪个，则必须遍历整棵树才行。
??所以，我们一般可以将父亲表示法和孩子表示法混用，这样，在知道某个结点的情况下，都能快速得到它的父结点和子结点。
??但是这种表示法的空间时间复杂度为O ( n 2 ) O(n^2) O(n2)，当n n n 较大时，并不是很友好。
3、左儿子右兄弟 1）存储方式
??对于任意一棵树，每个结点的第一个孩子结点如果存在就一定是唯一的，它的右兄弟结点如果存在也是唯一的。因此，对于每个结点，我们可以设置两个域，分别代表第一个孩子结点和右兄弟结点。
2）源码详解

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

( 1 ) (1) (1) left代表该结点的第一个孩子结点在Tree的结点列表nodes[]中的下标；
( 2 ) (2) (2) right代表该结点的右兄弟结点在Tree的结点列表nodes[]中的下标；；

3）图片剖析
??还是这样一棵树，[0]代表第 0 号结点，它的数据域为a a a，其中 0 为数组下标；[1]代表第 1 号结点，它的数据域为b b b，以此类推。

文章图片

??得到的结构体数组如下（其中? - ? 代表空）：

下标	data	left	right
0	a a a	1 1 1	? - ?
1	b b b	3 3 3	2 2 2
2	c c c	4 4 4	? - ?
3	d d d	6 6 6	? - ?
4	e e e	? - ?	5 5 5
5	f f f	? - ?	? - ?
6	g g g	? - ?	7 7 7
7	h h h	? - ?	8 8 8
8	i i i	? - ?	? - ?

4）结构剖析
??这种结构，解决了空间时间复杂度的问题，当知道某个结点时，首先访问l e f t left left 结点，然后一直访问r i g h t right right 结点直到空，就能获取当前结点的所有孩子结点。如果想获取父结点，可以再增加一个parent父结点域。
??这种表示法的另外一个好处是：将任意的树转换成了二叉树。这样就可以利用二叉树的性质来处理这棵树了。
??二叉树才是本文的重点，接下来重点介绍二叉树的内容。
三、二叉树的概念 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 代表深度）。
2）完全二叉树
??对一棵具有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) 再访问当前树的根；

4、层序遍历 1）算法描述

??【层序遍历】如果二叉树为空，则直接返回。否则，依次从树的第一层开始，从上至下逐层遍历。在同一层中，按从左到右的顺序对结点逐个访问。

??层序遍历就是一个广度优先搜索，对广搜有兴趣的小伙伴，可以参考如下文章：夜深人静写算法（十）- 单向广搜。
??关于 二叉树 的内容到这里就结束了。如果还有不懂的问题，可以 「通过作者电脑版主页」找到作者的「联系方式」 ，随时线上沟通。
??有关《画解数据结构》 的源码均开源，链接如下：《画解数据结构》

??相信看我文章的大多数都是「大学生」，能上大学的都是「精英」，那么我们自然要「精益求精」，如果你还是「大一」，那么太好了，你拥有大把时间，当然你可以选择「刷剧」，然而，「学好算法」，三年后的你自然「不能同日而语」。
??那么这里，我整理了「几十个基础算法」 的分类，点击开启：
《算法入门指引》
??如果链接被屏蔽，或者有权限问题，可以私聊作者解决。
??大致题集一览：

文章图片

文章图片

??为了让这件事情变得有趣，以及「照顾初学者」，目前题目只开放最简单的算法 「枚举系列」 （包括：线性枚举、双指针、前缀和、二分枚举、三分枚举），当有一半成员刷完 「枚举系列」 的所有题以后，会开放下个章节，等这套题全部刷完，你还在群里，那么你就会成为「夜深人静写算法」专家团 的一员。
??不要小看这个专家团，三年之后，你将会是别人 望尘莫及 的存在。如果要加入，可以联系我，考虑到大家都是学生， 没有「主要经济来源」，在你成为神的路上，「不会索取任何」。