数据结构第七章：树

Posted on | In , | |

Abstract：树。

7.1 树的概念与表示

对具有更一般意义的树结构进行讨论。本章所讨论的树结构，其结点可以有任意数目的子结点，这使其在存储以及操作实现上要比二叉树更复杂。

7.1.1 树的定义和相关术语

1.树的定义

树：n（n>=0）个有限数据元素的集合。n = 0时，为空树。

在一棵非空树T 中：

  • （1）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。
  • （2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm 称为这个根结点的子树。

递归概念：用树定义树；类同二叉树结构算法——递归。

描述——二元组：T = （D，R）

D：结点的集合；R：结点间关系的集合。

空树时：D=Φ；当T不为空时，D = {Root}∪DF

Root：根结点；DF：子树集合，DF＝D1∪D2∪…∪Dm 且Di∩Dj＝Φ（i≠j，1≤i≤m，1≤j≤m）

当T中结点个数n <= 1时，R = Φ；当树T 中结点个数n>1 时有：R＝{，i＝1，2，…，m}

Root：根结点；ri：根结点Root的子树Ti的根结点。

树的两个特点：

  • 根结点无前驱结点，除根结点外的所有结点有且只有一个前驱；
  • 所有结点有0个或多个后继结点。

树结构与非树

b、c、d都不是树结构。

有序树与无序树：如果一棵树中结点的各子树丛左到右是有次序的，即若交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。

森林：零棵或有限棵不相交的树的集合称为森林。自然界中树和森林是不同的概念，但在数据结构中，树和森林只有很小的差别。任何一棵树，删去根结点就变成了森林。

7.1.2 树的表示

树的表示方法：

1.直观表示法：如上图a，对树的逻辑结构的直观描述，最常用。

2.嵌套集合表示法：嵌套集合指一些集合的集体，对于其中任何两个集合，或者不相交，或者一个包含另一个；用嵌套集合的形式表示树，就是将根结点视为一个大的集合，其若干棵子树构成这个大集合中若干个互不相交的子集，如此嵌套下去，即构成一棵树的嵌套集合表示。下图(a)就是一棵树的嵌套集合表示。

3.凹入表示法：如下图c，用于树的屏幕和打印输出；

4.广义表表示法：将根作为由子树森林组成的表的名字写在表的左边，这样依次将树表示出来。下图 (b)就是一棵树的广义表表示。

树的三种表示法

7.2 树的基本操作与存储

  • Initiate(t):初始化一棵空树t
  • Root(x):求结点x所在树的根结点
  • Parent(t, x):求树t种结点x的双亲结点
  • Child(t, x, i):求树t中结点x的第i个孩子结点
  • RightSibling（t，x）求树t 中结点x 的第一个右边兄弟结点。
  • Insert（t，x，i，s）把以s 为根结点的树插入到树t 中作为结点x 的第i 棵子树。
  • Delete（t，x，i）在树t 中删除结点x 的第i 棵子树。
  • Tranverse（t）是树的遍历操作，即按某种方式访问树t 中的每个结点，且使每个结点只被访问一次。

7.2.2 树的存储结构

存储结构要求：

  • 存储data——各结点的数据信息
  • 唯一反映各结点之间的逻辑关系

1.双亲表示法：树中的每个结点都有唯一的一个双亲结点，根据这一特性，可用一组连续的存储空间（一维数组）存储树中的各个结点，数组中的一个元素表示树中的一个结点，数组元素为结构体类型，其中包括结点本身的信息以及结点的双亲结点在数组中的序号，树的这种存储方法称为双亲表示法。

1
2
3
4
5
6
#define MAXNODE
typedef struct{
elemtype data;
int parent;
}NodeType;
NodeType t[MAXNODE]

缺点：

  • 求某结点的孩子结点，即实现Child（t，x，i）操作时，需要查询整个数组
  • 不能反映各兄弟结点的关系，难以实现RightSibling（t，x）操作

解决：在结点结构中增设存放第一个孩子的域和存放第一个右兄弟的域；

树

树a的双亲表示法表示如下图：图中用parent 域的值为-1 表示该结点无双亲结点，即该结点是一个根结点。

树a的双亲表示法表示

2.孩子表示法：

(1) 多重链表法：

由于树中的每个结点都有0个或多个孩子结点，因此可令每个结点包括1个结点信息域data和多个指针域；每个指针域指向该结点的一个孩子结点，通过各指针域反映树中各结点间的逻辑关系。

多重链表：每个结点都有多个指针域，形成多条链表。

在一棵树中，各结点度数差异，结点指针域个数的设置有2种表示方法：

  • 每个结点指针域的个数 = 该结点的度数：节约存储空间；但由于各结点不同构，各操作不易实现；
  • 每个结点指针域个数 = 树的度数：结点同构，但浪费存储空间（适用：各结点度数相差不大的情况）；

树中结点存储表示：

1
2
3
4
5
#define MAXSON<树的度数>
typedefine struct TreeNode{
elemtype data;
struct TreeNode *son[MAXSON];
}NodeType;

对任意一棵树t，可定义：NodeType *t；使变量t为指向树的根结点的指针。

树的孩子表示法

（2）孩子链表表示法：

将树按下图形式存储。单链表的结构也由两个域组成，一个存放孩子结点在一维数组中的序号，另一个是指针域，指向下一个孩子。

树的孩子链表表示法

存储表示描述：

1
2
3
4
5
6
7
8
9
10
#define MAXNODE <树中结点的最大个数>
typedef struct ChildNode{
int childcode;
struct ChildNode *nextchild;
}
typedef struct {
elemtype data;
struct ChildNode *firstchild;
}NodeType;
NodeType t[MAXNODE];

3.双亲孩子表示法
双亲表示法是将双亲表示法和孩子表示法相结合的结果。其仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号。如下图：

树的双亲孩子表示法

4.孩子兄弟表示法

一种常用的存储结构。

方法：在树中，每个结点除其信息域外，再增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针。在这种存储结构下，树中结点的存储表示可描述为：

1
2
3
4
5
typedef struct TreeNode {
elemtype data;
struct TreeNode *son;
struct TreeNode *next;
}NodeType;

孩子兄弟表示法

7．3 树、森林与二叉树的转换

从树的孩子兄弟表示法可以看到，如果设定一定规则，就可用二叉树结构表示树和森林，这样，对树的操作实现就可以借助二叉树存储，利用二叉树上的操作来实现。本节将讨论树和森林与二叉树之间的转换方法。

7.3.1 树转换成二叉树

树与二叉树的区别：无序树的各孩子结点词序无关紧要；而二叉树的左、右孩子结点有区别。

转换方法：

  • 树中所有相邻兄弟之间加一条连线
  • 对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。
  • 以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明。

在二叉树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟，所以变换后的二叉树的根结点的右孩子必为空。
一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的。

树转换成二叉树

7.3.2 森林转换为二叉树

森林是若干棵树的集合，只要将森林中各棵树的根视为兄弟，每棵树又可以用二叉树表示，这样，森林也同样可以用二叉树表示。森林转换为二叉树的方法如下：

  • 将森林中的每棵树转换成相应的二叉树。
  • 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。

这一方法可形式化描述为：

如果F＝{ T1，T2，…，Tm }是森林，则可按如下规则转换成一棵二叉树B＝（root，LB，RB）。

  • （1）若F 为空，即m＝0，则B 为空树；
  • （2）若F 非空，即m≠0，则B 的根root 即为森林中第一棵树的根Root(T1)；B 的左子树LB 是从T1 中根结点的子树森林F1＝{ T11，T12，…，T1m1 }转换而成的二叉树；其右子树RB 是从森林F’＝{ T2，T3，…，Tm }转换而成的二叉树。

森林及其转换为二叉树的过程：

森林及其转换为二叉树

7.3.3 二叉树转换为树和森林

树和森林都可以转换为二叉树，二者不同的是树转换成的二叉树，其根结点无右分支，而森林转换后的二叉树，其根结点有右分支。显然这一转换过程是可逆的，即可以依据二叉树的根结点有无右分支，将一棵二叉树还原为树或森林，具体方法如下：

  • （1）若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来；
  • （2）删去原二叉树中所有的双亲结点与右孩子结点的连线；
  • （3）整理由（1）、（2）两步所得到的树或森林，使之结构层次分明。

这一方法可形式化描述为：

如果B＝（root，LB，RB）是一棵二叉树，则可按如下规则转换成森林F＝{ T1，T2，…，Tm }。

  • （1）若B 为空，则F 为空；
  • （2）若B 非空，则森林中第一棵树T1 的根ROOT（T1）即为B 的根root；T1 中根结点的子树森林F1 是由B 的左子树LB 转换而成的森林；F 中除T1 之外其余树组成的森林F’＝{ T2，T3，…，Tm }是由B 的右子树RB 转换而成的森林。

一棵二叉树还原为森林的过程:

二叉树还原成树

7．4 树和森林的遍历

7.4.1 树的遍历

1.先根遍历

定义：

  • 访问根结点
  • 按照从左至右顺序先根遍历根结点的每一棵子树

树

对上图先根遍历，顺序：ABEFCDG

2.后根遍历

定义：

  • 按照从左至右顺序后根遍历根结点的每一棵子树
  • 访问根结点

对上图后根遍历，顺序：EFBCGDA

7.4.2 森林的遍历

1.前序遍历

（1）访问森林中第一棵树的根结点；
（2）前序遍历第一棵树的根结点的子树；
（3）前序遍历去掉第一棵树后的子森林。

森林

对上图森林前序遍历，得出结果序列：ABCDEFGHJIK

2.中序遍历

（1）中序遍历第一棵树的根结点的子树；
（2）访问森林中第一棵树的根结点；
（3）中序遍历去掉第一棵树后的子森林。

对上图森林中序遍历，得出结果序列：B A D E F C J H K I G

森林的前序遍历和中序遍历与所转换的二叉树的先序遍历和中序遍历的结果序列相同。

7．5 树的应用

树的应用十分广泛，在后面的排序和查找常用的两项技术中，就有以树结构组织数据进行操作的。本节仅讨论树在判定树和集合表示与运算方面的应用。

7．5．1 判定树

最优二叉树：哈夫曼在判定问题中的应用

判定树：用于判定问题的描述与解决；解决过程中的一系列判断构成了树结构

Q：设有八枚硬币，分别表示为a，b，c，d，e，f，g，h，其中有一枚且仅有一枚硬币是伪造的，假硬币的重量与真硬币的重量不同，可能轻，也可能重。现要求以天平为工具，用最少的比较次数挑选出假硬币，并同时确定这枚硬币的重量比其它真硬币是轻还是重。

A：用H 和L 分别表示假硬币较其它真硬币重或轻。下面对这一判定方法加以说明，并分析它的正确性。

从八枚硬币中任取六枚，假设是a，b，c，d，e 和f，在天平两端各放三枚进行比较。

假设a，b，c 三枚放在天平的一端，d，e，f 三枚放在天平的另一端，可能出现三种比较结果：
（1）a＋b＋c>d＋e＋f
（2）a＋b＋c＝d＋e＋f
（3）a＋b＋c<d＋e＋f

这里，只以第一种情况为例进行讨论。若a＋b＋c>d＋e＋f，根据题目的假设，可以肯定这六枚硬币中必有一枚为假币，同时也说明g，h 为真币。这时可将天平两端个去掉一枚硬币，假设它们是c 和f，同时将天平两端的硬币各换一枚，假设硬币b，d 作了互换，然后进行第二次比较，那么比较的结果同样可能有三种：

①a＋d>b＋e 这种情况表明天平两端去掉硬币c，f 且硬币b，d 互换后，天平两端的轻重关系保持不变，从而说明了假币必然是a，e 中的一个，这时我们只要用一枚真币（b，c，d，f，g，h）和a 或e 进行比较，就能找出假币。例如，用b 和a 进行比较，若a>b，则a 是较重的假币；若a＝b，则e 为较轻的假币；不可能出现a<b 的情况。

②a＋d＝b＋e 此时天平两端由不平衡变为平衡，表明假币一定在去掉的两枚硬币c，f 中，a，b，d，e，g，h 必定为真硬币，同样的方法，用一枚真币和c 或f 进行比较，例如，用a 和c 进行比较，若c>a，则c 是较重的假币；若a＝c，则f 为较轻的假币；不可能出现c<a 的情况.

③a＋db 的情况。

7．5．2 集合的表示

集合：

  • 可分成多个子集
  • 分划
  • 运算：交并补差，判定
  • 树结构表示集合：结点——元素；树结构——双亲表示法存储；

存储描述：

1
2
3
4
typedef struct{
    elemtype data;
    int parent;
}NodeType

data 域存储结点本身的数据，parent 域为指向双亲结点的指针，即存储双亲结点在数组中的序号.

集合S1\S2\S3的树结构存储示意

集合并运算算法：

1
2
3
4
5
6
7
8
9
void Union （ NodeType a[]  int i int j
/*合并以数组a 的第i 个元素和第j 个元素为树根结点的集合*/
{ if ( a[i].parent != -1 || a[j].parent != -1 )
  {
	  printf (“ \ n 调 用参数 正确 ”) ；
		  return(；
			 }
			 a[j].parent = i); /*将i 置为两个集合共同的根结点*/
    }

如果要查找某个元素所在的集合，可以沿着该元素的双亲域向上查，当查到某个元素的双亲域值为－1 时，该元素就是所查元素所属集合的树根结点(-1表示无双亲结点)

算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
int Find（NodeType a[ ]，elemtype x）
{/*在数组a 中查找值为x 的元素所属的集合，*/
/*若找到，返回树根结点在数组a 中的序号；否则，返回－1*/
/*常量MAXNODE 为数组a 的最大容量*/
int i,j;
i=0;
while (i<MAXNODE && a[i].data!=x) i++;
if (i>=MAXNODE) return –1; /*值为x 的元素不属于该组集合，返回－1*/
j=i;
while (a[j].parent!=-1) j=a[j].parent;
return j; /*j 为该集合的树根结点在数组a 中的序号*/
}

7．5．3 关系等价求等价类问题

1．问题：已知集合S 及其上的等价关系R，求R 在S 上的一个划分{S1,S2,…,Sn}，其中，S1,S2,…,Sn 分别为R 的等价类，它们满足：

    ∪Si＝S 且Si∩Sj＝ф(i≠j)

设集合S 中有n 个元素，关系R 中有m 个序偶对。

2．算法思想：

（1）令S 中每个元素各自形成一个单元素的子集，记作S1，S2，…，Sn；
（2）重复读入m 个序偶对，对每个读入的序偶对，判定x 和y 所属子集。不失一般性，假设x∈Si，y∈Sj，若Si≠Sj，则将Si 并入Sj，并置Si 为空（或将Sj 并入Si，并置Sj 为空）；若Si＝Sj，则不做什么操作，接着读入下一对序偶。直到m 个序偶对都被处理过后，S1，S2，…，Sn 中所有非空子集即为S 的R 等价类，这些等价类的集合即为集合S 的一个划分。

3．数据的存储结构：对集合的存储采用第7.5.2 小节中介绍的集合的存储方式，即采用双亲表示法来存储本算法中的集合。

4． 算法实现

通过前面的分析可知，本算法在实现过程中所用到的基本操作有以下两个：

（1）Find（S，x）查找函数。确定集合S 中的单元素x 所属子集Si，函数的返回值为该子集树根结点在双亲表示法数组中的序号；
（2）Union（S，i，j）集合合并函数。将集合S 的两个互不相交的子集合并，i 和j分别为两个子集用树表示的根结点在双亲表示法数组中的序号。合并时，将一个子集的根结点的双亲域的值由没有双亲改为指向另一个子集的根结点。

这两个操作的实现在7.5.2 小节中已经介绍过，下面就本问题的解决算法步骤给出描述：
①k=1
②若k>m 则转⑦，否则转③
③读入一序偶对
④i= Find（S，x）;j= Find（S，y）
⑤若i≠j，则Union（S，i，j）；
⑥k++
⑦输出结果，结束。

5． 算法的时间复杂性：

查找算法和合并算法的时间复杂度分别为O(d)和O(1)，其中d 是树的深度。这种表示集合的树的深度和树的形成过程有关。在极端的情况下，每读入一个序偶对，就需要合并一次，即最多进行(m－n)/2 次合并，若假设每次合并都是将含成员多的根结点指向含成员少的根结点，则最后得到的集合树的深度为n，而树的深度与查找有关。这样全部操作的时间复杂性可估计为O(n2)。

若将合并算法进行改进，即合并时将含成员少的根结点指向含成员多的根结点，这样会减少树的深度，从而减少了查找时的比较次数。促使整个算法效率的提高。

Thanks!