数据结构(第6章)

第6章树

树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并具有层次关系的结构，它非常类似于自然界中的树，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。本章重点讨论二叉树的存储表示及其各种运算，并研究一般树和森林与二叉树的转换关系，最后介绍树的应用实例。

6.1 树的概念

在现实生活中，存在很多可用树型结构描述的实际问题。例如，某家族的血统关系如下：张源有三个孩子张明、张亮和张丽；而张明有两个孩子张林和张维；张亮有三个孩子张平、张华和张群；张平有两个孩子张晶和张磊。这个家庭关系可以很自然地用图6.1所示的树形图来描述，它很像一棵倒画的树。其中“树根”是张源，树的“分支点”是张明、张亮和张平，该家族的其余成员均是“树叶”，而树枝（即图中的线段）则描述了家族成员之间的关系。显然，以张源为根的树是一个大家庭。它可以分成张明、张亮和张丽为根的三个小家庭；每个小家庭又都是一个树型结构。由此可抽象出树的递归定义。

定义：树（Tree）是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：

(1)有且仅有一个特定的称为根（Root）的结点；

(2)其余的结点可分为m(m≥0)个互不相交的子集T1，T2,…,Tm，其中每个子集本身又是一棵树，并称其为根的子树（Subtree）。

在树的树形图表示中，结点通常是用圆圈表示的，结点的名字一般是写在圆圈旁边(见图6.2(a))，有时亦可写在圆圈内。

树的递归定义刻画了树的固有特性，即一个非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。用该定义来分析图 6.2（a）所示的树，它是由结点的有限集T={A，B，C，D，E，F，G，H，I，J}所构成，其中A 是根结点，T中其余结点可分成三个互不相交的子集：T1={B，E，F，I，J}，T2={C},T3={D,G,H}。T1、T2和T3是根A的三棵子树，且本身又都是一棵树。例如T1，其根为B，其余结点可分为两个互不相交的子集T11={E}和T12={F，I，J}，它们都是B的子树。显然T11是只含一个根结点E的树，而T12的根F又有两颗互不相交的子树{I}和{J}，其本身又都只含有一个根结点的树。对T2和T3也

可以进行类似的分析。

在不同的应用场合，树的表示方法也不尽相同。除树型表示法外，通常还有三种表示法。例如，图 6.2（a）所示的树可以用图6.2（b）、（c）和（d）来表示，其中（b）是用集合的包含关系来描述树结构，（e）类似于书的目录，（d）则是用广义表的形势表示的。本书中主要采用图 6.2（a）所示的树形图来表示树结构。

下面给出树结构中常用的基本术语，其中有许多术语借用了家族树中的一些习惯用语。

一个结点拥有的子树数成为该结点的度（Degree）。一棵树的度是指该树中结点的最大度数。度为零的结点称为叶子（Leaf）或终端结点。如图6.2（a）中，结点A、B、E的度分别为3、2、0，树的度为3。C、E、G、H、I和J 均为叶子。度不为零的结点称为分支结点或非终端结点，除根结点之外的分支结点之外的分支结点统称为内部结点，根结点又称为开始结点。

树中某个结点的子树之根成为该结点的孩子（Child）或儿子，相应地，该结点称为孩子的双亲（Parents）或父亲。如图6.2（a）中，B是结点A的子树T1的根，故B是A的孩子，而A是B的双亲。同一个双亲的孩子成为兄弟（Sibling）。如图6.2（a）中，B、C、D互为兄弟。

若树中存在一个结点序列k1，k2，…k j，使得k i是k i+1的双亲（1≤i＜j），则称该结点序列是从k1到k j的一条路径（Path）或道路。路径的长度等于j-1，它是该路径所经过的边（即连接两个结点的线段）的数目。由路径的定义可知，若一个结点序列是路径，则在树的树形图表示中，该结点序列“自上而下”地通过路径上的每条边。例如，在图6.2（a）中，结点A到I有一条路径ABFI，它的长度为3。显然，从树的根结点到树中其余结点均存在已条唯一的路径。但是结点B和G之间不存在路径，因此既不可能从B出发“自上而下”地经过若干结点到达G，也不可能从G出发“自上而下”地经过若干结点到达B。

若树中结点k到k8存在一条路径，则称k是k8的祖先

（Ancestor），k8是k的子孙（Descendant）。显然，一个结点的祖先是从根结点到该结点路径上所经过的所有结点，而一个结点的子孙则是以该结点为根的子树中所有的结点。我们约定：结点k的祖先和子孙不包含结点k本身。例如，在图6.2（a）所示的树中，F的祖先是A和B，F 的子孙是I和J。

结点的层数（Lerel）是从根起算，设根的层数为1，其余结点的层数等于其双亲结点的层数加1。双亲在同一层的结点互为堂兄弟。树中结点的最大层数成为树的高度（Height）或深度（Depth）。以图6.2（a）为例，A的层数为1 ，I和J的层数为4，E、F和G、H互为堂兄弟，该树的高度为4。注意，很多文献中将树根的层数定义为0。

若将书中每个结点的各子树看成是从左到有由次序的（即不能互换），则称该树为有序树（Ordered Tree）；否则称为无序树（Unodered tree）。作为有序树，图6.3中的两棵树是不同的，因为结点A的两个孩子在两棵树中的左右次序不同，但作为无序树，这两棵树是相同的。以后若不特别指明，我们讨论的树都是有序树。

森林（Forest）是m（m≥0）棵互不相交的树的集合。树和森林的概念很相近，删去一棵树的根，就得到一个森林。反之，加上一个结点作树根，森林就变为一棵树。

树型结构的逻辑特征可用树中结点之间的父子关系来描述：树中任一结点都可以有零个或多个直接后继（即孩子）结点，但至多只能由一个直接前趋（即双亲）结点。树中只有根结点无前趋，它是开始结点；叶结点无后继，它们是终端结点。显然，父子关系是非线性的，故树型结构是非线性结构。祖先与子孙的关系是对父子关系得延拓，

它定义了树中结点之间的纵向次序。有序树的定义使得同一组兄弟结点之间是从左到右由长幼之分的。如果对这一关系加以延拓，规定若k1和k2是兄弟，且k1和k2的左边，则k1的任一子孙都在k2的任一子孙的左边，那么我们就定义了树中结点之间的纵向次序。

6.2 二叉树

二叉树是树型结构的一个重要类型，许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换位二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

6.2.1二叉树的定义

定义：二叉树（Binary Tree）是n（n≥0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

这也是一个递归定义。二叉树可以是空集，因此根可以有空的左子树或右子树，或者左、右子树皆为空。由此可知，二叉树有五种基本形态，如图6.4所示。

二叉树中，每个结点最多只能有两棵子树，并且有左右之分。显然，它与无序不同。其实它与度数为2的有序树也不同，这是因为在有序树中，虽然一个结点的孩子之间是由左右次序的，但是若该结点只有一个孩子，就无须区分左右次序。而在二叉树，虽然它们同图6.6中的普通树（作为

有序树或无序树）很相似，但是它们却不能等同于这棵普通树。若将这三棵树均看做普通树，则它们就是相同的了。

由此可见，二叉树并非是树的特殊情形，，尽管二者有许多相似之处，但它们是两种不同的数据结构。

6.2.2 二叉树的性质

二叉树具有以下重要性质：

性质1 二叉树第i层上的结点数目最多为2i-1（i≥1）。

证明可用数学归纳法证明之：

归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。

归纳假设：假设对所有的j（1≤j＜i）命题成立，即第j层上至多有2j-1个结点，证明j=1时命题亦成立。

归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多由两个孩子，故第i层上的结点数，至多是第i-1层上的最大结点数的2倍，即j=i时，该层上至多有2*2i-2=2j-1个结点，故命题成立。

性质2 深度为k的二叉树至多有2k-1个结点（k≥1）。

证明在具有相同深度的二叉树中，仅当每一层都含有最大结点数时其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：

20+21+…+2k-1=2k-1

故命题正确。

性质3 在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。

证明因为二叉树中所有结点的度数均不大于2，所以结点总数（记为n）应等于0度结点数，1度结点（记为n1）和2度结点数之和：

n=n0+n1+n2（6.1）另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点的总数是n1+2n2，但树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：n=n1+2n2+1 （6.2）

由式（6.1）和（6.2）得到：

n0=n2+1

满二叉树和完全二叉树是二叉数的两种特殊情形。

满二叉树(Full Binary Tree)一棵深度为k且有2k-1个结点的二叉树称为满二叉树。

图6.7(a)是一个深度为4的满二叉树。满二叉树的特点是每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。满二叉树中不存在度数为1的结点，每个分支结点均有两颗高度相同的子树，且树叶都在最下一层上。

完全二叉树(Complete Binary Tree)若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

图 6.7（b）是一棵完全二叉树。显然满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。因此，在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。例如图6.7（c）中，结点F没有左孩子而有右孩子L，故它不是一棵完全二叉树。

性质4 具有n个结点完全二叉树的深度为?lgn?+1（或?lg （n+1）?）。

证明设所求完全二叉树的深度为K，由完全二叉树的定义知道，它的前K-1层是深度为K-1的满二叉树，一共有2k-1-1个结点。由于完全二叉树深度为K，故第K层上还有若干个结点，因此该完全二叉树的结点个数n>2k-1-1。另一方面，由性质2知道n≤2k-1,即:

2k-1-1

由此可推出：2k-1≤n﹤2k，取对数后有：

K-1≤lgn

因为K-1和K是相邻的两个整数，故有K-1=?lgn?，由此即得

k=?lgn?+1

6.2.3 二叉树的存储结构

1.顺序存储结构

该方法是把二叉树的所有结点按照一定的次序存储到一片连续的存储单元中

因此，必须把结点安排成一个适当的线性序列，使得结点在这个序列中的相互位置能反映出结点之间的逻辑关系。

在一棵具有n个结点的完全二叉树中，我们从树根起，自上层到下层，每层从左至右地给所有结点编号，就能得到一个足以反映整个二叉树结构的线性序列，如图6.8所示。

完全二叉树中除最下面一层外，各层都充满了结点，每一层的结点个数恰好是上一层结点个数的2倍。因此，从一个结点的编号就可推得其双亲，左右孩子，兄弟等结点的编号。

假设编号为i的结点是k i(1≤i≤n)，则有：

(1)若i﹥1，则k i的双亲编号为?i/2?；若i=1，则k i是根结

点，无双亲。

(2)若2i≤n，则k i的左孩子的编号为2i，否则，k i无左孩

子，即k i必定是叶子，因此完全二叉数中编号i﹥?n/2?的结点必定是叶结点。

(3)若2i+1≤n则k i的右孩子的编号是2i+1；否则，k i无

右孩子。

(4)若i为奇数且不为1，则k i的左兄弟的编号是i-1；否

则，k i无左兄弟。

(5)若i为偶数且小于n，则k i的右兄弟的编号是i+1；否

则，k i无右兄弟。

由上述关系可知，完全二叉树中结点的层次序列足以反映结点之间的逻辑关系。因此可将完全二叉树中所有结点，按编号顺序依次存储在一个向量bt[0..n]中，其中bt[1..n]用来存储结点，bt[0]不用或用来存储结点数目。例如表 6.1是图 6.8所示的完全二叉树的顺序存储结构，bt[0]为结点数目，bt[7]的双亲、左右孩子分别是bt[3]、bt[14]和bt[15]。

显然，对完全二叉树而言，顺序存储结构既简单又节省存储空间。但是，一般的二叉树采用顺序存储时，为了能用结点在向量中的相对位置来表示结点之间的逻辑关系，也必须按完全二叉树的形式来存储树中的结点，这将造成存储空间的浪费。在最坏的情况下，一个深度为K的且只有K个结点的右单支树却需要2k-1个结点的存储空间。例如，只有3个结点A、B和C的右单支树，将其添上一些实际上并不存在的“虚结点”后，使它成为如图6.9所示的完全二叉树（图中方形结点为虚结点），相应的顺序存储结构见表6.2。其中的“ ”表示不存在此结点。

二叉树的顺序存储结构较简单，请自行给出其类型定义。

2.链式存储结构

从上面的介绍可知：用顺序方式存储一般的二叉树将浪存储空间，并且若在树中需要经常插入和删除结点时，由于大量地移动结点，顺序存储方式更不可取。因此，存储树的最自然的方法是链接的方法。二叉树的每个结点最多有两个孩子，用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lchild 和rchild，分别指向该结点的左孩子和右孩子，结点的结构为：

相应的类型说明为：

Typedef char DataT ype；// 应由用户定义datatype的实际类型

Typedef stuct node{

DataT ype data；

Struct node *lchild，*rchild；//左右孩子指针

} BinTNode；//结点类型

Typedef BinTNode *BinTree

在一棵二叉树中，所有类型为BinTNode的结点，再加上一个指向开始结点（即根结点）的BinTree型指针（即根指针）root，就构成了二叉树的链式存储结构，并将其称为二叉链表。例如，图6.10(a)所示二叉树的二叉链表如图6.11(b)所示。显然，一个二叉链表由根指针root惟一确定。若二叉树为空，则root=NULL。若结点的某个孩子不存在，则相应的指针为空，具有一n个结点的二叉树的二叉链表表示中，一共有2n个指针域，其中只有n-1个用来指示结点的左右孩子，其余的n+1个指针而空。

二叉链表是二叉树的最常用的存储结构，下面几节给出的有关二叉树的各种算法，大多数都是基于这种存储结构，但是树形结构还可以有其它链接存储方法。至于选用何种方法，主要依赖于所有实施的各种运算的频度。例如，若经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针parent，形成一个带双亲指针的二叉链表。图6.10(c)是图6.10(a)所示的二叉树的带双亲指针的二叉链表。

6．3 二叉树的遍历

遍历是二叉树是最重要的运算之一，它是二叉树上进行其它运算之基础。所谓遍历(Traversal)是指沿着某条搜索路

线，依次对树中每个结点均做一次且仅做一次访问，但访问结点所做的操作依赖于具体的应用问题。

遍历一个线性结构很容易，只需从开始结点出发，依次访问当前结点的后继，直至终端结点为止。线性结构里后继的唯一性决定了遍历路线只有一条。然而，二叉树中每个结点可能有两个后继结点，这将导致存在多条遍历路线。因此，我们必须找到能适用于每个结点的相同遍历规则。从二叉树的递归定义可知，一棵非空的二叉树由根结点及左右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：访问结点本身（N），遍历该结点的左子树（L），遍历该结点的右子树（R）。显然这三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。其中前三种次序是左子树总是先于右子树被遍历，而后三种次序正好相反，但由于二者对称，故我们只讨论先左后右的前三种次序。

三种遍历的差别在于访问结点的次序不同，NLR、LNR 和LRN分别表示访问结点的操作是发生在遍历其左右子树之前、之中（间）和之后。因此将这三种遍历分别命名为前序遍历、中序遍历和后序遍历。另一方面，因为被访问的结点必是某子树的根，所以N、L和R又可解释为根、根的左子树和根的右子树。因此，又可将NLR、LNR和LRN分别称为先根遍历、中根遍历和后根遍历。

根据以上介绍的遍历规则，很容易给出其递归的遍历算法，以中序遍历为例，其递归算法定义为：

若二叉树非空，则依次执行如下操作：

(1)遍历左子树；

(2)访问根结点；

(3)遍历右子树。

将操作(1)和(2)次序对调即为先序遍历，而将(2)和(3)互次序则得到后序遍历。遍历算法中的递归终止条件是二叉树为空，此时应为空操作。用二叉链表作为存储结构，上述算法可描述为：

void Inorder （BinTree T）

{//算法里①-⑥是为了说明执行过程加入的标号

①if（T）{

②inorder（T-＞ichild）；

③Printf(“℅c”,T-＞data); //访问结点

④Inorder （T-＞ichild）；

⑤}

⑥} // Inorder

为了便于理解递速归算法Inorder，现以图6.11所示的二叉树（树中 为虚结点）为例，说明该算法遍历此二叉树的执行踪迹，如图6.12所示，图中“&B”等表示结点A、B 的地址。从该图中容易看出，中序遍历图6.11所示的二叉树时，对结点的访问次序为：

D B A

E C F

通常将这个结点序列简称为该二叉树的中序序列。

类似地，对于前序遍历和后序遍历，将结点按其访问的先后次序排列起来，所得到的结点序列分别称为前序序列和后序序列。例如，图6.11所示二叉树的前后序列和后序序列分别为ABDCEF 和DBEFCA。

粗略的讲，若去掉三种遍历算法中的打印输出语句，则三种遍历算法基本上相同。这说明三种遍历的搜索路线相同，如图6.11中的虚线所示。该路线从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次。若访问结点均是第一次经过结点时进行的，则是前序遍历；若访问结点均是在第二次（或者第三次）经过结点时进行的，则是中序遍历（或后序遍历）。因此，只要将搜索路线上所有在第一

次、第二次和第三次经过的结点分别列表，即可分别得到该二叉树的前序序列、中序序列和后序序列。

上述三种序列都是线性序列，有且仅有一个开始结点和一个终端结点，其余结点都有且仅有一个前趋结点和一个后继结点。为了区别于树形结构中前趋（即双亲）结点和后继（即孩子）结点的概念，对上述三种线性序列，我们均在某结点的前趋和后继之前冠以其遍历次序名称。例如，对图6.11所示的二叉树中结点C，其前序结点D，前序后继结点是E；中序前趋结点是E，中序后继结点是F；后序前趋结点是F，后序后继结点是A。但是就该树的逻辑结构而言，C的前趋结点是A，后继结点是E和F。

因为在二叉链表上实现的有关二叉树运算均是对已存在的二叉链表进行操作，所以我们必须事先建立一棵二叉树的二叉链表。构造二叉链表的方法很多，这里介绍一个基于先序遍历的构造算法。算法的输入是二叉树的二叉链表。算法的输入是二叉树的先序序列，但必须在其中加入虚记点以示空指针的位置。例如对图6.11所示二叉树，其输入的先序序

列是：ABD???CE??F??。假设虚结点输入时以空格字符表示，相应的构造算法为：

void CreateBinTree （BinTree *T）

{//构造二叉链表。T是指向根指针的指针，故修改*T就修改了实参（根指针）本身

char ch;

if（（ch=getchar( )）==…?）

*T=NULL;//读入空格，将相应指针置空

else{//读入非空格

*T=（BinTNode *）malloc(sizeof(BinTNode))；//生成结点

(*T)->data=ch；

CreateBinTree(&(*T)->lchild)；//构造左子树

CreateBinTree(&(*T)—>rchild)；//构造右子树

}

}

调用该算法时，应将待建立的二叉链表的根指针的地址作为实参。例如，设root是一根指针（即它的类型是BinTree）；则调用CreateBinTree（& root）后root就指向了已构造好的二叉链表的根结点。

本节介绍的算法其时间复杂程度均为o(n)，这里n为树的结点数。

6.4线索二叉树

当用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右孩子结点的指针域，所以从任一结点出发只能直接找到该结点的左、右孩子，而一般情况下无法直接找到该结点在某种遍历序列中的前趋和后继结点。为此，若在每个结点中增加两个指针域来存放遍历时得到的前趋和后继信息，将大大降低存储空间的利用率。但是在n个结点的二叉链表中含有n+1个空指针域，因此可以利用这些

空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针，这种附加的指针称为“线索”，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树（Threaded Binary Tree）

为了区分一个结点的指针域是指向其孩子的指针、还是指向其前趋或后继的线索，可在每个结点中增加两个标志域，这样，线索链表中的结点结构为：

其中:

左标志ltag=0：lchild是指向结点的左孩子的指针；

左标志ltag=1：lchild是指向结点的前趋的左线索。

右标志rtag=0：rchild是指向结点的右孩子的指针；

右标志rtag=1：rchild是指向结点的后继的右线索。

例如图6.13(a)所示的中序线索二叉树，它的线索链表见图6.13(b)。图中的实线表示指针，虚线表示线索。结点c 的左线索为空，表示c是中序序列的开始结点，它没有前趋；结点E的右线索为空，表示E是中序序列的终端结点，它没有后继。显然在线索二叉树中，一个结点是叶结点的充要条件为：它的左右标志均是1。

将二叉树变为线索二叉树的过程称为线索化。按某种次序将二叉树线索化，只要按该次序遍历二叉树，在遍历过程中用线索取代空指针。为此，附设一个指针pre始终指向刚刚访问过的结点，而指针p指示当前正在访问的结点。显然结点*pre是结点*p的前趋，而*p是*pre的后继。下面给出将二叉树按中序线索化的算法。该算法与中序遍历算法类似，只需要将遍历算法中访问结点*p的操作具体化为在*p 及其中序前趋*pre（若pre≠NULL）之间建立线索。显然pre 的初值应为NULL。

Typedef enum{Link，Thread}PointerT ag；

//枚举值Link和Thread分别为0，1

Typedef struct node{

Data Type data；

PointerT ag ltag，rtag；//左右标志

Struct node *lchild，*rchild；

}BinThrNode；

typedef BinThrNode *BinThrTree；

BinThrNode *pre= NULL；//全局量

void InorderThreading(BinThrTree p)

{//将二叉树p中序线索化

if(p){//p非空时，当前访问结点是*p

InorderThreading(p->lchild)；// 左子树线索化

//以下直至右子树线索化之前相当于遍历算法中访问结点的操作

p->ltag=( p-> lchild)? Link:Thread；

//左指针非空时左标志为Link(即0)，否则为Thread（即1）

p->rtag=( p-> rchild)? Link:Thread；

if(pre){ //若*p的前趋*pre存在

if(pre->rtag==Thread)// *p的前趋右标志为线索

pre-> rchild= =p// 令*pre的右线索指向中序后继

if(p->ltag==Thread)// *p的左标志为线索

p->lchild=pre// 令*p的左线索指向中序前趋

}

pre=p；//令pre是下一访问结点的中序前趋

InorderThreeding(p->rchild)；//右子树线索化} //endif

} //InorderThreading

显然，和中序遍历算法一样，递归过程中对每结点仅做一次访问，因此对于n个结点的二叉树，算法的时间复杂度亦为O(n)。

类似地可得前序线索化和后序线索化算法。

建立了线索链表之后，我们来讨论线索二叉树上的运算。下面介绍线索二叉树上两种常用的运算。

1．找某结点*p在指定次序下的前趋和后继结点

在中序线索二叉树中，查找结点*p的中序后继结点分两种情形：

（1）若*p的右子树空（即p—>rtag为Thread），则p —>rchild为右线索，直接指向*p的中序后继。例如，图6。13是D的中序后继是A。

（2）若*p的右子树非空（即p—>rtag为link），则*p的中序后继必是其右子树中第一个中序遍历到的结点，也就是从*p的右孩子开始，沿该孩子的左链往下查找，直至找到一个没有左孩子的结点为止。该结点是*p的右子树中“最左下”的结点，它就是*p的中序后继结点。如图6。13所示，*p的中序后继结点是Rk(k≥1).Rk可能有右孩子也可能无右孩子，若Rk无右孩子，则它必定是叶结点。若k=1，则表示*p的右孩子R1是*p的中序后继。如图6。13中，A的中序后继是F，它有右孩子；F的中序后继是H，它无右孩子；B的中序后继是D，它是B的右孩子（即D相当于是R1）。

基于上述分析，不难给出中序线索二叉树中求中序

后继结点的算法。

BinThrNode * InorderSuccessor(BinThrNode*p)

{//在中序线索树中找结点*p的中序后继，设p非空

BinThrNode *q；

if (p->rtag==Thread)//*p的右子树为空

return p->rchild；//返回右线索所指的中序后继else{

q=p->rchild；//从*p的右孩子开始查找

while(q->ltag==Link)

q=q->lchild; //左子树非空时，沿左链往下查找

return q;//当q的左子树为空时，它就是最左下结点

}

}

显然，该算法的时间复杂程度不超过树的高度h，即O(h)。

由于中序是一种对称序，故在中序线索二叉树中查找结点*p的中序前趋结点与找中序后继结点的方法完全对称。若*p的左子树为空，则p->lchild为左线索，直接指向*p的中序前趋结点；若*p的左子树非空，则从*p的左孩子出发，沿右指针链往下查找，直到找到一个没有右孩子的结点为止。该结点是*p的左子树中“最右下”的结点，它是*p的左子树中最后一个中序遍历到的结点，即*p的中序前趋结点（见图6.15）。

由上述讨论可知：若结点*p的左子树（或右子树）非空，则*p的中序前趋（或中序后继）是从*p的左孩子（或右孩子）开始往下查找，由于二叉链表中结点的链域是向下链接的，所以在非线索二叉树中亦同样容易找到*p的中序前趋（或中序后继）；若结点*p的左子树（或右子树）为空，则在中序线索二叉树中是通过*p的左线索（或右线索）直接找到*p的中序前趋（或中序后继），但中序线索一般都是“向上”指向其祖先结点，而二叉链表中没有向上的链接，因此在这种情况下，对于非线索二叉树，仅从*p出发无法找到其中序前趋（或中序后继），而必须从根结点开始中序遍历，才能找到*p的中序前趋（或中序后继）。由此可见，线索使得查找中序前趋和中序后继变得简单有效，然而线索对于查找指定结点的前序前趋和后序后继却没什么帮助，请看下面的分析。

在后序线索二叉树中，查找指定结点*p的后序前趋结点的规律是：

(1)若*p的左子树为空，同p-> lchild 是前趋线索，指示其后序前趋结点。例如，在图6.16中，H的后序前趋是B，F的后序前趋是G。

(2)若*p的左子树非空，则p->lchild 不是前趋线索。但因为在后序遍历时，根是在遍历其左右子树之后被访问的，故*p的后序前趋必是两子树中最后一个遍历到的结点。因此，当*p的右子树非空时，*p的右孩子必是其后序前趋，

数据结构第六章一二次作业

上机题 （1）编写完整程序，用先序遍历法建立二叉树的二叉链 表存储结构。输出该二叉树的先、中、后序遍历结 点访问次序以及层次遍历结点访问次序。（建议结 点数据域类型为char） // erchashu.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include #include typedef struct node { char data; struct node *lchild, *rchild; }*BiT, BiTNode; BiT crtBT() { char ch; BiT bt; ch=getchar(); if(ch=='#') return NULL; bt=new BiTNode(); bt->data=ch; bt->lchild=crtBT(); bt->rchild=crtBT(); return bt;

} void preorder(BiT bt) { if(bt) { printf("%c",bt->data); preorder(bt->lchild); preorder(bt->rchild); } //printf("\n"); } void midorder(BiT bt) { if(bt) { midorder(bt->lchild); printf("%c",bt->data); midorder(bt->rchild); } //printf("\n"); } void lasorder(BiT bt) { if(bt) { lasorder(bt->lchild); lasorder(bt->rchild); printf("%c",bt->data); } //printf("\n"); } int main(int argc, char* argv[]) { BiT bt; bt=crtBT(); preorder(bt); printf("\n"); midorder(bt); printf("\n"); lasorder(bt); printf("\n"); return 0; } （2)从键盘输入n个数据建立n元完全二叉树顺序存储结

数据结构-第六章-图-练习题及答案详细解析(精华版)

图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度

⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。

数据结构(C++版)课后作业6-8章附答案

第6 章图 课后习题讲解 1. 填空题 ⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵任何连通图的连通分量只有一个，即是（）。【解答】其自身 ⑶图的存储结构主要有两种，分别是（）和（）。【解答】邻接矩阵，邻接表 ⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。【解答】求第j列的所有元素之和 ⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。【解答】出度 ⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 （8）如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 2. 选择题 ⑵n个顶点的强连通图至少有（）条边，其形状是（）。A n B n+1 C n-1 D n×(n-1) E 无回路 F 有回路G 环状H 树状【解答】A，G ⑶含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（）。 A 1 B n/2 C n-1 D n 【解答】C 【分析】若超过n-1，则路径中必存在重复的顶点。 （4）最小生成树指的是（）。 A 由连通网所得到的边数最少的生成树 B 由连通网所得到的顶点数相对较少的生成树 C 连通网中所有生成树中权值之和为最小的生成树 D 连通网的极小连通子图 【解答】C （5）下面关于工程计划的AOE网的叙述中，不正确的是（） A 关键活动不按期完成就会影响整个工程的完成时间 B 任何一个关键活动提前完成，那么整个工程将会提前完成 C 所有的关键活动都提前完成，那么整个工程将会提前完成 D 某些关键活动若提前完成，那么

数据结构第六章树和二叉树习题及答案

习题六树和二叉树 一、单项选择题 1．以下说法错误的是（） A. 树形结构的特点是一个结点可以有多个直接前趋 B. 线性结构中的一个结点至多只有一个直接后继 C. 树形结构可以表达（组织）更复杂的数据 D. 树（及一切树形结构）是一种”分支层次”结构 E. 任何只含一个结点的集合是一棵树 2. 下列说法中正确的是（） A. 任何一棵二叉树中至少有一个结点的度为2 B. 任何一棵二叉树中每个结点的度都为2 C. 任何一棵二叉树中的度肯定等于2 D. 任何一棵二叉树中的度可以小于2 3. 讨论树、森林和二叉树的关系，目的是为了（） A. 借助二叉树上的运算方法去实现对树的一些运算 B. 将树、森林按二叉树的存储方式进行存储 C. 将树、森林转换成二叉树 D. 体现一种技巧，没有什么实际意义4．树最适合用来表示（） A. 有序数据元素 B .无序数据元素 C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B ．11 C ．15 D ．不确定 6. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1, M2和M3与森林F 对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B ．M1+M2 C ．M3 D ．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A．250 B ．500 C ．254 D ．505 E ．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为（） A. 不确定 B . 2n C . 2n+1 D . 2n-1 9．二叉树的第I 层上最多含有结点数为（） I I-1 I-1 I A．2I B ．2 I-1 -1 C ．2 I-1 D ．2 I -1 10．一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有（）结点A．2h B ．2h-1 C ．2h+1 D ．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A.指向最左孩子 B .指向最右孩子 C .空D .非空 12．已知一棵二叉树的前序遍历结果为为（）。 A．CBEFDA B ．FEDCBA 13．已知某二叉树的后序遍历序列是（）。 ABCDEF中序遍历结果 为 C ．CBEDFA D dabec, 中序遍历序列是 CBAEDF则后序遍历的结 果 ．不定 debac , 它的前序遍历是

数据结构 第六章 图 练习题及答案详细解析

图 1. 填空题 ⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk

数据结构课后习题及解析第六章汇总

第六章习题 1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 3．已知一棵度为k的树中有n 1个度为1的结点，n 2 个度为2的结点，……，n k 个度为k的结点， 则该树中有多少个叶子结点并证明之。 4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。 5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 6．给出满足下列条件的所有二叉树： ①前序和后序相同 ②中序和后序相同 ③前序和后序相同 7． n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child 域有多少个？ 8．画出与下列已知序列对应的树Ｔ： 树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。 9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 请为这8个字母设计哈夫曼编码。 10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因. 11. 画出和下列树对应的二叉树：

12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。 15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。 16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。 17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。 18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。 19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指：在二叉树中不存在子树个数为1的结点。 20．计算二叉树最大宽度的算法。二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。 21．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。 22. 证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树； 给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树； 23. 二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 24. 二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。 实习题 1.[问题描述] 建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序）， 打印输出遍历结果。 [基本要求] 从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。 [测试数据] ABCффDEфGффFффф（其中ф表示空格字符） 输出结果为：先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA 2．已知二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的竖向显示（竖向显示就是二叉树的按层显示）。

数据结构与算法第六章课后答案第六章 树和二叉树

第6章 树和二叉树（参考答案） 6.1 (1)根结点a 6.2 三个结点的树的形态： 三个结点的二叉树的形态： （1） （1） （2） （4） （5） 6．3 设树的结点数是n ，则 n=n0+n1+n2+……+nm+ (1) 设树的分支数为B ，有 n=B+1 n=1n1+2n2+……+mnm+1 (2) 由（1）和（2）有： n0=n2+2n3+……+(m-1)nm+1 6.4 (1) k i-1 (i 为层数) (2) (n-2)/k+1 (3) (n-1)*k+i+1 (4) (n-1)%k !=0; 其右兄弟的编号 n+1 6.5（1）顺序存储结构 注：#为空结点

6.6 (1) 前序 ABDGCEFH (2) 中序 DGBAECHF (3) 后序 GDBEHFCA 6.7 (1) 空二叉树或任何结点均无左子树的非空二叉树 (2) 空二叉树或任何结点均无右子树的非空二叉树 (3) 空二叉树或只有根结点的二叉树 6.8 int height(bitree bt) // bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度 { int bl,br; // 局部变量，分别表示二叉树左、右子树的高度 if (bt==null) return(0); else { bl=height(bt->lchild); br=height(bt->rchild); return(bl>br? bl+1: br+1); // 左右子树高度的大者加1（根） } }// 算法结束 6.9 void preorder(cbt[],int n,int i); // cbt是以完全二叉树形式存储的n个结点的二叉树，i是数 // 组下标，初始调用时为1。本算法以非递归形式前序遍历该二叉树 { int i=1,s[],top=0; // s是栈，栈中元素是二叉树结点在cbt中的序号 // top是栈顶指针，栈空时top=0 if (n<=0) { printf(“输入错误”);exit（0）；} while (i<=n ||top>0) { while(i<=n) {visit(cbt[i]); // 访问根结点 if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空，其编号进栈 i=2*i;// 先序访问左子树 } if (top>0) i=s[top--]; // 退栈，先序访问右子树 } // END OF while (i<=n ||top>0) }// 算法结束 //以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示void preorder(bt[],int n,int i); // bt是以完全二叉树形式存储的一维数组，n是数组元素个数。i是数 // 组下标，初始调用时为1。 { if (i<=n && bt[i]!=’*’) { visit(bt[i]); preorder(bt,n,2*i); preorder(bt,n,2*i+1); }// 算法结束 6.10 int equal(bitree T1,bitree T2); // T1和T2是两棵二叉树，本算法判断T1和T2是否等价 // T1和T2都是空二叉树则等价 // T1和T2只有一棵为空，另一棵非空，则不等价 // T1和T2均非空，且根结点值相等，则比较其左、右子树

数据结构课后习题答案第六章

第六章树和二叉树（下载后用阅读版式视图或web版式可以看清） 习题 一、选择题 1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为( )。 A.向量 B.树C图 D.二叉树 2．树最合适用来表示( )。 A.有序数据元素 B元素之间具有分支层次关系的数据 C无序数据元素 D.元素之间无联系的数据 3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。 A. la (2b (3d,3e),2c) B. a(b(D,e),c) C. a(b(d,e),c) D. a(b,d(e),c) 4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。 A. 2h_l B.h C．2h-1 D. 2h 5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。 A. 2i B. 2i-l C. 2i+l D. 2i+2 6.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为( )。 A.3 B.4 C.5 D.6 7.深度为5的二叉树至多有( )个结点。 A. 31 B. 32 C. 16 D. 10 8.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。 A. 15 B. 16 C. 17 D. 47 9.题图6-1中，( )是完全二叉树，( )是满二叉树。 10.在题图6-2所示的二叉树中：

(1)A结点是 A.叶结点 B根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点 (2)J结点是 A.叶结点 B．根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点 (3)F结点的兄弟结点是 A.E B.D C．空 D.I (4)F结点的双亲结点是 A.A B.B C.C D.D (5)树的深度为 A.1 B.2 C.3 D.4 (6)B结点的深度为 A.1 B.2 C.3 D.4 (7)A结点所在的层是 A.1 B.2 C.3 D.4 11.在一棵具有35个结点的完全二叉树中，该树的深度为( )。 A.5 B.6 C.7 D.8 12. 一棵有124个叶结点的完全二叉树，最多有( )个结点。 A．247 B．248 C．249 D．250 13.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若 有左子树，则左子树是结点( )。 A. R[2i+l] B. R[2i] C.R[i/2] D. R[2i-1] 14.在一非空二叉树的中序遍历序列中，根结点的右边( )。 A.只有右子树上的所有结点 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点 15．一棵度为m的树中，有n i个度为1的结点，有n2个度为2的结点……，有n m个度为m的结点，则该树的叶结点数为( )。 A. n1+n2+...+n m B. (m-l) n m+...+n2+1

数据结构第六章题目讲解

02一选择题：1、以下说法错误的是 ①树形结构的特点是一个结点可以有多个直接前趋 ②线性结构中的一个结点至多只有一个直接后继③树形结构可以表达(组织)更复杂的数据④树(及一切树形结构)是一种"分支层次"结构⑤任何只含一个结点的集合是一棵树 2．深度为6的二叉树最多有( )个结点①64 ②63 ③32 ④31 3 下列说法中正确的是 ①任何一棵二叉树中至少有一个结点的度为2 ②任何一棵二叉树中每个结点的度都为2 二叉树可空 ③任何一棵二叉树中的度肯定等于2 ④任何一棵二叉树中的度可以小于2 4 设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有（）个结点。 ①n1-1 ②n1③n1+n2+n3④n2+n3+n4 二．名词解释：1 结点的度 3。叶子 4。分支点 5。树的度 三填空题二叉树第i(i>=1)层上至多有_____个结点。 1、深度为k(k>=1)的二叉树至多有_____个结点。 2、如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X 有：若i=1,则结点X是_ ____；若i〉1,则X的双亲PARENT(X)的编号为__ ____。 若2i>n，则结点X无_ _____且无_ _____；否则，X的左孩子LCHILD(X)的编号为____。若2i+1>n，则结点X无__ ____；否则，X的右孩子RCHILD(X)的编号为_____。 4．以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。 Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶子数count的初值为0*/ {if(t!=NULL) {if((t->lchild==NULL)&&(t->rchild==NULL))__ __; countleaf(t->lchild,&count); countleaf(t->rchild,&count);} } 5 先根遍历树和先根遍历与该树对应的二叉树，其结果_____。 6 由____转换成二叉树时，其根结点的右子树总是空的。 7 哈夫曼树是带权路径度___ _____的树，通常权值较大的结点离根__ ______。 8 一棵树的形状如图填空题33所示，它的根结点是_____，叶子结点是______，结点H的度是_____，这棵树的度是_____，这棵树的深度是________，结点F的儿子结点是______，结点G的父结点是_____。

数据结构(C语言版)第6章习题答案

第6章树和二叉树自测卷解答 一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分） （√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点） （×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1） （×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。 （√）10. 〖01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的结点。 最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5 二、填空（每空1分，共15分） 1．由３个结点所构成的二叉树有5种形态。 2. 【计算机研2000】一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 3．一棵具有２５７个结点的完全二叉树，它的深度为9。 （注：用? log2(n) ?+1= ? 8.xx ?+1=9 4.【全国专升本统考题】设一棵完全二叉树有700个结点，则共有350个叶子结点。 答：最快方法：用叶子数＝[n/2]＝350 5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。 答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0. 6.【严题集6.7③】一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为2。 答：当k=1(单叉树)时应该最深，深度＝n（层）；当k=n-1（n-1叉树）时应该最浅，深度＝2（层），但不包括n=0或1时的特例情况。教材答案是“完全k叉树”，未定量。) 7. 【试题1】二叉树的基本组成部分是：根（N）、左子树（L）和右 子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即 按N L R次序），后序法（即按L R N次序）和中序法（也称

数据结构 第6章习题答案

第6章树和二叉树习题解答 一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分） （√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点） （×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1） （×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。 （√）10. 〖01年考研题〗具有12个结点的完全二叉树有5个度为2的结点。 最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5 二、填空（每空1分，共15分） 1．由３个结点所构成的二叉树有5种形态。 2. 【计算机研2000】一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 3．一棵具有２５７个结点的完全二叉树，它的深度为9。 （注：用? log2(n) ?+1= ? 8.xx ?+1=9 4.【全国专升本统考题】设一棵完全二叉树有700个结点，则共有350个叶子结点。 答：最快方法：用叶子数＝[n/2]＝350 5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。 答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0. 6.【严题集6.7③】一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为2。 答：当k=1(单叉树)时应该最深，深度＝n（层）；当k=n-1（n-1叉树）时应该最浅，深度＝2（层），但不包括n=0或1时的特例情况。教材答案是“完全k叉树”，未定量。) 7. 【试题1】二叉树的基本组成部分是：根（N）、左子树（L）和右 子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即 按N L R次序），后序法（即按L R N次序）和中序法（也称

数据结构第六章知识题课

1、下图所示的4棵二叉树中，不是完全二叉树的是（ ） 2、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（ ）。 A 、正确 B 、错误 C 、不一定 3、已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是（ ）。 A 、acbed B 、decab C 、deabc D 、cedba 4、如果T2是由有序树T 转换而来的二叉树，那么T 中结点的后序就是T2中结点的（ ）。 A 、前序 B 、中序 C 、后序 D 、层次序 5、深度为5的二叉树至多有（ ）个结点。 A 、16 B 、32 C 、31 D 、10 6、在一个非空二叉树的中序遍历序列中，根结点的右边（ ）。 A B C D

A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的部分结点 D、只有左子树上的所有结点 7、树最适合用来表示（）。 A、有序数据元素 B、无序数据元素 C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据。 8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。 A、不发生改变 B、发生改变 C、不能确定 D、以上都不对 9、实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（）存储结构。 A、二叉链表 B、广义表存储结构 C、三叉链表 D、顺序存储结构 10、对一个满二叉树，m个树叶，n个结点，深度为h，则（）。 A、n=m+h B、h+m=2n C、m=h-1 D、n=2h-1 11、设n，m为二叉树上的两个结点，在中序遍历时，n在m前的条件是（）。 A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙12．已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，

数据结构第六章

一、单项选择题 1.已知一个长度为16的顺序L，气元素按关键字有序排列，或采用折半查找法查找一个不在L中存在的元素，则关键字的比较次数最多的是（）。 A．4 B. 5 C. 6 D. 7 2.顺序查找适合于存储结构为（）的线性表。 A.顺序存储结构或链式存储结构 B.散列存储结构 C.索引存储结构 D.压缩存储结构 3.对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任意一个元素的查找成功的平均查找长度为（）。 2 B.(n+1)/2 C.(n-1)/2 4 4.对长度为3的顺序表进行查找，若查找的第一个元素概率为1/2，查找第二个元素的概率为1/3，查找第三个元素的概率为1/6，则查找表中任意一个元素的平均查找长度为( )。 3 3 3 5.当采用分块查找时，数据的组织方式为（）。 A.数据分成若干块，每块内数据有序 B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 6.下列关于二分查找的叙述中，正确的是（）。 A．表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D．表必须有序，且表只能以顺序方式存储 7.使用二分（折半）查找元素的速度比用顺序法（）。 A.必然快 B.必然慢 C.相等 D.不能确定 8.已知一个长度为16的顺序表，其元素按关键字有序排列，若采用折半查找查找一个不存在的元素，则比较的次数至少是（），至多是（）。

《数据结构》第六章作业参考答案

第六章 树和二叉树 6.3 6.14 (a)右单支树 (b) 左单支树 (c)只有根结点的二叉树 6.15 后序遍历序列：GDBEHFCA 后序线索二叉树 6.19 (b) (c) 具有3个结点的树的形态有两种： 具有3个结点的二叉树形态有五种

(d) 6.21 (a) (b) (c) (d) (e)

6.22 (1) (a)A (b)ABC (c)ABC (d)ABCEIJFGKHD (2) (a)A (b)CBA (c)BCA (d)BIJEFKGHCDA 6.26 赫夫曼树 提高通信信道的利用率，提高报文发送速度和节省存储空间。 6．27 6.42 解:依题意:计算一棵二叉树的叶子结点数的递归模型如下: ?? ? ??>-+>-==>-=>-===其它 且若若)()()(1 )(0)(rchild b f lchild b f b f NULL rchild b NULL lchild b b f NULL b b f

int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 { if(!T) return 0; //空树没有叶子 else if(!T->lchild && !T->rchild) return 1; //叶子结点 else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数}//LeafCount_BiTree 6.43 void Bitree_Revolute(Bitree T)//交换所有结点的左右子树 { if(T) { T->lchild<->T->rchild; //交换左右子树 Bitree_Revolute(T->lchild); Bitree_Revolute(T->rchild); //左右子树再分别交换各自的左右子树 } }//Bitree_Revolute 6.47 void LayerOrder(Bitree T)//层序遍历二叉树 { InitQueue(Q); //建立工作队列 if(T) EnQueue(Q,T); while(!QueueEmpty(Q)) { DeQueue(Q,p); visit(p->data); if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); } }//LayerOrder 6.56 BTNode *PreOrder_Next(BTNode *p)//在先序后继线索二叉树中查找结点p的先序后继,并返回指针 { if(p->RTag==Thread) return p->rchild; else if(p->lchild) return p->lchild; else return p->rchild; }//PreOrder_Next

第六章 数据结构习题pll

习题6解答 判断题： 1.二叉树中每个结点有两个子女结点，而对一般的树则无此限制，因此二叉树是树的特殊情形。（） 2.二叉树就是结点度为2的树。 ( ) 3.二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。 ( ) 4.当k≥1时，高度为k的二叉树至多有21 k个结点。 5.完全二叉树的某结点若无左孩子，则它必是叶结点。 ( ) 6.用一维数组存放二叉树时，总是以前序遍历顺序存储结点。（） 7.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。（） 8.存在这样的二叉树，对它采用任何次序的遍历，结果相同。（） 9.中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。（） 10.将一棵树转换成二叉树后，根结点没有左子树。（） 11.由树转换成二叉树，其根结点的右子树总是空的。（） 12.前序遍历森林和前序遍历与该森林对应的二叉树其结果不同。（） 13.在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。（） 14.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。（） 15.霍夫曼树一定是满二叉树。（） 16.树的度是树内各结点的度之和。（） 17.由二叉树的结点构成的集合可以是空集合。（） 18.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。（） 选择题： 19.树最适合用来表示( )。 A．有序数据元素 B. 无序数据元素 C．元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 20.如果结点A有3个兄弟，而且B是A的双亲，则B的度是( )。 A. 4 B. 5 C. 1 D. 3 21.下列有关二叉树的说法正确的是( )。 A．二叉树的度为2 B. 一棵二叉树度可以小于2 C．二叉树中至少有一个结点的度为2 D. 二叉树中任一个结点的度都为2 22.以下说法错误的是( )。 A．二叉树可以是空集 B. 二叉树的任一结点都可以有两棵子树 C．二叉树与树具有相同的树形结构 D. 二叉树中任一结点的两棵子树有次序之分 23.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。 A．15 B. 16 C. 17 D.47 24. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[i]若有左子女，则左子女是结点( )。

数据结构复习题-第6章答案2014-6-16

第6章树和二叉树 一、选择题（每小题1分，共10分） 1.以下数据结构中，（ A ）是非线性数据结构。 A.树 B.线性表 C.队列 D.栈 2.在一棵二叉树中第五层上的结点数最多为（ B ）。 A.8 B.15 C.16 D.32 3. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ A ）。 A. CBEFDA B. FEDCBA C. CBEDFA D. 不定 4.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( B ）。 A.9 B.11 C.15 D.不确定 5.给定二叉树如图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,7,5,6,1,2,4，则其遍历方式是（D ）。 A. LRN B. NRL C. RLN D. RNL 6.在下列存储形式中，哪一个不是树的存储形式？（ D ） A.双亲表示法 B.孩子表示法 C.孩子兄弟表示法 D.顺序存储表示法 7.有n个叶子的哈夫曼树的结点总数为（D ）。 A．不确定B．2n C．2n+1 D．2n-1 8.设i为n个结点的完全二叉树结点编号，i=1，2，3...n；若i≤（n-1）/2时，结点i的右孩子为（ B ） A.2i B.2i+1 C.2i-1 D.i+1 9. 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ C ）。 A.23 B.37 C.44 D.46 10.一棵具有n个结点的完全二叉树的树高度（深度）是（ A ）。 A. +1 B. log2n+1 C. D. log2n-1 11.由权值分别为7，9，4，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ）。 A.36 B.60 C.48 D.53 12.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ）。 A. 24 B. 71 C. 48 D. 53 13.具有35个结点的完全二叉树的深度为( B )。 A. 5 B. 6 C. 7 D. 8 14.由权值分别为３,８,６,２,５的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ D ）． A．24 B．55 C．72 D．53 15.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序( A )。 A．不发生改变 B．发生改变 C．不能确定 D．以上都不对

数据结构课后习题第六章

一．选择题 1.设高度为h的二叉树只有为0和2的结点，则此类二叉树的结点数至少有（）个，至多有几个（） A.2h B.2h-1 C.2h+1 D.2h-1 E.2h-1 F.2h+1 2.高度为h的完全二叉树有（）个结点，至多有（）个结点。 A.2h B. 2h-1 C. 2h+1 D. 2h-1 3.具有n个结点的满二叉树有（）个叶结点。 A.n/2 B.(n-1)/2 C.(n+1)/2 D.n/2+1 4.一棵具有n个叶节点的哈夫曼树，共有（）个结点。 A.2n B. 2n-1 C.2n+1 D.2n-1 5.一棵具有25个结点的完全二叉树最多有（）个结点。 A.48 B.49 C.50 D.51 6.已知二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列是（）。 A.CBEFDA B.FEDCBA C.CBEDFA D.不定 7.已知二叉树的中序遍历序列是debac,后序遍历序列是dabec,则前序遍历序列是（）。 A.acbed B.decab C.deabc D.cedba 8.下面4棵二叉树中，（）不是完全二叉树。 A C D 9.在线索化二叉树中，t所指结点没有左子树的充分必要条件是（）。 A.t->left=null B. t->ltag=1 C. t->left=null且t->ltag=1 D.以上都不对 10.下列线索二叉树中（用虚线表示线索），符合后续线索树的定义的是（）。

11.算术表达式a+b*(c+d/c)转换为后缀表达式是（）。 A．ab+cde/* B．abcde/+*+ C．abcde/*++ D. abcde*/++ 12.具有10个叶结点的二叉树中有（）个度为2的结点。 A．8 B.9 C.10 D.11 13.一个具有1025个结点的二叉树的高h为（）。 A.11 B.10 C.11~1025 D.10~1024 14.前序遍历与中序遍历结果相同的二叉树为（）；前序遍历和后序遍历结果相同 的二叉树为（）的二叉树。 A.空二叉树 B.只有根结点 C.根结点无左孩子 D.根结点无右孩子 15.一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 （）。 A.所有非叶结点均无左孩子 B.所有非叶结点均无右孩子 C.只有一个叶子结点 D.A和B同时成立 16.某二叉树的中序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A.空或只有一个根结点 B.任一非叶结点无左子树 C.高度等于其结点数 D.任一非叶结点无右子树 17.线索二叉树是一种（）结构。 A. 逻辑B逻辑和存储C物理D线性 18.n个结点的线索二叉树上含有的线索数为（）。 A.2n B.n-1 C.n+1 D.n 19.由3个结点可以构造出（）种不同的二叉树。 A.2 B.3 C.4 D.5 20.若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（）。 A.n-1 B.「n/m」-1 C.「（n-1）/（m-1）」 D. 「n/（m-1）」-1 21.对n（n>=2）个权值均不同的字符构成的哈夫曼树，关于该树的叙述中，错误的是 （）。 A.该树一定是一棵完全二叉树 B.树中一定没有度为1的结点