【数据结构】—— 树

目录

树的定义        

树的结点

 结点间关系

 树的相关概念

树的存储结构

双亲表示法

孩子表示法

 兄弟孩子表示法

提示：如果学过树的相关概念，直接跳过！！！

树的定义        

        之前我们一直在谈的是一对一的线性结构，可现实中，还有很多一对多的情况需要处理，所以我们需要研究这种一对多的数据结构--“树”，考虑它的各种特性，来解决我们在编程中碰到的相关问题。

###树的定义
        树(Tree)是n（n≥0)个结点的有限集。n = 0时称为空树。在任意一棵非空树中:

1. 有且仅有一个特定的称为根(Root)的结点;
2. 当n>1时，其余结点可分为m(m>0)个互不相交的有限集 T1、T2、……、Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree )。

         子树T和子树 Tz就是根结点A的子树。当然，D、G、H、I组成的树又是B为结点的子树，E、C、F、J组成的树是C为结点的子树。

 对于树的定义还需要强调两点:

1. n>0 时根结点是唯一的，不可能存在多个根结点，别和现实中的树的根混为一谈，现实中的树有很多根须，那是真实的树，数据结构中的树是只能有一个根结点。
2. m>0 时，子树的个数没有限制，但它们一定是互不相交的。

###知识串通

        当然，你可能不知道图这个概念，不过没关系我们树讲完了就开始讲图！这里先过一遍，方便对树的结构理解！树和图有什么区别？这个称之为树的东西和无向图差不多嘛。树其实就是不包含回路的连通无向图。你可能还是无法理解这其中的差异，下面举个例子。

         上面这个例子中左边的是一棵树，而右边的是一个图。因为左边的没有回路，而右边的存在 1→2→5→3→1这样的回路。
正是因为树有着“不包含回路”这个特点，所以树就被赋予了很多特性：

1. 一棵树中的任意两个结点有且仅有唯一的一条路径连通。
2. 一棵树如果有n个结点，那么它一定恰好有-1条边。
3. 在一棵树中加一条边将会构成一个回路

树的结点

        树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶结点(Leaf)或终端结点；度不为0的结点称为非终端结点或分支结点。树的度是树内各结点的度的最大值。如图所示，因为这棵树结点的度的最大值是结点D的度，为3，所以树的度也为3。

 结点间关系

        结点的子树的根称为该结点的孩子(Child)结点，相应地，该结点称为孩子的双亲(Parent)结点。同一个双亲的孩子之间互称兄弟(Sibling)结点。结点的祖先是从根到该结点所经分支上的所有结点。所以对于H来说，D、B、A 都是它的祖先。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。B的子孙有 D、G、H、I，如图下图所示。

 树的相关概念

         结点的层次(Level)从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第1层，则其子树的根就在第 1+1 层。其双亲在同一层的结点互为堂兄弟。显然如下图所示 D、E、F是堂兄弟，而 G、H、I、J也是。树中结点的最大层次称为树的深度(Depth)或高度，当前树的深度为4。

         如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
        森林(Forest)是m(m>0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。相较于左图来说，右图两棵子树其实就可以理解为森林。

到此，我们就将树的大部分概念全都理清了，总结如下：

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

树的存储结构

        说到存储结构，就会想到我们前面章节讲过的顺序存储和链式存储两种结构。先来看看顺序存储结构，用一段地址连续的存储单元依次存储线性表的数据元素。这对于线性表来说是很自然的，对于树这样一多对的结构呢？树中某个结点的孩子可以有多个，这就意味着，无论按何种顺序将树中所有结点存储到数组中，结点的存储位置都无法直接反映逻辑关系，你想想看，数据元素挨个的存储，谁是谁的双亲，谁是谁的孩子呢？简单的顺序存储结构是不能满足树的实现要求的。
不过充分利用顺序存储和链式存储结构的特点，完全可以实现对树的存储结构的表示。我们这里要简单介绍三种不同的表示法：双亲表示法、孩子表示法、孩子兄弟表示法。其中孩子兄弟表示法最为常用。（如果不理解这些，也没有太大关系，等到我们讲解二叉树的时候你就会顿悟！）。

双亲表示法

        我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。也就是说，每个结点除了知道自己是谁以外，还知道它的双亲在哪里。也就是我们在结点中定义data、parent来标识；其中 data 是数据域，存储结点的数据信息。而parent 是指针域存储该结点的双亲在数组中的下标。结构定义如下所示：

using TreeData = int; //重命名类似typedef
#define NUM 1024
typedef struct Node
{
	TreeData data;
	int patent;
}Node;
typedef struct PTree
{
	Node nodes[NUM];
	int root, nodeNum;
};

有了这样的结构定义，我们就可以来模拟双亲表示法了。由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-1，这也就意味着，我们所有的结点都存有它双亲的位置。按照下图的树形结构，那么它的双亲表示法实现的效果是怎么样的！

这样的存储结构，我们可以根据结点的 parent指针很容易找到它的双亲结点，所用的时间复杂度为 O(1)，直到 parent 为-1时，表示找到了树结点的根。可如果我们要知道结点的孩子是什么，对不起，请遍历整个结构才行。

孩子表示法

        换一种完全不同的考虑方法。由于树中每个结点可能有多棵子树，可以考虑用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，我们把这种方法叫做多重链表表示法。不过，树的每个结点的度，也就是它的孩子个数是不同的。

基于此思想设计方案：每个结点指针域的个数等于该结点的度（也可以将指针域的个数就等于树的度），我们专门取一个位置来存储结点指针域的个数，其结构如下图所示：

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

我们要讲的孩子表司法就是基于此的优化：具体办法是，把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中，为了实现该结构：需要设计两种结点结构：

第一种孩子链表的结点的结构：

typedef struct CBNode
{
	int child;
	struct CBNode* next;
}CBNode;

其中 child 是数据域，用来存储某个结点在表头数组中的下标。next 是指针域，用来存储指向某结点的下一个孩子结点的指针。

第二种是表头结点的结构：

typedef struct CBox
{
	TreeData data;
	CBNode* childLinkHead;
}CBox;

其中 data 是数据域，存储某结点的数据信息。childLinkHead 是头指针域，存储该结点的孩子链表的头指针；

最终定义树的结构即可，

typedef struct CTree
{
	CBox nodes[NUM];
	CBNode* childLinkHead;
}CTree;

 最终孩子表示法的结构示意图如下：

 兄弟孩子表示法

        刚才我们分别从双亲的角度和从孩子的角度研究树的存储结构，如果我们从树结点的兄弟的角度又会如何呢?当然，对于树这样的层级结构来说，只研究结点的兄弟是不行的，我们观察后发现，任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。结构定义如下：

typedef struct BCNode
{
	struct BCNode* child; // 第一个孩子结点
	struct BCNode* Brother; // 指向其下一个兄弟结点
	TreeData _data; // 结点中的数据域
}BCNode;

其中，child指向当前结点的第一个孩子，即左孩子；brother指向其堂兄弟结点；如果该结点的child、brother都不存在全部指向NULL即可；

        这种表示法，给查找某个结点的某个孩子带来了方便，只需要通过child找到此结点的长子，然后再通过长子结点的brother找到它的二弟，接着一直下去，直到找到具体的孩子。当然，如果想找某个结点的双亲，这个表示法也是有缺陷的，那怎么办呢?如果真的有必要，完全可以再增加一个parent 指针域来解决快速查找双亲的问题，这里就不再细谈了。其实这个表示法的最大好处是它把一棵复杂的树变成了一棵二叉树。什么是二叉树留到下一章再谈！到此我们已经完成了树的基础铺垫，接下来就该进入更深入的学习：二叉树、堆、并查集、二叉排序树、平衡二叉排序树等(不一定按顺序讲)。

总结

好啦！简单总结一下，本章主要从树的定义开始引入了树的基础概念：结点的度、孩子结点、根节点、树的深度...接下来的重点介绍了树的存储结构：双亲表示法、孩子表示法、兄弟孩子表示法；其中，兄弟孩子表示法最为常用，基于兄弟孩子表示法引入二叉树的概念，当然还没有开始讲二叉树。