当前位置 博文首页 > Change_Improve的博客：数据结构——树-基本知识点（第六章）
目录
1. 树的定义
1.1 结点分类
1.2 结点间关系
1.3 树的其他相关概念
2. 树的抽象数据类型
3. 树的存储结构
3.1 双亲表示法
3.2 孩子表示法
3.3 孩子兄弟表示法
4. 二叉树的定义
4.1 二叉树特点
4.2 特殊二叉树
5. 二叉树的性质
5.1 二叉树性质 1
5.2 二叉树性质 2
5.3 二叉树性质 3
5.4 二叉树性质 4
5.5 二叉树性质5
6. 二叉树的存储结构
6.1 二叉树的顺序存储结构
6.2 二叉链表
7. 遍历二叉树
7.1 二叉树遍历原理
7.2 二叉树遍历方法
7.3 前序遍历算法
7.4 中序遍历算法
7.5 后续遍历算法
7.6 推导遍历结果（给出两种推导另外一种）
8. 二叉树的建立
9. 线索二叉树
9.1 线索二叉树原理
9.2 线索二叉树结构实现
10. 树、森林与二叉树的转换
10.1 树转换为二叉树
10.2 森林转换为二叉树
10.3 二叉树转换为树
10.4 二叉树转换为森林
10.5 树与森林的遍历
11. 赫夫曼树及其应用
11.1 赫夫曼树
11.2 赫夫曼树定义与原理
11.3 赫夫曼编码
12. 总结
?树：树 (Tree)是 n ( n ≥ 0) 个结点的有限集。n=0 时称为空树。在任意一棵非空树中：(1) 有且仅有一个特定的称为根(Root) 的结点；(2) 当 n>1 时，其余结点可分为 m (m＞0) 个互不相交的有限集
、
、......... 、
，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree)。
?????? 树：树 (Tree)是 n ( n ≥ 0) 个结点的有限集。n=0 时称为空树。在任意一棵非空树中：(1) 有且仅有一个特定的称为根(Root) 的结点；(2) 当 n>1 时，其余结点可分为 m (m＞0) 个互不相交的有限集、、......... 、 ，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree)。如下图所示：
?????? 对于树的定义还还需要强调两点：
?????? 1. n>0（结点个数）时根结点是唯一的，不可能存在多个根结点，别和现实中的大树混在一起，现实中的树有很多根须，那是真实的树。数据结构中的树只能有一个根结点。
?????? 2. m>0（除根结点的结点数）时，子树的个数没有限制，但它们一定是互不相交的。像下图所示的两个结构就不符合树的定义，因为它们都有相交的子树。
?????? 树的结点包含一个数据元素及若干个指向其子树的分支。结点拥有的子树数称为结点的度（Degree）。度为 0 的结点称为叶结点（Leaf）或终端结点；度不为 0 的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。如下图所示，因为这棵树的结点的度的最大值是结点 D 的度，为 3，所以树的度也为 3。
?????? 结点的子树的根称为该结点的孩子（Child），相应地，该结点称为孩子的双亲（Parent）。同一个双亲的孩子之间互称兄弟（Sibling）。结点的祖先是从根到该结点所经分支的所有结点。下图所示中，对于 H 来说，D、B、A 都是它的祖先。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。下图所示，B 的子孙有 D、G、H、I。
?????? 结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第L层，则其子树的根就在第 L+1 层。其双亲在同一层的结点互为堂兄弟。显然下图所示中的 D、E、F 是堂兄弟，而 G、H、I、J 也是。树中结点的最大层次称为树的深度（Depth）或高度，当前树的深度为 4 。
?????? 如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
?????? 森林（Forest）是m（m≥0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。
?????? 对比线性表与树的结构，它们有很大的不同，如下图所示：
| 线性结构 | 树结构 |
| 第一个数据元素：无前驱 | 根结点：无双亲，唯一 |
| 最后一个数据元素：无后继 | 叶结点：无孩子，可以多个 |
| 中间元素：一个前驱一个后继 | 中间结点：一个双亲多个孩子 |
?????? 树的一些基本和常用操作：
ADT 树（tree）
Data
树是由一个根结点和若干课子树构成。树中结点具有相同数据类型及层次关系。
Operation
InitTree(*T)：构成空树 T。
DestroyTree(*T)：销毁树 T。
CreateTree(*T,Definition)：按 definition 中给出的树的定义来构造树。
ClearTree(*T)：若树 T 存在，则将树 T 清为空树。
TreeEmpty(T)：若 T 为空树，返回 true，否则返回 false。
TreeDepth(T)：返回 T 的深度。
Root(T)：返回 T 的根结点。
Value(T,cur_e)：cur_e 是树T中一个结点，返回此结点的值。
Assign(T,cur_e,value)：给树 T 的结点 cur_e 赋值为 value。
Parent(T,cur_e)：若 cur_e 是树 T 的非根结点，则返回它的双亲，否则返回空。
LeftChild(T,cur_e)：若 cur_e 是树 T 的非叶结点，否则返回它的最左孩子，否则返回空。
RightSlibling(T,cur_e)：若 cur_e 有右兄弟，则返回它的右兄弟，否则返回空。
InsertChild(*T,*p,i,c)：其中 p 指向树 T 的某个结点，i 为所指结点 p 的度加上 1，
非空树 c 与 T 不相交，操作结果为插入 c 为树 T 中 p 指结点的第 i 棵子树。
DeleteChild(*T,*p,i)：其中 p 指向树 T 的某个结点，i 为所指结点 p 的度，
操作结果为删除 T 中 p 所指结点的第 i 棵子树。
endADT?????? 树中某个结点的孩子可以有多个，这就意味着，无论按何种顺序将树中所有结点存储到数组中，结点的存储位置都无法直接反应逻辑关系，简单的顺序存储结构是不能满足树的实现要求的。
?????? 不过充分利用顺序存储和链式存储结构的特点，可以完全实现对树的存储结构的表示。这里将介绍三种不同的表示法：双亲表示法、孩子表示法、孩子兄弟表示法。
?????? 除了根结点外，其余每个结点，它不一定有孩子，但是一定有且仅有一个双亲。
?????? 我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。也就是说，每个结点除了知道自己是谁外，还知道它的双亲在哪里。结点结构如下图所示：
?????? 其中 data 是数据域，存储结点的数据信息。 parent 是指针域，存储该结点的双亲在数组中的下标。
?????? 以下是双亲表示法的结点结构定义代码：
//树的双亲表示法结点结构定义
#define MAX_TREE_SIZE 100 //结点数组的大小
typedef int TElemType; //根结点的数据类型，此处定位整型
typedef struct PTNode //结点结构
{
TElemType data; //结点数据
int parent; //双亲位置
}PTNode;
typedef struct //树结构
{
PTNode nodes[MAX_TREE_SIZE]; //结点数组
int r, n; //根的位置和结点数
}PTree;?????? 有了这样的结构定义，就可以实现双亲表示法了。由于根结点是没有双亲的，所以我们约定根结点的位置域设置为 -1 ，这也就意味着，我们所有的结点都存有它的双亲的位置。如下图所示的树结构和树双亲表示所示。
?????? 这样的存储结构，我们可以根据结点的 parent 指针很容易找到它的双亲结点，所用的时间复杂度为 O(1) ，直到 parent 为 -1 时，表示找到了树结点的根，可是要是知道结点的孩子是什么，只能遍历整个结构才可以。
?????? 此时是比较麻烦的，我们可以增加一个结点最左边孩子的域，不妨叫它长子域，这样就可以很容易得到结点的孩子。如果没有孩子的结点，这个长子域就设置为 -1 ，如下表所示：
?????? 对于有 0 个或 1 个孩子结点来说，这样的结构是解决了要找结点孩子的问题了。甚至是有 2 个孩子，知道了长子是谁，另一个当然就是次子了。
?????? 另外一个问题，我们很关注兄弟之间的关系，双亲表示法无法体现这样的关系，我们可以增加一个右兄弟域来体现兄弟关系，也就是说，每个结点如果它存在右兄弟，则记录右兄弟的下标。同样的，如果右兄弟不存在，则赋值为 -1 ，如下表所示：
?????? 但如果结点的孩子很多，超过了 2 个。我们又关注结点的双亲、又关注结点的孩子、还关注结点的兄弟，而且对时间遍历要求还比较高，那么我们还可以把此结构扩展为有双亲域、长子域、再有右兄弟域。存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理，取决于基于该存储结构的运箅是否适合、是否方便，时间复杂度好不好等。注意也不是越多越好，有需要时再设计相应的结构。就像再好听的音乐，不停反复听上千遍也会腻味，再好看的电影，一段时间反复看上百遍，也会无趣。
?????? 换一种完全不同的考虑方法。由于树中每个结点可能有多棵子树，可以考虑用多重链表表示法。即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，我们把这种方法叫做多重链表表示法。不过，树的每个结点的度，也就是它的孩子个数是不同的。所以可以设计两种方案来解决。
?????? 方案一
?????? 一种是指针域的个数就等于树的度，树的度是树各个结点度的最大值。其结构如表所示：
?????? 其中 data 是数据域。child1 到 childd 是指针域，用来指向该结点的孩子结点。
?????? 对于下图左图所示的树来说，树的度为 3 ，所以我们指针域的个数是 3 ，这种方法实现如下图右图所示。
?????? 这种方法对于树中各结点的度相差很大时，显然是很浪费空间的，因为有很多的结点，它的指针域都是空的。不过如果树的各结点相差很小时，那就意味着开辟的空间被充分利用了，这时存储空间的缺点反而变成了优点。
?????? 既然很多指针域可能为空，为什么不按需分配空间呢。于是就有了第二种方案。
?????? 方案二
?????? 第二种方案每个结点指针域的个数等于该节点的度，我们专门取一个位置来存储结点指针域的个数，其结构如下图所示：
?????? 其中 data 为数据域，degree 为度域，也就是存储该结点的孩子结点的个数，child1 到 childd 为指针域，指向该结点的各个孩子的结点。
?????? 对于下图左图所示的树来说，这种方法实现如下图右图所示：
?????? 这种方法克服了浪费空间的缺点，对空间利用率是很高了，但是由于各结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗。
?????? 仔细观察，为了遍历整棵树，把每个结点放到一个顺序存储结构的数组中是合理的，但每个结点的孩子有多少是不确定的，所以我们再对每个结点的孩子建立一个单链表体现它们的关系。这样就可以减少空指针的浪费又能使结点结构相同。
?????? 这就是孩子表示法。具体办法是，把每个结点的孩子结点排列起来，以单链表作存储结构，则 n 个结点有 n 个孩子链表，如果是叶子结点则此单链表为空。然后 n 个头指针又组成一个线性表，采用顺序存储结构，存放一个一维数组中，如下图所示。
?????? 为此，设计两种结构组织，一个是孩子链表的孩子结点，如下图所示：
?????? 其中 child 是数据域，用来存储某个结点在表头数组中的下标。next 是指针域，用来存储指向某结点的下一个孩子结点的指针。
?????? 另一个是表头数组的表头结点，如下图所示：
?????? 其中 data 是数据域，存储某结点的数据信息。firstchild 是头指针域，存储该结点的孩子链表的头指针。
?????? 以下是我们孩子表示法的结构定义代码。
//树的孩子表示法结构定义
#define MAX_TREE_SIZE 100 //结点数组的大小
typedef int TElemType; //根结点的数据类型，此处定位整型
typedef struct CTNNode //孩子结点
{
int child;
struct CTNode *next;
}*ChildPtr;
typedef struct //表头结构
{
TElemType data;
ChildPtr firstchild;
}CTBox;
typedef struct //树结构
{
CTBox nodes[MAX_TREE_SIZE]; //结点数组
int r, n; //根的位置和结点数
}CTree;?????? 这样结构的优点在于我们要查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便的，对头结点的数组循环即可。
?????? 缺点是，寻找某个结点的双亲时，需要遍历整棵树才行，比较麻烦。
?????? 可以将双亲表示法和孩子表示法综合一下，如下图所示：
这种方法称为双亲孩子表示法，应该算是孩子表示法的改进。
?????? 从树结点的兄弟的角度研究树的存储结构，对于树这样的层级结构来说，只研究结点的兄弟是不行的，我们观察后发现，任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。
?????? 结点结构如下图所示：
?????? 其中 data 是数据域，firstchild 为指针域，存储该结点的第一个孩子结点的存储地址，rightsib 是指针域，存储该结点的右兄弟结点的存储地址。
?????? 结构定义代码如下：
//树的孩子兄弟表示法结构定义
typedef struct CSNode
{
TElemType data;
struct CSNode *firstchild, *rightsib;
}CSNode,*CSTree;?????? 对于下图所示的树来说，这种方法实现的示意图如下图所示：
?????? 此表示法，查找某个结点的某个孩子带来了方便，只需要通过 firstchild 找到此结点的长子，然后再通过长子结点的 rightsilb 找到它的二弟，接着一直下去，直到找到具体的孩子。缺点是如果想找某个结点的双亲，这个表示法也是有缺陷的。
?????? 如果有必要，完全可以再增加一个 parent 指针域来解决快速查找双亲的问题。
?????? 其实这个表示法最大的好处是它把一棵复杂的树变成了一棵二叉树。把左图变成了右图这个样子。
?????? 这样就可以利用二叉树的特性和算法来处理这棵树了。
现在我们来做个游戏，我在纸上已经写好了一个 100 以内的正整数数字，请大家想办法猜出我写的是哪一个？注意你们猜的数字不能超过 7 个，我的回答只会告诉你 是“大了”或“小了”。
这个游戏在一些电视节目中，猜测一些商品的定价时常会使用。我看到过有些人是一点一点的数字累加的，比如 5、10、15、20 这样猜，这样的猜数策略太低级了，显然是没有学过数据结构和算法的人才做得出的事。
?????? 其实这是一个很经典的折半查找算法。如果用下图的办法（省略下三层）。就一定能在七次之内猜出结果。
?????? 猜测过程如下图所示：
???? 可以看出折半查找效率很高。不过对于这种在某个阶段都是两种结果的情形，比如开和关、0 和 1 、真和假、上和下、对与错、正面与反面等，都适合用树状结构来建模，而这种树是一种很特殊的树状结构，叫做二叉树。
?????? 二叉树：二叉树（Binary Tree）是 n（n ≥ 0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
?????? 下图所示就是一棵二叉树：
?????? 二叉树的特点有：
?????? ■ 每个结点最多有两棵子树，所以二叉树中不存在度大于 2 的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。
?????? ■ 左子树和右子树是有顺序的，次序不能任意颠倒。就像人是双手、双脚，但显然左手、左脚和右手、右脚是不一样的，右手带左手套、右脚穿左鞋都会及其别扭和难受。
?????? ■
