六、树
6.1 树的定义
**树(Tree)是n (n≥0)个结点的有限集。n=0时称为空树。**在任意一棵非空，树中:
(1) 有且仅有一个特定的称为根(Root) 的结点;
(2) 当n>1时，其余结点可分为m (m>0)个互不相交的有限集T1、 T2、… Tn, 其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。
树的定义其实就是我们在讲解栈时提到的递归的方法。也就是在树的定义之中还用到了栈的概念，这是一种比较新的定义方法。下图中的子树T1和子树T2就是根结点A的子树。当然，D、G、H、I组成的树又是B为结点的子树，E、J组成的树是C为结点的子树。
对于树的定义还需要强调两点:
n>0时根结点是唯一的，不可能存在多个根结点，别和现实中的大树混在一起，现实中的树有很多根须，那是真实的树，数据结构中的树是只能有一个根结点。
m>0时，子树的个数没有限制，但它们一定是 互不相交的。像下面的两个结构就不符合树的定义，因为它们都有相交的子树。
下面这张图就是不符合要求的树定义
6.1.1基本术语
根节点：非空树中无前驱结点的结点
结点的度：结点拥有的子树数
树的度：树内各节点的度的最大值
叶子：度为0，没有分支了，也叫终端结点
分支结点：度不为0的点，根结点以外的分支结点称为内部结点
除了根结点以外，其他的结点都称为内部结点
6.1.2结点间的关系
结点的子树的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)。
为啥叫双亲呢？因为就一个结点，对结点来说其父母同体所以只能把它称为双亲
同一个双亲的孩子之间互称兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。所以对于H来说，D、B、A都是它的祖先。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。B的子孙有D、G、H、I
6.1.3树的其他相关概念
结点的层次(Level) 从根开始定义起，根为第一层,根的孩子为第二层。若某结点在第1层，则其子树的根就在第l+1层。**其双亲在同一层的结点互为堂兄弟。**图中D、E、F是堂兄弟，而G、H、I、J也是。
树中结点的最大层次称为树的深度(Depth) 或高度，当前树的深度为4。
如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
森林(Forest) 是m (m≥0)棵互不相交的树的集合
把根节点删除，树就变成了森林
两棵子树其实就可以理解为森林。
给森林中的各子树加上一个双亲结点，森林就变成了树
对比线性表与树的结构，它们有很大的不同
线性结构
第一个数据元素:无前驱
中间元素：一个前驱一 个后继
最后一个数据元素:无后继
树结构
根结点:无双亲，唯一
叶结点:无孩子，可以多个
中间结点:一个双亲多个孩子
6.2树的抽象数据类型
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的非叶结点，则返回它的最左孩子，否则返回空。 RightSibling (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
6.3树的存储结构
说到存储结构，就会想到顺序存储和链式存储两种结构。
先来看看顺序存储结构，用一段地址连续的存储单元依次存储线性表的数据元素。这对于线性表来说是很自然的，对于树这样一多对的结构呢?
简单的顺序存储结构是不能满足树的实现要求的。
6.3.1双亲表示法
每个结点，它不一定有孩子，但是一定有且仅有一个双亲。
我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。也就是说，每个结点除了知道自己是谁以外，还知道它的双亲在哪里。
其中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个。我们又关注结点的双亲、又关注结点的孩子、还关注结点的兄弟，而且对时间遍历要求还比较高，那么我们还可以把此结构扩展为有双亲域、长子域、再有右兄弟域。存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理，取决于基于该存储结构的运算是否适合、是否方便，时间复杂度好不好等。注意也不是越多越好，有需要时再设计相应的结构。就像再好听的音乐，不停反复听上千遍也会腻味，再好看的电影，一段时间反复看上百遍，也会无趣，你们说是吧?
6.3.2孩子表示法
换一种完全不同的考虑方法。由于树中每个结点可能有多棵子树，可以考虑用多重链表，即每个结点有多个指针域，其中每**个指针指向一棵子树的根结点,我们把这种方法叫做多重链表表示法。**不过，树的每个结点的度，也就是它的孩子个数是不同的。所以可以设计两种方案来解决。
方案一：
一种是指针域的个数就等于树的度，复习一下，树的度是树各个结点度的最大值
[data|child|child1|…|childn]
其中data是数据域，child1到childn是指针域，用来指向该结点的孩子结点
用图来说明一下吧
这种方法显然是很浪费空间的，因为有很多结点，它的指针域都是空的
第二种方案
每个结点指针域的个数等于该结点的度，专门取一个位置来存储结点指针域的个数
如下
data为数据域，degree为度域，也就是存储该结点的孩子结点的个数，child1到childn为指针域，指向该结点的各个孩子的结点
实现如图所示
这种方法克服了浪费空间的缺点，对空间利用率提高了很多，但是各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗
能不能有既可以减少空指针的浪费又能使结点结构相同。
我们为了要便利整棵树，把每个结点放到一个顺序存储结构的数组中是合理的，但，每个结点的孩子有多少是不确定的，所以我们再对每个结点的孩子建立一个单链表来体现它们的关系
这就是孩子表示法。具体办法是，把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中
如下图：
图中：
data firstchild是表示表头结点，其中data是数据域，存储某结点的数据信息。firstchild是头指针域，存储该结点的孩子链表的头指针
child next中child是数据域，用来存储某个结点在表头数组中的下标。next是指针域，用来指向某结点的下一个孩子结点的指针
代码实现如下：
/*树的孩子表示法结构定义*/ #define MAX TREE SIZE 100 typedef struct CTNode/* 孩子结点*/ { int child; struct CTNode *next; } typedef struct //表头结构 { TelemType data; ChildPty firstchild; }CTBox; typedef struct //树结构 { CTGBox nodes[MAX_TREE_SIZE]; //结点数组 int r,n; //根的位置和结点数 }CTree;
**这样的结构对于我们要查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。**对于遍历整棵树也是很方便的，对头结点的数组循环即可。
6.3.3孩子兄弟表示法
任意一个树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此设置两个指针，分别指向该结点的第一个孩子和此节点的右兄弟
如图
其中data是数据域，firstchild 为指针域，存储该结点的第一个孩子结点的存储地址，rightsib 是指针域，存储该结点的右兄弟结点的存储地址。
代码实现：
/*树的孩子兄弟表示法结构定义*/ typedef struct CSNode { TElemType data; struct CSNodeZ* firstchild, *rightsib; } CSNode, *CSTree;
实现效果：
这种表示法，给查找某个结点的某个孩子带来了方便
通过fistchild 找到此结点的长子，
然后再通过长子结点的rightsib 找到它的二弟，
接着一直下去，直到找到具体的孩子。
当然，如果想找某个结点的双亲，这个表示法也是有缺陷的
在来个指针就可以了对吧！~~
上述这种孩子兄弟表示法最大的好处是它把一颗复杂的树变成了一颗二叉树
如下所示
