【数据结构】树和二叉树以及经典例题

1.树的基本概念

在认识数据结构里的“树”之前，我们先来看看现实生活中的树
1

我们现实生活中的树有什么特征？
有树根，有枝节，有叶子。
编程来源于生活，我们数据结构里的“树”也有这些特征。
1
2
3

概念如下：

树是一种非线性数据结构，它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。 ————百度百科

注意 “非线性” 这个词，表面了该数据结构是一对多或者多对多的关系
1

1.1 树的特点

1.有一个特殊的结点，称为根结点，根节点没有前驱结点（就是最上面的结点）
2.除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

我们主要来看第二条：
“互不相交的集合”，就是结点之间不能有交集
如下图
1
2
3

其实，仔细观察的话，我们可以发现，这个说法还能换成：
树结构之间不能有回路
1
2

这几个点之间产生了回路，所以就不是树。
1

再来看看第二个特点：子树
就是，一颗大的树里面，包含了多个子树。
如图：
1
2
3

图中圈出来就是子树，这些子树还能被分为更小的子树。
1

再来刨析第二条特点：
每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
“前驱”“后继”是什么？
在上面树的逻辑图中   （仔细想想什么是逻辑图，后面会讲）
我们可以看到，除了第一层，和最后一层外，中间的结点都连了相应的结点
连接在上面的叫“前驱”，连接在下面的叫“后继”
根结点只有后继没有前驱，
最后一层的结点（也叫叶结点），只有前驱，没有后继
所以总结为：
 子树的根结点只有一个前驱，有0个或者多个后继
1
2
3
4
5
6
7
8
9
10

1.2 树的一些相关概念

概念挺多的，我们这里划分一下分为常用的和不常用的
1

常用的并且重要的：
1

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I...等节点为叶节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推
树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
1
2
3
4
5
6
7
8
9
10

不常用的：
非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G...等节点为分支节点
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
森林：由m（m>0）棵互不相交的树的集合称为森林；（就是两棵或多棵互不相干的树）
1
2
3
4

1.3 树的表示

还记得我们上面提到的逻辑图吗？
1

这种能形象地表示数据结构的图，我们称为逻辑图。
比如链表，那种两个结点之间有箭头指向的图，以及我们上面这幅图都是逻辑图
其最大的特点就是，这种图是我们想象出来的，真实结构并不是这样的
所以在计算机里，我们还要利用更底层的数据结构实现它。
比如利用数组实现树，或者链表实现树
1
2
3
4
5

1.3.1 那种结构表示树最优？（不是二叉树，就是普通的树）

如果仅仅是一棵普普通通的二叉树，每个结点最多连两个结点，那么我们分别创建
左孩子指针和右孩子指针就能表示了。
但是，这里是树，也就是说一个结点可能连接两个以上的结点，
可能3个，4个，5个，6个...
那我们可以利用“指针数组”去实现这么多的结点。
但是，有没有更好的方法？
同样只利用两个指针就可以一直表示下去？
思考一下
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
//孩子兄弟表示法
typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

有牛人发明了这种“孩子兄弟表示法”，能完美实现2个度以上的树
1

一个结点里存有 “孩子”和“兄弟”
“孩子“指向自己的下一个结点，没有”兄弟“就不用指向
”孩子“指向的结点，也有自己的”孩子“和”兄弟“，然后可以可以无限表示下去了。
仔细感受一下，牛人发明的这种方法，不得不佩服。
1
2
3
4

1.4 树在实际中的运用（表示文件系统的目录树结构）

2. 二叉树（重点！！！）

2.1 二叉树的概念

在上面学习了树以后，我们接下来看看二叉树
二叉树：由一个根节点加上两棵别称为左子树和右子树的二叉树组成
1
2

注意：
1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

对于任意的二叉树都是由以下几种情况复合而成的：
1
2
3
4
5

2.2 特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是
说，如果一个二叉树的层数为K，且结点总数是2^k - 1 ，则它就是满二叉树。
（注意是结点总数）
1
2
3

记住这个层数为k时，结点总数是 $2^k-1$，非常重要，后面需要用到

2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
1

简单理解完全二叉树就是，最后一层可以满，满了就是满二叉树。也可以不满，不满的话起码结点从左往右排好
1

2.3 完全二叉树的范围

因为满二叉树是一种的特殊的完全二叉树，所以完全二叉树的总结点最多是 $2^k-1$,(k表示总层数)

那么最少是多少？
最少的话是不是最后一层只有一个结点？
既然这样的话，那么最后一层的上一层总结点数是不是 $2^{k-1}-1$
那么上一层是满的，再 +1 是不是就是最后一层加一个结点
答案就是:
$2^{k-1}$

所以完全二叉树的总结点范围就是
$2^{k-1}$ ~ $2^k-1$ （k是总层数）

2.4 二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有$2^{(i-1)}$个结点. (注意这里是某一层上的最多结点)

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是$2^h-1$ (就是满二叉树)

3. 对任何一棵二叉树, 如果度为0其叶结点个数为n₀ , 度为2的分支结点个数为n₂ ,则有 n₀＝ n₂ ＋1（度为0的结点永远比度为2的结点多1，这个结论也挺重要的，自己画图理解一下）

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log₂(n+1)

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
   5.1 若i>0，i 位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
   5.2 若2i+1，左孩子序号：2i+1，2i+1>=n否则无左孩子
   5.3 若2i+2，右孩子序号：2i+2，2i+2>=n否则无右孩子

光看性质是不是觉得很乱，我们来做几道题就明白了。
1