1.5.3　树与图

1．树

树状结构是以分支关系定义的层次结构，它是一种重要的非线性结构。该结构在客观世界中广泛存在，例如人类的家庭族谱、各种社会组织机构、计算机文件管理和信息组织方面都用到该结构。

（1）树的定义。

定义5　树是由n（n≥0）个结点组成的有限集。在任意一棵非空树中，有且仅有一个特定的结点称为该树的根结点，当n>1时，根结点之外的其余结点可分为m（m≥0）个互不相交的有限集合T₁，T₂，…，T_m，其中每个集合本身又是一棵树，称为根的子树。树的示意图如图1-7所示。

图1-7是一棵由11个结点组成的树T。其中A是根结点，其余结点分为3个互不相交的有限子集：T₁={B，E，F，K}，T₂={C，G}，T₃={D，H，I，J}，T₁，T₂，T₃都是根A的子树，这3棵子树的根结点分别是B，C，D，每棵子树本身也是一棵树，可继续划分。例如子树T₃以D为根结点，子树的其余结点又可分为3个互不相交的子集T₃₁={H}，T₃₂={I}，T₃₃={J}，而T₃₁、T₃₂和T₃₃又是只有一个根结点的树。

（2）树结构中的重要术语。

父结点：若一个结点有子树，则该结点为父结点（或称为双亲结点）。

孩子结点：若某结点有子树，则其子树的根为该结点的孩子结点。

兄弟结点：同一个结点的孩子结点。

层次：结点的层次是从根结点开始定义的，根结点的层次为1，其余结点的层次是其父结点的层次加1。若某结点在第i层，则其子树的根就在第i+1层。

结点的深度：结点所在的层次减1。

树的高度（深度）：树中结点的最大深度。

度：结点拥有的子树数目称为该结点的度，即一个结点的孩子数目就是该结点的度。

叶子结点：度为0的结点。

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

二叉树：二叉树是一种非常重要的树状结构，它的特点是每个结点至多只有两棵子树，并且，二叉树的子树有左右之分，其次序有时不能任意颠倒。

例如，对于如图1-7所示的树，根结点A是结点B、C和D的父结点，结点B是结点E、F的父结点；结点B、C和D是结点A的孩子结点，并且B、C和D互为兄弟结点；结点A的层次是1、深度为0，结点B的层次为2、深度为1，结点K的层次为4、深度为3，因此该树的深度为3；另外，结点A拥有的孩子结点数目为3，因此A的度为3，同样结点C的度为1，结点F的度为0，可见F为叶子结点，图1-7中所示的F，G，H，I，J都是该树的叶子结点。

（3）树的存储结构。

与线性结构类似，树的存储结构也可以采用顺序存储结构和链式存储结构两种方式。在大量的应用中，人们曾使用多种形式的存储结构来表示树，这里只介绍常用的几种。

①顺序存储结构——双亲表示法。

由于树中的每个结点可以有任意多棵子树，结点的编号和孩子结点的编号不存在必然的关系，因此必须在结点中指出它们之间的父子关系。

双亲表示法是以一组连续的空间来存储树中的结点，并将树中所有结点从上到下、从左至右依次编号，并用该编号作为结点在顺序存储中的位置。

树中每个结点包含两个域，即数据域（data）和双亲域（parent）。数据域存放结点的数据，双亲域存放双亲（父）结点在顺序存储中的位置编号。通过parent域，顺序存储的各个结点仍然保持正确的前驱-后继关系。

【例1-8】　用双亲表示法顺序存储如图1-8（a）所示的树。

根据树的顺序存储结构，采用双亲表示法顺序存储如图1-8（a）所示的一棵树，表示结果如图1-8（b）所示。

由于根结点没有父结点，因此将其parent域设置为-1。

这种结构利用了每个结点（除根外）只有唯一的父结点的性质，但是这种表示法在求结点的孩子时需要遍历整个结构。

②链式存储结构——孩子表示法。

把每个结点的孩子结点排列起来，看成一个线性表，且以单链表作为存储结构，则n个结点有n个孩子链表（叶子结点的孩子链表为空表）。而n个头指针又组成另外一个线性表。为了便于查找，可采用顺序存储结构。

与双亲表示法相反，孩子表示法便于那些涉及孩子的操作的实现，却不适用于对双亲结点进行操作。为此，可以把二者结合起来。

③链式存储结构——孩子兄弟表示法。

孩子兄弟表示法又称二叉树表示法或二叉链表表示法，即以二叉链表作为树的存储结构，链表中结点的两个域分别指向该结点的第一个孩子结点和下一个兄弟结点。

利用这种存储结构易于实现找结点孩子等操作。如果为每个结点增加一个parent域，则同样能方便地实现对双亲的操作。

树有十分重要的用途，如构造哈夫曼树、最优二叉查找树及解空间树等，在实际的应用中，请读者细细体会其奥妙吧。

2．图

图是一种比线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅存在线性关系，即每个元素只有一个直接前驱和一个直接后继。在树状结构中，元素之间具有明显的层次关系。每一个元素只能和上一层（如果存在的话）的一个元素相关，但可以和下一层的多个元素相关。在图形结构中，元素之间的关系可以是任意的，一个图中任意两个元素都可以相关，即每个元素可以有多个前驱和多个后继。

图的应用最早可以追溯到18世纪，伟大的数学家欧拉（Euler）利用图解决了著名的格尼斯堡七桥问题，这一创举为图在现代科学技术领域中的应用奠定了基础。目前图的应用极为广泛，特别是近年来的迅速发展，已经渗入到诸如语言学、逻辑学、物理、电子电路分析及计算机学科中。

（1）图的定义。

定义6　图是一种数据结构，可以用二元组表示，图中的数据元素通常称为顶点（或结点），数据元素之间的关系称为边，其形式化定义为G=（V，E）。

其中，集合V是顶点集，即它是顶点的有穷非空集合；集合E是边集，即它是V中两个顶点之间的关系的有穷集。

在图G中，若<v，w>∈E，则<v，w>表示从v到w的一条弧，v称为弧尾或始点，w称为弧头或终点，此时的图称为有向图。若<v，w>∈E必有<w，v>∈E，即E是对称的，则以无序对（v，w）代替这两个有序对，表示v和w之间的一条边，此时的图称为无向图。下面通过实例（如图1-9所示）讲述一下这两种图的区别及相应的形式化定义方法。

在图1-9（a）中，每条边的方向是用从始点指向终点的箭头表示的，因此该图是有向图。该有向图的形式化定义为G₁=（V₁，E₁）；顶点集V₁={v₁，v₂，v₃}；边集E₁={<v₁，v₂>，<v₁，v₃>，<v₂，v₃>，<v₃，v₂>}；注意<v₃，v₂>与<v₂，v₃>表示两条不同的边。

图1-9（b）中所示的每条边都是没有方向的，因此该图为无向图。该无向图的形式化定义为G₂=（V₂，E₂）；顶点集V₂={v₁，v₂，v₃，v₄}；边集E₂={（v₁，v₂），（v₁，v₃），（v₁，v₄），（v₂，v₃），（v₃，v₄）}；注意（v₂，v₁）与（v₁，v₂）表示同一条边。

（2）图的相关重要术语。

①邻接点和相关边。

对于无向图G=（V，E），如果边（v，w）∈E，则称顶点v和w互为邻接点，称边（v，w）依附于顶点v和w，即边（v，w）是与顶点v和w相关联的边。

对于有向图G=（V，E），如果<v，w>∈E，则称顶点v邻接到顶点w，顶点w邻接于顶点v，而弧<v，w>是与顶点v和w相关联的。

②路径和回路。

路径：在无向图G=（V，E）中，从顶点v到顶点v′的路径是一个顶点序列（v=v_i，0，v_i，1，…，v_i，_m=v′），其中（v_i，j-1，v_i，j）∈E，1≤j≤m。如果G是有向图，则路径也是有向的，顶点序列应满足<v_i，j-1，v_i，_j>∈E，1≤j≤m。路径的长度为路径上的边（或弧）的数目。

第一个顶点和最后一个顶点相同的路径称为回路或环。环的判断也是一个非常重要的概念，在Kruskal算法中就涉及了对环的判断。另外，有向无环图是描述含有公共子式的表达式、一项工程及系统的进行过程的有效工具。

③权、网。

有时候图中的边或弧具有和其相关的数据，如表示一个顶点到另一个顶点的距离和费用，称这些相关的数据为边或弧的权，而这种带权的图称为网。网示意图如图1-10所示。

④连通、生成树。

在无向图G中，如果从顶点v到顶点v′有路径，则称v和v′是连通的。如果图中任意两个顶点都是连通的，则称G是连通图。

在有向图G中，如果对于每一对v，w∈V，v≠w，从v到w和从w到v都存在路径，则称G是强连通的。

一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只能构成一棵树的n-1条边。同样，生成树是一个很重要的概念，例如在求解如何在最节省费用的前提下在n个城市间构造通信联络网时，就用到了最小生成树的概念。在该概念的指导下，问题的解决将变得非常容易。

（3）图的存储结构。

图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储空间中的位置来表示元素之间的关系，即图没有顺序映像的存储结构，但可以借助数组来表示元素之间的关系。

常用图的存储结构有邻接矩阵、邻接表、邻接多重表和十字链表。用多重链表表示图是自然的事，它是一种最简单的链式映像结构。另外，在实际的应用中，应根据具体的图和所定义的运算，选择恰当的存储结构来使用。

①邻接矩阵。

邻接矩阵是表示图中各顶点之间关系的矩阵，是图的存储结构之一。一般借助数组来实现。

定义7　假设G=（V，E）是一个有n个顶点的图，规定各顶点的序号依次为1，2，3，…，n，则G的邻接矩阵是一个具有如下定义的n阶方阵：

对于带权图（或网），可以将上述定义改为

其中，W_i表示<v_i，v_j>弧或（v_i，v_j）边上的权值。

例如，图1-9（a）的邻接矩阵为

图1-9（b）的邻接矩阵为

图1-10（a）的邻接矩阵为

图1-10（b）的邻接矩阵为

显然，在无向图中，邻接矩阵是对称的，因此仅需要存储上三角或下三角的元素。

可见，一个图可以用两个数组来表示。其中一维数组用来存储数据元素（即图的顶点）的信息，二维数组用来存储数据元素之间关系的信息（即图中边或弧的信息），即邻接矩阵。借助邻接矩阵很容易判定任意顶点之间是否存在边（或弧），并容易求得各顶点的度。

②邻接表。

邻接表是图的一种链式存储结构。在邻接表中，图中每个顶点对应一个单链表，第i个单链表中的结点表示依附于顶点v_i的边（对于有向图是以顶点v_i为尾的弧）。每个结点由三个域组成，邻接点域指示与顶点v_i邻接的点在图中的位置，链域指示下一条边或弧的结点，数据域存储与边或弧相关的信息。每个链表设置一个表头结点，该结点中的链域指向链表中第一个结点，数据域用来存储v_i的名称或其他相关信息。

显然，在边稀疏的情况下，采用邻接表表示图比邻接矩阵节省存储空间，且在邻接表中容易找到任一个顶点的第一个邻接点和下一个邻接点，但要判断任意两个顶点间是否存在边就没有邻接矩阵方便了。

由于在邻接表中，为了求某个顶点的入度则必须遍历所有链表。因此，为了提高入度计算的效率，通常为图建立一个逆邻接表。逆邻接表就是链表结点代表以v_i为弧头的弧。

③十字链表。

十字链表是有向图的另一种链式存储结构。可以看成将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点也有一个结点。这两个结点的结构示意图如图1-11所示。

在每条弧所对应的结点中，尾域tailvex和头域headvex分别指示弧尾和弧头这两个顶点在图中的位置，链域hlink指向弧头相同的下一条弧顶点，而链域tlink指向弧尾相同的下一条弧顶点，info域指示该弧的相关信息。显然，弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上。它们的头结点即为顶点结点，由三个域组成，其中data域存储和顶点相关的信息，firstin和firstout链域分别指向以该顶点为弧头或弧尾的第一个弧结点。

在十字链表中，既容易找到以v_i为尾的弧，也容易找到以v_i为头的弧，因此在某些有向图的应用中，十字链表是很有用的工具。

④邻接多重表。

邻接多重表是无向图的另一种链式存储结构。虽然邻接表是无向图的一种很有效的存储结构，在邻接表中很容易求得顶点和边的各种信息。但是，在邻接表中每一条边（v_i，v_j）有两个顶点，分别在第i个和第j个链表中，这给某些图的操作带来了不便。例如在某些图中需要对已被搜索过的边做标记等，此时需要找到表示同一条边的两个结点，在进行这一类操作时采用邻接多重表作为存储结构更为适宜。

邻接多重表和十字链表类似。这里不再赘述。