树的概念及结构|树的三种表示方法

前言

以前我们学的线性结构是一对一的线性关系，但现实中，还有一对多的情况要处理，那就是树形结构。今天我们将学习树的概念及结构、和树的三种常见表示方法。

一、树的概念及结构

1、树的概念

树是一种非线性的数据结构，它是由n（n >= 0）个有限结点组成的一个具有层次关系的集合。

（1）为什么把这种结构，叫做树呢？

答案是： 因为它的逻辑图看起来像一颗倒挂的树，根朝上，叶向下。如下图：

（2）空树

空树： n=0时称为空树。

（3）非空树

根节点： 有且仅有一个特定的结点，称为根(Root)节点。（根节点没有前驱结点）

树是递归实现的： 当n>1时，除根节点外，其余结点可分为m（m>0）个互不相交的有限集T1,T2,……Tm，其中每一个集合Ti（1<= i <=m）本身又是一颗树，并且称为根的子树(SubTree)。（每颗子树的根节点有且仅有一个前驱，可以有0个或多个后继）简单来说：任何一颗树都由根与子树组成。（没有子树就结束） 如下图：

（4）对于树的定义需要强调两点

① 对于任意一棵树根节点都是唯一，子树的根节点是子树的。

② 在树形结构中，子树之间一定是互不相交的，否则就不是树型结构。如下图：

（5）树的其他的表示形式（了解）

2、树的相关概念

• 结点的度： 结点拥有的子树的个数称为结点的度。如上图：A的度为6。
• 叶结点或终端结点： 度为0的结点称为叶子结点或终端结点。如上图：B、C、H、I……等结点为叶节点。
• 分支结点或非终端结点： 度不为0的结点称为分支结点或非终端结点。（除了根节点外，分支节点也称内部结点。）如上图：D、E、F、G……等结点为分支节点。
• 树的度： 树的度是树内各节点的度的最大值。如上图：树的度为6。
• 孩子结点与双亲结点： 结点的子树的根称为该节点的孩子结点，相应的，该节点称为孩子结点的双亲结点。如上图：A是B的双亲结点，B是A的孩子结点。
• 兄弟结点： 同一个双亲结点的孩子结点之间互称兄弟结点。如上图：B、C是兄弟结点。
• 结点的祖先： 从根到该节点所经分支上所有结点。如上图A是所有结点的祖先。
• 结点的子孙： 以某结点为根的子树中的任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙。
• 结点的层次： 从根开始定义起，根为第一层，根的孩子为第二层，以此类推。（数组我们是从0开始，为什么层次不从0开始呢——因为不符合我们平时的习惯，如以0开始，我们说根为第0层，那空树就得说-1层了，所以我们一般从1开始。）
• 树的深度或高度： 树中节点的最大层次。如上图：树的高度为4。
• 堂兄弟结点： 其双亲在同一层的结点互为堂兄弟。如上图：B、C、D、E、F、G互为堂兄弟。
• 森林： 由m（m>=0）颗互不相交的树的集合称为森林。
• 有序树与无序树： 如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

二、树的存储结构

树这种一对多的结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间的关系， 不过充分利用顺序存储和链式存储结构的特点，完全可以实现树的存储结构的表示。我们这里了解三种不同的表示法：双亲表示法、孩子表示法、孩子兄弟表示法。

1、双亲表示法

定义： 用一组连续空间存储树的节点，同时在每个结点中，附设一个指示器指示其双亲结点在表中的位置。结点结构如下图所示：


其中data是数据域，存储结点的数据信息。parent是指针域，存储该结点的双亲在数组中的下标，因为根节点没有双亲，所以我们约定根节点的位置域设置为-1。

实现： 树的结构需要有三个成员：结点数组、结点数、根的位置，所以我们将其定义为一个结构体。

双亲表示法的代码实现：

//树节点的数据类型
typedef int TElemType;
//结点结构
typedef struct PTNode
{
	TElemType data;//结点数据域
	int parent;//结点指针域，指向双亲的下标位置
}PTNode;

//树结构
typedef struct PTree
{
	PTNode* a;//指向堆区开辟的节点数组
	int root;//根节点的位置
	int size;//结点数
}PTree;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

如下图中树结构和树双亲表示所示：


优缺点：

优点：①找双亲容易；②顺序存储。

缺点：找孩子难，需要遍历整个结构。

2、孩子表示法

定义： 由于树中每个结点可能有多棵子树，可以考虑用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根节点，我们把这种方法叫做多重链表表示法。

因为树的每个结点的度，也就是它的孩子个数是不同的。所以我们有两种设计方案来解决。

方案一（树的度已知）：结点同构 ——已知树的度为d，指针域的个数就等于树的度。其结构如下图：


其中data是数据域，child1到childd是指针域，用来指向该结点的孩子结点。

代码示例：

//已知树的度为N
#define N 5
//树的节点
typedef struct TreeNode
{
	struct TreeNode* child[N];//指针数组——存储孩子结点的位置
	int data;//存储数据
}TreeNode;
1
2
3
4
5
6
7
8

如下左图的树，树的度是3，所以指针域的个数是3，孩子表示如下右图所示：


如图我们可知这种方法当树中很多结点的度小于d时，结点中有很多指针域为空，空间浪费。

方案二（树的度未知）：孩子表示法——理解两个结构：①孩子结点；②表头结点。然后使用顺序存储实现孩子表示法。 如图所示：

①孩子结点： 就是用单链表存储某个结点的所有孩子结点的地址（注：n个结点有n个孩子链表，如果是叶子结点则该链表为空。）结构如下所示：


②表头结点： 有两个成员：data成员存储某个结点的数据信息；firstchild成员存储该结点孩子链表的头指针。结构如图所示：


③树结构： 由三个成员组成：指向表头数组的指针a、保存根位置的root、保存节点数的size。

代码示例：

//孩子结点
typedef struct CTNode
{
	int child;//数据域，存储孩子结点在表头数组中的下标
	struct CTNode* next;//指向下一个孩子结点
}CTNode;

//表头结点
typedef struct
{
	int data;//存储结点的数据
	CTNode* firstchild;//存储孩子链表的头指针
}CTBox;

//树的结构
typedef struct
{
	CTBox* a;//指向堆区开辟表头数组
	int root;//根位置
	int size;//节点数
}Tree;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3、孩子兄弟法

定义： 我们观察发现，任意一棵树，它的节点的第一个孩子如果存在就是唯一，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟，也可叫做左兄弟右孩子法。结构如图所示：


代码示例：

typedef int DataType;
typedef struct TreeNode
{
	struct Node* firstChild1; // 第一个孩子结点
	struct Node* pNextBrother; // 指向其下一个兄弟结点
	DataType data; // 结点中的数据域
}TreeNode;
1
2
3
4
5
6
7

如下图树结构与孩子兄弟的表示：


总结：这三种表示方法就是分别从孩子、双亲、兄弟的角度设计的。