一、基本概念
树的定义
树（Tree）是 n（n >= 0）个结点的有限集。
- n = 0 时，称为空树；
- n > 0 时，为非空树，在非空树中：
- (1) 有且只有一个特定的称为根（Root）的结点；
- (2) n > 1 时，其余结点可分为 m（m>0）个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）;
注意：
1、n > 0 时根结点是唯一的，不可能存在多个根结点。
2、m > 0 时，子树的个数没有限制，但它们一定是互不相交的。
两个结构就不符合树的定义，因为它们都有相交的子树。
相关术语
- 结点的度：结点拥有子树数，称为结点的度；
- 叶结点：度为0的结点，称为叶结点（Leaf）或终端结点；
- 分支结点：度不为0的结点，称为分支结点；
- 树的度：树内部各结点的度的最大值；
度
- 结点的子树的根称为该结点的孩子，结点称为孩子的双亲；
- 结点为根的子树中所有结点都是该结点的子孙，该结点称为子孙的祖先；
- 同一个双亲的孩子之间称为兄弟；
- 双亲在同一层的结点称为堂兄弟；
结点关系
- 结点的层次从根开始，根结点为第1层，根结点的孩子为第2层，依次类推。
- 树中结点的最大层次称为树的深度或高度
结点的层次
- 若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(Ordered Tree)；
否则称为无序树(UnorderedTree)。
注意：若不特别指明，一般讨论的树都是有序树。
举例
- 森林（Forest）是 m（m>=0）颗不相交的树的集合。
森林
二、树的存储结构
对于存储结构，可能会联想到前面的 顺序存储和链式存储结构。但是对于树这种可能会有很多孩子的特殊数据结构，只用顺序存储结构或者链式存储结构很难实现，
不过充分利用顺序存储和链式存储结构的特点，完全可以实现对树的存储结构的表示。产生主要的三种存储结构表示法：双亲表示法、孩子表示法、孩子兄弟表示法。
2.1、双亲表示法
我们假设 以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。
也就是数组中存放一个结构体，结构体大致如下：
struct
/* 树的双亲表法结点结构定义*/
#define MAX_TREE_SIZE 100
typedef int ElemeType;
typedef struct PTNode{ // 结点结构
ElemeType data; //结点数据
int parent; // 双亲位置
}PTNode;
typedef struct { // 树结构
PTNode nodes[MAX_TREE_SIZE]; // 结点数组
int r; // 根的位置
int n; // 结点数
}PTree;
双亲表示法
双亲表示法的特点
- 由于根结点是没有双亲的，约定根结点的位置位置域为-1.
- 根据结点的parent指针很容易找到它的双亲结点。所用时间复杂度为O(1)，直到parent为-1时，表示找到了树结点的根。
- 缺点：如果要找到孩子结点，需要遍历整个结构才行。
对结构体拓展，对其进行改进
可如果我们要知道结点的孩子是什么，对不起，请遍历整个结构才行。
这真是麻烦，能不能改进一下呢?
当然可以。我们增加一个结点最左边孩子的域，不妨叫它长子域，这样就可以很容易得到结点的孩子。如果没有孩子的结点，这个长子域就设置为-1，如下图：
对struct进行拓展
2.2、双亲表示法
初始
树的度是3，所以我们的指针域的个数是3，这种方法实现如图
多重链表表示法
这种方法对于树中各结点的度相差很大时，显然是很浪费空间的，因为有很多的结点，它的指针域都是空的。不过如果树的各结点度相差很小时，那就意味着开辟的空间被充分利用了，这时存储结构的缺点反而变成了优点。
改进
改进方案每个结点指针域的个数等于该结点的度，我们专门取一个位置来存储结点指针域的个数，如下图：
改进，节省空间
这种方法克服了浪费空间的缺点，对空间利用率是很高了，但是由于各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗。
再次改进
我们为了要遍历整棵树，把每个结点放到一个顺序存储结构的数组中是合理的，但每个结点的孩子有多少是不确定的，所以我们再对每个结点的孩子建立一个单链表体现它们的关系 。
结构体
再次改进
这样的结构对于我们要查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便的，对头结点的数组循环即可。
但是，这也存在着问题，我如何知道某个结点的双亲是谁呢?比较麻烦，需要整棵树遍历才行，难道就不可以把双亲表示法和孩子表示法综合一下吗?当然是可以。
最终 - 双亲孩子表示法
双亲孩子表示法
2.3、孩子兄弟表示法 - 将复杂树变为二叉树
结构体
image.png
其实这个表示法的最大好处是它把一棵复杂的树变成了一棵二叉树。我们把上图变形就成了下图这个样子：
image.png
最后，如果真的有必要，完全可以再增加一个parent指针域来解决快速查找双亲的问题。
相关文档参考
引用《大话数据结构》作者：程杰
数据结构（十三）——树
树的三种存储结构
【数据结构】树的定义和树的三种存储结构
网友评论