数据结构-树图概念

线性表

“线性表”是指由有限多个类型相同的数据元素组成的集合，它有以下的特点： (1)有唯一的头结点(即第一个数据元素)和尾结点(即最后一个数据元素)； (2)除结点外，集合中的每个数据元素均只有一个前驱；

(3)除尾结点外，集合中的每一个数据元素均只有一个后继。 “线性表”是一种运用非常广范的数据结构。

例1、某旅馆有100个房间，以1到 100 编号，第一个服务员来了，他将所有的房门都打开，第二个服务员再把所有编号是2 的倍数的房门都关上，第三个服务员对编号是3 的倍数的房门原来开的关上，原来关上的打开，此后的第四，五...服务员均照此办理。问第100个服务员走进后，有哪几扇门是开着的。 【参考程序】

#include using namespace std; int main() { bool a[101]; int i,j;

for (i=1;i<=100;i++)

a[i]=true; //a[i]为true，表示门是开的 for (i=2;i<=100;i++) for (j=1;j<=100;j++) if (j%i==0)

a[j]=!(a[j]); //!是取相反的运算 for (i=1;i<=100;i++) if ( a[i]==true)

cout<栈

栈是只能在某一端插入和删除的特殊线性表。 用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。 栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。

插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO 表）。

一个栈可以用定长为Ｎ的数组Ｓ来表示，用一个栈指针 TOP 指向栈顶。若 TOP＝0，表示栈空，TOP=N时栈满。进栈时TOP加１。退栈时 TOP 减１。当 TOP<0

时为下溢。栈指针在运算中永远指向栈顶。

1、进栈（push）算法

①若 top>=ｎ时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢 出；不满则作②）；

②置top=top+1（栈指针加１，指向进栈地址）； ③s[topP]=x，结束（X为新进栈的元素）； 2、退栈（pop）算法

①若top<=0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)； ②x=s[top]，（退栈后的元素赋给x）；

③top=top-1，结束（栈指针减１，指向栈顶）。

队列

队列是限定在一端进行插入，另一端进行删除特殊线性表。正象排列买东西，排在前面的人买完东西后离开队伍（删除），而后来的人总是排在队伍未尾（插入）。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能从队头离去。由于总是先入队的元素先出队（先排队的人先买完东西），这种表也称为先进先出（FIFO）表。 队列可以用数组 q[1] „[ｍ]来存储，数组的上界ｍ即是队列所容许的最大容量。在队列的运算中需设两个变量：

head：队头，指向实际队头元素的前一个位置 tail：队尾，指向实际队尾元素所在的位置

一般情况下，两个指针的初值设为0，这时队列为空，没有元素。图 1 ( a)画出了一 个由6个元素构成的队列，数组定义q[1]„[10]。 q(i) i=3,4,5,6,7,8头指针head＝2，尾指针tail＝8。

队列中拥有的元素个数为:L=tail-head 现要让排头的元素出队，则需将头指针加1。 即 head=head+1这时头指针向上移动一个位置，指向q(3)，表示q(3)已出队。见图 1 (b)。 如果想让一个新元素入队，则需尾指针向上移动一个位置。即 tail=tail+1 这时 Q(9)

入队，见图1 (c)。

当队尾已经处理在最上面时，即 tail=10，见图 1 (d)，如果还要执行入队操作，则要 发生\"上溢\"，但实际上队列中还有三个空位置，所以这种溢出称为\"假溢出\"。

克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动，显然这种方 法是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就\"翻转\"为１。在结构上采用这种技巧来存储的队列称为循环队列。见图2

循环队的入队算法如下： 1、tail=tail+1；

2、若tail=n+1，则tail=1；

3、若head=tail尾指针与头指针重合了，表示元素已装满队列， 则作上溢出错处理； 4、否则，q(tail)=x，结束（x为新入出元素）。

树

树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。一切具有层次关系的问题都可用树来描述。

例如，一个集团公司，可以描述如下:

它很象一株倒悬着的树，从树根到大分枝、小分枝、直到叶子把数据联系起来，这种数据结构就叫做树结构，简称树 一、树的概述

树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。以下具体地给出树的定义及树的数据结构表示。 （一）树的定义

树是由一个或多个结点组成的有限集合，其中： ⒈必有一个特定的称为根(ROOT)的结点；

⒉剩下的结点被分成ｎ>=0个互不相交的集合T1、T2、......Tn，而且， 这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。

树中每个分叉点称为结点，起始结点称为树根，任意两个结点间的连接关系称为树枝，结点下面不再有分枝称为树叶。结点的前趋结点称为该结点的\"双亲\"，结点的后趋结点称为该结点的\"子女\"或\"孩子\"，同一结点的\"子女\"之间互称\"兄弟\"。

A(a)EKL(c)(a)空树(b)只有根结点的树(c)一般的树图1BFCGHG……………..第0层………….第1层DA(b)IJ…….第2层.….………第3层

（二）树的表示法 1.树形表示法

2.广义表表示法

将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式：

（三）树的有关术语

度：一个结点拥有的子树数称为该结点的度。

树的度：一棵树的度是指该树中结点的最大度数。

叶子和分支结点：度为零的结点称为叶子或终端结点。度不为零的结点称为分支结点或非终端结点。除根结点之外的分支结点统称为内部结点，根结点又称为开始结点。 双亲和孩子：树中某个结点的子树之根称为该结点的孩子或儿子，相应地，该结点称为孩子的双亲或父亲。

兄弟（Sibling）和堂兄弟：同一个双亲的孩子称为兄弟。双亲在同一层的结点互为堂兄弟。

结点的层数（Level）：是从根起算，设根的层数为1，其余结点的层数等于其双亲结点的层数加1。

树的高度（Height）：树中结点的最大层数称为树的高度或深度（Depth）。 有序树和无序树：若将树中每个结点的各子树看成是从左到右有次序的（即不能互换），则称该树为有序树；否则称为无序树。

森林（Forest）：是m(m≥0)棵互不相交的树的集合。

二．二叉树

二叉树是一种十分重要的树型结构。它的特点是，树中的每个结点最多只有两棵子树，即树中任何结点的度数不得大于２。二叉树的子树有左右之分，而且，子树的左右次序是重要的，即使在只有一棵子树的情况下，也应分清是左子树还是右子树。 （一）定义

二叉树是结点的有限集合，这个集合或是空的，或是由一个根结点和两棵互不相交的称之为左子树和右子树的二叉树组成。图2列出了二叉树的五种基本形态。

图 2

(a)为空二叉树；(b)只有一个结点的二叉树；(c)只有左子树的二叉树；(d)只有右子树的二叉 树；(e)左右完全的二叉树。

（二）满二叉树

除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树。

一棵深度为k的满二叉树，是有2

k+1

-1个结点.的深度为k的二叉树。2

k+1

-1个结点

是二叉树所能具有的最大结点个数。图3所示为一棵深度为3的满二叉树。

20 21 22 2 3

图 3 图 4

（三）完全二叉树

对满二叉树，从第一层的结点(即根)开始，由下而上，由左及右，按顺序结点编号，便得到满二叉树的一个顺序表示。据此编号，完全二叉树定义如下：一棵具有ｎ个结点，深度为K的二叉树，当且仅当所有结点对应于深度为K的满二叉树中编号由1至ｎ的那些结点时，该二叉树便是完全二叉树。图4是一棵完全二叉树。 （只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；） （四）二叉树的性质

性质1；若二叉树的层次从0开始，则在二叉树的第i层最多有2i个结点（i>=0） 性质2；深度为k的二叉树最多有2k+1-1个结点(k>=-1) 说明：k=-1是空树的情形，此时结点数为0，即2k+1-1=2-1+1-1=0，结论成立。k>=0是非空二叉树的情形，具有层次i=0，1，2，….k。根据性质1，第i层最多有2i个结点，则整个二叉树中所具有的最大结点数为：

(第i层上的最大结点数）i0i0kk2i =2k+1-1；

性质3；对于任意一棵二叉树，如果其叶结点数为n0，而度数为2的结点总数为

n2，则n0=n2+1；

证明：

假设这棵树的总结点树为 n，度为 1 的结点树为 n1。因为二叉树中的所有结点的度都为0、1、2，所以：n= n0+ n1+ n2 ①再看二叉树的分支数。除了根结点，其余每个结点都有且仅有一个分支进入，设 B为分支总数（入度），则 B=n-1。而度为 1 的结点有 1 个分支射出，度为 2 的结点有 2 个分支射出，度为0的结点没有分支射出，所以分支总数（出度）又等于：n1+2*n2,当然，入度=出度，即：n-1= n1+2*n2,所以得出：n= n1+2*n2+1

②由①②可以得出：n0=n2+1。

性质4；具有n个结点的完全二叉树的深度为int（log2n）+1 证明：

假设深度为k，则根据完全二叉树的定义，前面k-1 层一定是满的，所以 n>2 k-1-1。但n 又要满足n<=2 k-1。所以，2k-1-11,则其父结点编号为 trunc(i/2)。

② 如果 2*i>n，则结点 i无左孩子（当然也无右孩子，为什么？即结点 i 为 叶结点）；否则左孩子编号为 2*i。

③ 如果2*i+1>n，则结点i 无右孩子；否则右孩子编号为 2*i+1。

（四）遍历二叉树

在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对全部结点逐一进行某种处理。这就是二叉树的遍历问题。所谓二叉树的遍历是指按一定的规律和次序访问树中的各个结点，而且每个结点仅被访问一次。“访问”的含义很广，可以是对结点作各种处理，如输出结点的信息等。遍历一般按照从左到右的顺序，共有3种遍历方法，先（根）序遍历，中（根）序遍历，后（根）序遍历。 1.先序遍历的操作定义如下：

若二叉树为空，则空操作，否则 ① 访问根结点

② 先序遍历左子树 ③ 先序遍历右子树

先序遍历右图结果为：1247536 2.中序遍历的操作定义如下：

若二叉树为空，则空操作，否则 ① 中序遍历左子树 ② 访问根结点 ③ 中序遍历右子树

中序遍历右图结果为：742513869 3.后序遍历的操作定义如下：

若二叉树为空，则空操作，否则 ① 后序遍历左子树 ② 后序遍历右子树 ③ 访问根结点

后序遍历右图结果为：7452631

练习：写出下面这棵数的先序遍历、中序遍历、后序遍历的结果

-+a/*bcef-d

（五）树和森林与二叉树的转换

树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可惟一地对应到一棵二叉树;反之，任何一棵二叉树也能惟一地对应到一个森林或一棵树。 1.树、森林到二叉树的转换

(1)将树转换为二叉树 树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树： ①在所有兄弟结点之间加一连线;

②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。

【例1】 下面左图所示的树可转换为右图所示的二叉树。具体转换过程可

注意：由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。 (2)将一个森林转换为二叉树 具体方法是：

① 将森林中的每棵树变为二叉树

② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。

【例2】下图中，左边包含三棵树的森林可转换为右边的二叉树。

具体转换过程可

2.二叉树到树、森林的转换

把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。 【例3】下图的森林就是由例2中二叉树转换成的。

图

第一节 图的基本概念

线性表：数据间关系是线性的，每个元素只有一个前趋，一个后续，1：1； 树：有着明显的层次关系，每个元素只有一个前趋，但有多个后续，1：N； 图：数据之间的关系是任意，每个元素的前趋和后续个数是不定的，M：N； 引入：柯尼斯堡七桥问题，能否从A 地发出，各座桥恰好通过一次，最后回到出

发地A？

结论：1736年，数学家欧拉 首先解决了这个问题，由此开创了图论研究。这事实上是

欧拉图的“一笔画问题”。答案是否定的，因为，对于每一个顶点，不论如何经过，必须有一条进路和一条出路，与每一个顶点相邻的线（关联边）必须是偶数条（除起点和终点外），而此图中所有点都只有奇数条关联边。在后面的应用中，我们将专门讨论这个问题。

定义：简单讲，一个图是由一些点和这些点之间的连线组成的。严格意义讲，图是一种数据结构，定义为：graph=（V，E）。V 是一个非空有限集合，代表顶点（结点），E 代表边的集合，一般用（Vx，Vy）表示，其中，Vx，Vy 属于 V。 分类：如果边是没有方向的，称为“无向图”。表示时用一队圆括号表示，如：（Vx，Vy），（Vy，Vx），当然这两者是等价的。并且说边（Vx，Vy）依附于（相关联）顶点 Vx 和Vy。 如果边是带箭头的，则称为“有向图”，表示时用一队尖括号表示，此时与是不同的，如的起点为Vx，终点为 Vy。有向图中的边又称为弧。起点称为弧头、终点称为弧尾。

相邻：若两个结点U、V之间有一条边连接，则称这两个结点 U、V 是关联的。 带权图：两点间不仅有连接关系，还标明了数量关系（距离、费用、时间等）。 图的阶：图中结点的个数。

结点的度：图中与结点 A关联的边的数目，称为结点A 的度。 入度：在有向图中，把以结点V为终点的边的数目称为 V的入度； 出度：在有向图中，把以结点U为起点的边的数目称为 U的出度； 奇点：度数为奇数的结点； 偶点：度数为偶数的结点；

终端结点：在有向图中，出度为0的结点；

定理1：图中所有结点的度数之和等于边数的2 倍； 定理2：任意一个图一定有偶数个奇点；

连通：如果图中结点 U，V 之间存在一条从 U 通过若干条边、点到达 V 的通路，则称 U、V是连通的。 路(径）：从一个结点出发，沿着某些边连续地移动而到达另一个指定的结点，这种依次由结点和边组成的序列，叫“路”或者“路径”。 路径长度：路径上边的数目。

简单路径：在一个路径上，各个结点都不相同，则称为简单路径。 回路：起点和终点相同的路径，称为回路，或“环”。

连通图：对于图G中的任一对不同顶点U、V，都有一条（U，V）通路，则称图G 是连通的。

强连通图：在有向图 G中，每一对结点之间都有路径的图。 网络：带权的连通图。