【数据结构】树（一）—— 树的基础知识（C语言版）

一、树的定义

树(Tree)是 n(n≥0)个结点的有限集。

n=0 时称为空树。

在任意一颗非空树中：
（1）有且仅有一个特定的称为根(Root)的结点

（2）当 n>1时，其余结点可分为 m(m>0)个互不相交的有限集 T₁、T₂、…、T_m， 其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)，如下图所示

树的其它表示方法

其中(a)是以嵌套集合 （即是一些集合的集体，对于其中任何两个集合，或者不相交，或者一个包含另一个） 的形式表示 的； (b)是以广义表的形式表示的，根作为由子树森林组成的 表的名字写在表的左边； © 用的 是凹入表示法（类似书的编目）。

树的定义其实实质是递归的方法。如下图，子树T1 和 T2 就是根节点A的子树

注意

n>0 时，根节点唯一，不存在多个根节点
m>0 时，子树个数没有限制，但**一定互不相交**

如下图：不属于树。

二、树的相关概念

树的结点包含一个数据元素及若干指向其子树的分支。

1. 度(Degree)

度(Degree)：结点拥有的子树树称为结点的度。
（1）度为0的结点称为 叶节点(Leaf)或终端结点。
（2）度不为0的结点称为非终端结点或分支结点。
（3）除根节点外，分支结点也称为内部结点。
（4）树的度就是树内各结点的度的最大值。

2. 结点间的关系

结点的子树的根称为该结点的 孩子(Child)， 相应的，该结点称为汉子的双亲(Parent)。
同一个双亲的孩子之间互称 兄弟(Sibling)。
结点的祖先是从根到该结点所经分支上的所有结点。
以某结点为根的子树中的任一结点都称为该结点的 子孙。

3. 结点的层次(Level)

结点的 层次(Level)从根开始定义起，根为第一层，根的孩子为第二层。树中结点的最大层次称为树的 深度(Depth)或高度。比如下图树的深度为4

4. 有序树与森林

有序树：树中结点的各子树从左至右有次序，不能互换，否则为 无序树。

森林(Forest)：是 m(m>0)棵互不相交的树的集合。
对树中每个结点而言，其子树的集合即为森林。

三、线性表和树的不同

四、树的性质

• 树中的结点数等于所有结点的度数加1
• 度为 m 的树中第 i 层上至多有$m^{i-1}$个结点（i大于等于1）
• 高度为 h 的 m 叉树至少有 h个结点，至多有 $(m^h-1)/(m-1)$ 个结点
• 具有 n 个结点的 m 叉树的最小高度为

• m 叉树允许所有结点的度都小于m，任意结点的度最多有m个孩子，且可以是空树；
• 度为 m 的树，任意结点的度小于等于 m ，至少有一个结点的度等于 m，且一定是非空树，至少有 m+1个结点。

五、树的抽象数据类型

ADT 树 (tree)
Data树是由一个根节点和若干棵子树构成。树中结点具有相同数据类型及层次关系
OperationInitTree(*T): 构造空树 TDestroyTree(*T)：销毁树 TCreateTree(*T, definition)：按 definitin 中给出树的定义来构造树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 赋值为 valueParent(T, cur_e)：若 cur_e 是树 T 的非根节点，则返回它的双亲，否则返回空LeftChild(T, cur_e)：若 cur_e 是树 T 的非叶节点，则返回它的最左孩子，否则返回空RightSibling(T, cur_e)：若 cur_e 有右兄弟，则返回它的右兄弟，否则返回空InsertChild(*T, *p, i, c)：其中p 指向树 T 的某个结点，i (1<= i <= p)为所指结点 p 的度加上 1， 非空树 c 与 T不相交.操作结果为插入 c 为树 T 中 p 所指结点的第 i 课子树DeleteChild(*T, *p, i)：其中 p 指向树 T 的某个节点，i (1<= i <= p)为所指结点 p 的度.操作结果为删除 T 中  p 所指结点的第 i 棵子树
endADT

六、树的存储结构

先分别说下三种不同的表示法：双亲表示法、孩子表示法、孩子兄弟表示法

双亲表示法：一般采用顺序存储方式；
孩子表示法：采用顺序存储+链式存储；
孩子兄弟表示法：采用链式存储，（其实是一个二叉链表，相当于构建二叉树）

1. 双亲表示法

树的结点以一组连续空间表示，且在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。（静态链表）

其中data是数据域，存储结点的数据信息。而parent是指针域，存储该结点的双亲在数组中的下标

/* 树的双亲表示法结点结构定义 */
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)。

双亲表示法的优化

双亲表示法对于双亲很容易找到，但是，节点的孩子不太好找，需要遍历整个结构，所以稍加改动，添加一个左孩子域就行，没有左孩子的就设为-1

同样对于兄弟节点比较关注的话，添加一个兄弟节点域。

如果节点的孩子还很多，超过2个。然后又关注节点的双亲、又关注节点的孩子、还关注节点的兄弟，而且对时间的遍历要求还比较高，那么我们还可以把此结构扩展为有双亲域、长子域、再有右兄弟域。存储结构的设计是一个非常灵活的过程。一个存储过程设计得是否合理，取决于基于该存储结构的运算是否合适、是否方便，时间复杂度好不好等。注意也不是越多越好，又需要时再设计相应的结构。

2. 孩子表示法

多重链表，就是链表里的结点可能隶属多个链表，
https://blog.csdn.net/maxiaoyin111111/article/details/84542585

思路： 由于树中每个结点可能有多棵子树，可以考虑用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的结点。（多重链表表示法）

缺点： 对于树的每个结点的度，即它的孩子的个数是不同的。
解决方案:
（一） 指针域的个数等于树的度

此方法容易造成内存空间的浪费。

（二）每个结点指针域的个数等于该结点的度。
使用一个特定位置存储结点指针域的个数

其中 data 为数据域， degree 为度域， 也就是存储该结点的孩子结点的个数， child1 到 child 为指针域， 指向该结点的各个孩子的结点。

这种方法克服了浪费空间的缺点，对空间利用率很高，但是由于各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上会带来时间上的损耗。

两方法的更进一步优化：
为了遍历整课树，把每个结点放到一个顺序存储结构的数组中是合理的，但是每个结点的孩子有多少是不确定的，所以可以建立一个单链表体现它们的关系。即孩子表示法

孩子表示法：由孩子链表的孩子结点和表头数组的表头结点组合。

把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子节点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，采用个顺序存储结构，存放进一个一维数组中。

为此，有两种结点结构： 孩子链表的孩子结点 ， 表头数组的表头结点

孩子链表的孩子结点, child为数据域，存储某个结点在表头数组中的下标，next为指针域，存储指向下一孩子结点的指针

表头数组的表头结点，data是数据域，存储某结点的数据信息。firstchild是头指针域，存储该结点的孩子链表的头指针。

/* 树的孩子表示法结构定义 */
#define MAX_TREE_SIZE 100
typedef struct CTNode  // 孩子结点
{int child;struct CTNode *next;
}*ChildPtr;
typedef struct  // 表头结构
{TElemType data;ChildPtr firstchild;
}CTBox;
typedef struct  // 树结构
{CTBox nodes[MAX_TREE_SIZE];  //结点数组int r, n;                    // 根的位置和结点数
}CTree;

优点：方便查找孩子以及兄弟结点
缺点：对于双亲则需要遍历整棵树。
优化方法：添加双亲域

3. 孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。故可设置两个指针，分别指向第一个孩子和此结点的右兄弟。

结点结构中,data是数据域，firstchild是指针域，存储该结点的第一个孩子结点的存储地址，rightsib是指针域，存储该结点的右兄弟结点的存储地址

/* 树的孩子兄弟表示法结构定义 */
typedef struct CSNode
{TElemType data;struct CSNode *firstchild, *rightsib;
}CSNode, *CSTree;`

这种表示法的好处就是将一颗复杂的树变成了一颗二叉树了。

麻烦的是找双亲不太好找，需要的话可以加个parent指针来解决快速查找双亲的问题。

本篇文章摘自《大话数据结构》，有兴趣的小伙伴可以找这本书来看看。