3.遍历算法.为了叙述方便，我们以如下图为例解释三种遍历的方法. ①中序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： (1)遍历左子树； (2)访问根结点； (3)遍历右子树.
按照以上算法，可以得到图中二叉树的中序序列为dbheiafcg. ②先序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作： (1)访问根结点； (2)遍历左子树； (3)遍历右子树.
如上例中二又树可以得到前序序列为abdehicfg. ③后序遍历得递归算法定义：
若二叉树非空，则依次执行如下操作： (1)遍历左子树； (2)遍历右子树； (3)访问根结点.
如上例中二叉树可以得到后序序列为dhiebfgca.
例、 有二叉树中序序列为ABCEFGHD，后序序列为：ABFHGEDC.请画出此二叉树，并求前序序列. 根据后序序列知根节点为C 因此左子树：中序序列为AB 后序序列为AB 右子树：中序序列为EFGHD 后序序列为FHGED 依次推得该二叉树的结构图. 前序序列为：CBADEGFH. 【练习题】一、选择题
1.一棵非空二叉树的前序遍历序列和后序遍历序列正好相反，则该二叉树一定满足______.
A.所有结点均无左孩子 B.所有的结点均无右孩子 C.只有一个叶子结点 D.是任意一棵二叉树
2.一棵完全二叉树上有1001个结点，其中叶子结点的个数是______.
a b c d e f g h i 11
A.250 B.500 C.254 D.505 E.以上答案都不对
3.设深度为k的二叉树上只有度为0 和度为2的结点，则这类二叉树上所含的结点总数为_______. A.k+1 B.2k C.2k-l D.2k+1
4.设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有_____个结点. A.13 B.12 C.26 D.25
5.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是_____. A.4 B.5 C.6 D.7
6.设树T的高度为4，其中度为1、2、3和4的结点个数分别为4、2、l、1，则T中的叶子数为______. A.5 B.6 C.7 D.8
7.某二叉树中序序列为abcdefg，后序序列为bdcafge，则前序序列是_____. A.egfacbd B.eacbdgf C.eagcfbd D.以上答案都不对
8.在一棵度为 3 的树中，度为 3 的结点个数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点个数为______. A.4 B.5 C.6 D.7
9.在一棵具有K层的满三叉树中，结点总数为______. A.(3k-1)/2 B.3k-l C.(3k-1)/3 D.3k
10.满二叉树的叶结点为N，则它的结点总数为____. A.N B.2N C.2N-1 D.2N+1 E.2N-1 二、问题解答
1.已知，按中序遍历二叉树的结果为：abc.
问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树. 2.一棵树的前序遍历为：ABDECFGHI，中序遍历为：DBEAFCHIG，求后序遍历。
12
4.4图
图(Graph)是一种复杂的非线性结构.在人工智能、工程、数学、物理、化学、生物和计算机科学等领域中，图结构有着广泛的应用.奥林匹克信息学竞赛的许多试题，亦需要用图来描述数据元素间的联系.
图G由两个集合V和E组成，记为：G=(V，E)，其中：V是顶点的有穷非空集合，E是V中顶点偶对(称为边)的有穷集.通常，也将图G的顶点集和边集分别记为V(C)和E(G).E(G)可以是空集.若E(G)为空，则图G只有顶点而没有边.
(一)有向图和无向图 1.有向图
若图G中的每条边都是有方向的，则称G为有向图(Digraptl).在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示.有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head).例如
(G1)={
若图G中的每条边都是没有方向的，则称G为无向图(Undigraph).无向图中的边均是顶点的无序对，无序对通常用圆括号表示.例如无序对(vi，vj)和(vj,vi)表示同一条边.下面4-4-1（b）中的G2和图4-4-1(c)中的G3均是无向图，它们的顶点集和边集分别为： V(G2)={vl，v2，v3，v4}
E(G2)={(Vl，V2)，(v1，v3)，(vl，v4)，(v2，v3)，(v2，v4)，(V3，V4)} V(G3)={vl，V2，v3，v4，v5，v6，v7}
E(G3)={(Vl，v2)，(Vl，v3)，(V2，v4)，(v2，v5)，(v3，v6)，(V3，V7)}
图4—4—1
13
3.图G的顶点数n和边数e的关系 (1)若G是无向图，则O≤e≤n(n—1)/2
恰有n(n一1)/2条边的无向图称无向完全图(Undireet—ed Complete Graph)
(2)若G是有向图，则O≤e≤n(n—1).
恰有n(n一1)条边的有向图称为有向完全图(Directed Complete Graph).
注意：完全图具有最多的边数.任意一对顶点间均有边相连.例如上面图4-4-1(b)的G2就是具有4个顶点的无向完全图. (二)图的边和顶点的关系 1.无向边和顶点关系
若(vi，vj)是一条无向边，则称顶点vi和vj互为邻接点(Adjacent)，或称vi和vj相接连；并称(vi，vj)依附或关联(Incident)于顶点vi和vj，或称(vi，vj)与顶点vi和vj相关联.例如图4-4-1（b）G2中：①与顶点vl相邻接的顶点是v2，v3和V4；②关联于顶点V2的边是(v1，v2)，(v2，v3)和(v2,v4) 2.有向边和顶点关系
若
(1)无向图中顶点v的度(Degree)
无向图中顶点v的度(Degree)是关联于该顶点的边的数目，记为D(v).例如图4-4-l(b)G2中顶点vl的度为3. (2)有向图顶点v的度(InDegree)
有向图中，以顶点v为终点的边的数目称为v的人度(Indegree)，记为ID(v).例如在图4-4-l
(a)G1中顶点v2的入度为1.有向图中，以顶点v为始点的边的数目，称为v的出度(Outdegree)，记为OD(v).例如在图4-4-1(a)Gl中顶点v2的出度为2.所以在有向图中，顶点v的度定义为该顶点的人度和出度之和，即D(v)=ID(v)+OD(v).例如在图4-4-1(a)G1中顶点v2的人度为l，出度 为2，则度为3.
从上述我们可以得知，无论有向图还是无向图，顶点数n、边数e和度数之间有
如下关系：
14
(三)子图
设G=(V，E)是一个图，若v’是V的子集，E’是E的子集，且E’中的边所关联的顶点均在V’中，则G’=(V’，E’)也是一个图，并称其为G的子图(Subgraph).例如图4-4-2(a)给出了有向图G1的若干子图；图4-4-2(b)
给出了无向图G2的若干个子图.
再比如，设V’={vl，v2，v3}，E’={(vl，v2)，(v2，v4)}，显然，V’属于V(G2)，E’属于E(G2)，但因为E’中序偶对(v2，v4)所关联的顶点v4不在V’中，所以(V’，E’)不是图，也就不可能是G2的子图. (四)路径(Path) 1.无向图的路径
在无向图G中，若存在一个顶点序列vp，vil’vi2，?，vim，vq，使得(vp，vil)，(vil，vi2)，?，(vim, vq)均属于E(G)，则称顶点vp到vq存在一条路径(Path). 2.有向图的路径
在有向图G中，路径也是有向的，它由E(G)中的有向边
路径长度定义为该路径上边的数目. 4.简单路径
若一条路径上除了vp和vq可以相同外，其余顶点均不相同，则称此路径为一条简单路径.例如在图G2中顶点序列v1，v2，v3，v4是一条从顶点v1到顶点v4的长度为3的简单路径.例如在图G2中，顶点序列vl，v2，v4，vl，v3是一条从顶点vl到顶点v3的长度为4的路径，但不是简单路径； 5.简单回路或简单环 (Cycle)
15
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库简单的数据结构(3)在线全文阅读。
相关推荐：