第五章树和二叉树
一、单项选择题
1．关于二叉树的下列说法正确的是 (1)。
A．二叉树的度为2 B．二叉树的度可以小于2
C．每一个结点的度都为2 D．至少有一个结点的度为
2．设深度为h(h>0)的二叉树中只有度为0和度为2的结点，则此二叉树中所含的结点总数至少为（2）。
A．2h B．2h-1 C．2h+1 D．h+1
3．在树中，若结点A有4个兄弟，而且B是A的双亲，则B的度为 (3) 。
A．3 B．4 C．5 D．6
4．若一棵完全二叉树中某结点无左孩子，则该结点一定是 (4) 。
A.度为1的结点 B．度为2的结点 C．分支结点 D．叶子结点
5．深度为k的完全二叉树至多有 (5) 个结点，至少有 (6) 个结点。
A．2k-1-1 B．2k-1 C．2k-1 D．2k
6．前序序列为ABC的不同二叉树有 (7) 种不同形态。
A．3 B．4 C．5 D．6
7．若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其后序序列为 (8) ，层次序列为 (9) 。
A．BCAGFED B．DAEBCFG C．ABCDEFG D．BCAEFGD
8．在具有200个结点的完全二叉树中，设根结点的层次编号为1，则层次编号为60的结点，其左孩子结点的层次编号为 (10) ，右孩子结点的层次编号为 (11) ，双亲结点的层次编号为 (12)。
A．30 B．60 C．120 D．121
9．遍历一棵具有n个结点的二叉树，在前序序列、中序序列和后序序列中所有叶子结点的相对次序 (13) 。
A.都不相同 B．完全相同 C．前序和中序相同 D．中序与后序相同
10．在由4棵树组成的森林中，第一、第二、第三和第四棵树组成的结点个数分别为30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为（14），根结点的右子树中结点个数为 (15) 。
A．20 B．29 C．30 D．35
11.具有n个结点(n>1)的二叉树的前序序列和后序序列正好相反，则该二叉树中除叶子结点外每个结点 (16) 。
A.仅有左孩子 B．仅有右孩子 C．仅有一个孩子 D．都有左、右孩子
12．判断线索二叉树中p结点有右孩子的条件是 (17) 。
A.p!=NULL B．p->rchild!=NULL C．p->rtag=0 D．p->rtag=1
13．将一棵树转换成二叉树，树的前根序列与其对应的二叉树的 (18) 相等。树的后根序列与其对应的二叉树的 (19)相同。
A．前序序列 B．中序序列 C．后序序列 D．层次序列
14．设数据结构(D，R)，D={dl，d2，d3，d4，d5，d6}，R={
(20)： A．线性表 B．二叉树C．队列 D．栈
(21)：A．前序 B．中序 C．后序 D．层次
15．对于树中任一结点x，在前根序列中序号为pre(x)，在后根序列中序号为post(x)，
若树中结点x是结点y的祖先，下列（22）条件是正确的。
A.pre(x) B．pre(x) C. pre(x)>pre(y)且post(x) D．pre(x)>pre(y)且post(x)>post(y) 16．每棵树都能惟一地转换成对应的二叉树，由树转换的二叉树中，一个结点N的左孩子是它在原树对应结点的 (23) ，而结点N的右孩子是它在原树里对应结点的 (24) 。 A．最左孩子 B．最右孩子 C．右邻兄弟 D．左邻兄弟17．二叉树在线索化后，仍不能有效求解的问题是 (25) 。 A．前序线索树中求前序直接后继结点 B．中序线索树中求中序直接前驱结点 C．中序线索树中求中序直接后继结点 D．后序线索树中求后序直接后继结点 18．一棵具有124个叶子结点的完全二叉树，最多有 (26)个结点。 A．247 B．248 C．249 D．250 。 二、填空题 1.树中任意结点允许有（1）孩子结点，除根结点外，其余结点（2）双亲结点。 2.若一棵树的广义表表示为A(B(E，F)，C(C(H，I，J，K)，L)，D(M(N)))。则该树的度为 (3) ，树的深度为 (4) ，树中叶子结点个数为 (5) 。 3．若树T中度为1、2、3、4的结点个数分别为4、3、2、2，则T中叶子结点的个数是 (6) 。 4．一棵具有n个结点的二叉树，若它有m个叶子结点，则该二叉树中度为1的结点个数是 (7) 。 5．深度为k(k>0)的二叉树至多有 (8) 个结点，第i层上至多有 (9) 个结点。 6．已知二叉树有52个叶子结点，度为1的结点个数为30则总结点个数为 (10) 。 7．已知二叉树中有30个叶子结点，则二叉树的总结点个数至少是（11）。 8．高度为6的完全二叉树至少有 (12) 个结点。 9．一个含有68个结点的完全二叉树，它的高度是 (13) 。 10．已知一棵完全二叉树的第6层上有6个结点(根结点的层数为1)，则总的结点个数至少是 (14) ，其中叶子结点个数是（15）。 11．已知完全二叉树第6层上有10个叶子结点，则这棵二叉树的结点总数最多是（16）。 12．一棵树转换成二叉树后，这棵二叉树的根结点一定没有 (17) 孩子，若树中有m 个分支结点，则与其对应的二叉树中无右孩子的结点个数为（18）。 13．若用二叉链表示具有n个结点的二叉树，则有（19）个空链域。 14．具有m个叶子结点的哈夫曼树，共有（20）个结点。 15．树的后根遍历序列与其对应的二叉树的（21）遍历序列相同。 16．线索二叉树的左线索指向其（22），右线索指向其（23）。 三、应用题 1．具有n个结点的满二叉树的叶子结点个数是多少? 2．列出前序遍历序列是ABC的所有不同的二叉树。 3．已知二叉树的层次遍历序列为ABCDEFGHIJK，中序序列为DBGEHJACIKF，请构造一棵二叉树。 4．已知二叉树的中序遍历序列是ACBDGHFE，后序遍历序列是ABDCFHEG，请构造一棵二 叉树。 5．已知二叉树的前序、中序和后序遍历序列如下，其中有一些看不清的字母用*表示，请先填写*处的字母，再构造一棵符合条件的二叉树，最后画出带头结点的中序线索链表。 (1)前序遍历序列是：*BC***G* (2)中序遍历序列是：CB*EAGH* (3)后序遍历序列是：*EDB**FA 6．将下图所示的森林转换成一棵二叉树，并画出这棵二叉树的顺序存储结构。 7．将下图所示的二叉树还原成森林。 8．对于给定的一组权值{3，5，6，7，9}，请构造相应的哈夫曼树，并计算其带权路径长度。 四、算法设计题 1．请设计一个算法，求以孩子兄弟链表表示的树中叶子结点个数。 2．请编写一个算法，实现将以二叉链表存储的二叉树中所有结点的左、右孩子进行交换。 3．请编写一个算法，将以二叉链表存储的二叉树输出其广义表表示形式。 4．请编写一个算法，判断以二叉链表存储的二叉树是否为完全二叉树。 5．假设二叉树采用链接存储方式存储，编写一个二叉树先序遍历和后序遍历的非递归算法。.. 6．已知一棵二叉树用二叉链表存储，t指向根结点，p指向树中任一结点。请编写一个非递归算法，实现求从根结点t到结点p之间的路径。 第6章树和二叉树作业 1、假设在树中，结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树的树边集合为{ (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h), (a,c) } ，用树型表示法表示该树，并回答下列问题： ①哪个是根结点? 哪些是叶子结点? 哪个是g的双亲? 哪些是g的祖先? 哪些是g的孩子? 那些是e的子孙? 哪些是e的兄弟? 哪些是f 的兄弟? ②b和n的层次各是多少? 树的深度是多少? 以结点c为根的子树的深度是多少? 2、一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问： ①各层的结点数是多少? ②编号为i的结点的双亲结点(若存在)的编号是多少? ③编号为i的结点的第j个孩子结点(若存在)的编号是多少? ④编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少? 3、设有如图6-27所示的二叉树。 ①分别用顺序存储方法和链接存储方法画 出该二叉树的存储结构。 ②写出该二叉树的先序、中序、后序遍历序 列。 4、已知一棵二叉树的先序遍历序列和中序遍 历序列分别为ABDGHCEFI和 GDHBAECIF，请画出这棵二叉树，然后给 出该树的后序遍历序列。 5、设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG 和DECBHGFA ，请画出这棵二叉树，然后给出该树的先序序列。 6、已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif 和gdbkeihfca，请画出这棵二叉树对应的中序线索树和后序线索树。 7、以二叉链表为存储结构，请分别写出求二叉树的结点总数及叶子结点总数的算法。 8、设图6-27所示的二叉树是森林F所对应的二叉树，请画出森林F。 9、设有一棵树，如图6-28 所示。 ①请分别用双亲表示法、孩 子表示法、孩子兄弟表示法 给出该树的存储结构。 ②请给出该树的先序遍历 序列和后序遍历序列。 ③请将这棵树转换成二叉 树。 10、设给定权值集合 w={3,5,7,8,11,12} ，请构造 关于w的一棵huffman树，并求其加权路径长度WPL 。 11、假设用于通信的电文是由字符集{a, b, c, d, e, f, g, h}中的字符构成，这8个字符在电文中出现的概率分别为{0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10} 。 ①请画出对应的huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。 ②求出每个字符的huffman编码。 第六章树和二叉树 1 一、选择题 1. 已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( ) A．-A+B*C/DE B．-A+B*CD/E C．-+*ABC/DE D．-+A*BC/DE 2. 在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③B．②③④C．②④D．①④ 3. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（） A．5 B．6 C．7 D．8 4. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（） A．m-n B．m-n-1 C．n+1 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.有关二叉树下列说法正确的是（） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 8. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 A．250 B．500 C．254 D．505 E．以上答案都不对 9. 具有10个叶结点的二叉树中有（）个度为2的结点。 A．8 B．9 C．10 D．ll 10. 深度为h的满m叉树的第k层有（）个结点。(1= //二叉树的基本操作 #include 树作业（一） 【作业要求】 1.提交文档，写出答案 2.如果有需要绘图，可以手绘拍照节省时间 【题目说明】 1 单项选择题 1. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_B_。 A. 正确 B. 错误 2. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 B 个。 A．15 B．16C．17D．47 3. 按照二叉树的定义，具有3个结点的不同形状的二叉树有__C__种。 A. 3 B. 4 C. 5 D. 6 4. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有__C__种。 A. 5 B. 6 C. 30 D. 32 5. 深度为5的二叉树至多有__C__个结点。 A. 16 B. 32 C. 31 D. 10 6. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_ _B__。 A. 2h B. 2h-1 C. 2h+1 D. h+1 7. 对一个满二叉树，m个树叶，n个结点，深度为h，则__D__ 。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-1 8. 如图1所示的4棵二叉树，__C__不是完全二叉树。 (A) (B) (C) (D) 图1 9. 树最适合用来表示__C__。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 2 填空题 1. 举例说明树和二叉树的两个主要差别_树的节点的最大度数没有限制，但是二叉树的节点的最大度数为2___、__树中节点的子节点没有顺序之分，但是二叉树中节点的子节点分左孩子、右孩子__。 2. 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如下图所示，请画出该二叉树的形态。 123456789101112131415161718192021 e a f d g c j l h b 一棵二叉树的顺序存储数组t 3. 深度为k的完全二叉树至少有__2k?1__个结点。至多有__2k?1__个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是__2k?2+1__。 4、已知一棵完全二叉树的第6层（设根是第1层）有8个叶结点，则该完全二叉树的结点个数最多是多少？ 二叉树的基本操作实现及其应用 一、实验目的 1．熟悉二叉树结点的结构和对二叉树的基本操作。 2．掌握对二叉树每一种操作的具体实现。 3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 4.会用二叉树解决简单的实际问题。 二、实验内容 设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1 按先序次序建立一个二叉树， 2按（A:先序 B:中序 C:后序）遍历输出二叉树的所有结点 以上比做，以下选做 3求二叉树中所有结点数 4求二叉树的深度 三、实验步骤 ㈠、数据结构与核心算法的设计描述 /* 定义DataType为char类型 */ typedef char DataType; /* 二叉树的结点类型 */ typedef struct BitNode { DataType data; struct BitNode *lchild,*rchild; }*BitTree; 相关函数声明： 1、/* 初始化二叉树，即把树根指针置空 */ void BinTreeInit(BitTree *BT) { BT=(BitTree)malloc(sizeof(BitNode)); BT->data=NULL; cout<<"二叉树初始化成功!"< 实验三二叉树的基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 题目一：二叉树的基本操作实现（必做题） [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 三、算法设计 1、主要思想：根据二叉树的图形结构创建出二叉树的数据结构，然后 用指针对树进行操作，重点掌握二叉树的结构和性质。 2、本程序包含四个模块： （1）结构体定义 （2）创建二叉树 （3）对树的几个操作 （4）主函数 四、调试分析 这是一个比较简单程序，调试过程中并没有出现什么问题，思路比较清晰 五、实验结果 六、总结 此次上机实验对二叉树进行了以一次实际操作，让我对二叉树有了更深的了解，对二叉树的特性有了更熟悉的认知，让我知 道了二叉树的重要性和便利性，这对以后的编程有更好的帮助。 七、源程序 #include 树 (树根结点的高度为1) 一、选择题 3．以下说法错误的是( )。 A．完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B．在三叉链表上，二叉树的求双亲操作很容易实现 C．在二叉链表上，求根以及求左、右孩子等操作很容易实现 D．在二叉链表上，求双亲操作的时间性能很好 4．以下说法错误的是( )。 A．一般在哈夫曼树中，权值越大的叶子离根结点越近 B．哈夫曼树中没有度数为1的分支结点 C．若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点D．若初始森林中共有n棵二叉树， 进行2n-1次合并后才能剩下一棵最终的哈夫曼树 5．深度为6的二叉树最多有( )个结点。 A．64 B．63 C．32 D．31 6．将含有41个结点的完全二叉树从根结点开始编号，根为1号， 后面按从上到下、从左到右的顺序对结点编号， 那么编号为21的双亲结点编号为( )。 A．10B．11 C．41 D．20 7．设深度为k的二叉树上只有度为0和度为2的结点， 则这类二叉树上所含结点总数最少( )个。 A．k+l B．2k C．2k-1D．2k+1 8．下列说法中正确的是( )。 A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的每个结点的度肯定等于2 D．任何一棵二叉树中的每个结点的度都可以小于2 9．一棵二叉树满足下列条件：对任意结点，若存在左、右子树， 则其值都小于它的左子树上所有结点的值， 而大于右子树上所有结点的值。 现采用( )遍历方式就可以得到这棵二叉树所有结点的递减序列。A．前序B．中序C．后序D．层次 10．如图6-1所示的二叉树的中序遍历序列是( )。 A．abcdgef B．dfebagc C．dbaefcg D．defbagc 数据结构二叉树基本操作 (1). // 对二叉树的基本操作的类模板封装 //------------------------------------------------------------------------------------------------------------------------ #include 《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。 问题分析： 二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题，我觉得应该： 1、建立二叉树； 2、通过递归方法来遍历（先序、中序和后序）二叉树； 3、通过队列应用来实现对二叉树的层次遍历； 4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等； 5、运用广义表对二叉树进行广义表形式的打印。 算法规定： 输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。 输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。对二叉树的一些运算结果以整型输出。 程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。 测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E 预测结果：先序遍历ABCDEGF 中序遍历CBEGDFA 后序遍历CGEFDBA 层次遍历ABCDEFG 广义表打印A（B（C,D（E（,G）,F））） 叶子数3 深度5 宽度2 非空子孙数6 度为2的数目2 度为1的数目2 查找5，成功，查找的元素为E 删除E后，以广义表形式打印A（B（C,D（,F））） 输入二：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B 预测结果：先序遍历ABDEHCFG 中序遍历DBHEAGFC 后序遍历DHEBGFCA 层次遍历ABCDEFHG 广义表打印A（B(D,E(H)),C(F(,G))） 叶子数3 深度4 宽度3 非空子孙数7 度为2的数目2 度为1的数目3 查找10，失败。 习题6树和二叉树 说明： 本文档中，凡红色字标出的题请提交纸质作业，只写题号和答案即可。 6.1单项选择题 1. 由于二叉树屮每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法_B_。 A. 正确 B.错误 2. 假定在一棵二叉树屮，双分支结点数为15,单分支结点数为30个，则叶子结点数为 B_个。 A. 15 B. 16 C. 17 D. 47 3. 按照二叉树的定义，具有3个结点的不同形状的二叉树有_C_种。 A. 3 B.4 C. 5 D. 6 4. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有_C_种。 A.5 B.6 C. 30 D. 32 5. 深度为5的二叉树至多有_C_个结点。 A. 16 B. 32 C. 31 D. 10 6. 设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点 数至少为 B 。 A. 2h B. 2h-l C. 2h+l D. h+l 7. 对一个满二叉树，m 个树叶，n 个结点，深度为h,则_A_。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h -l 8. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_A_。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 9. 如杲某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的后 序为_C_。 A. uwvts B. vwuts C. wuvts D. wutsv 10. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_A_。 A.正确 B.错误 11. 某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是 dgbaechf,则其后序遍历的结点访问顺序是_D_。 A. bdgcefha B. gdbecfha 12. 在一非空二叉树的中序遍历序列中, A.只有右子树上的所有结点 13. 如图6.1所示二叉树的中序遍历序列是_B_。 14. 一棵二叉树如图6.2所示，其中序遍历的序列为 B 。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh C. bdgaechf D. gdbehfca 根结点的右边_A_。 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 图6」 浙江大学城市学院实验报告 课程名称数据结构 实验项目名称实验十二叉树的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期 一.实验目的和要求 1、掌握二叉树的链式存储结构。 2、掌握在二叉链表上的二叉树操作的实现原理与方法。 3、进一步掌握递归算法的设计方法。 二.实验内容 1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test10.cpp，验证头文件中各个操作。 二叉树二叉链表存储表示如下： typedef struct BiTNode { TElemType data ; struct BiTNode *lchild , *rchild ; }BiTNode,*BiTree ; 基本操作如下： ①void InitBiTree(BiTree &T ) //初始化二叉树T ②void CreateBiTree(BiTree &T) //按先序遍历序列建立二叉链表T ③bool BiTreeEmpty (BiTree T); //检查二叉树T是否为空，空返回1，否则返回0 ④int BiTreeDepth(BiTree T); //求二叉树T的深度并返回该值 ⑤void PreOrderTraverse (BiTree T); //先序遍历二叉树T ⑥void InOrderTraverse (BiTree T); //中序遍历二叉树T ⑦void PostOrderTraverse (BiTree T); //后序遍历二叉树T ⑧void DestroyBiTree(BiTree &T) //销毁二叉树T 本程序由SOGOF完成 该完整程序主要是递归函数的使用及模板的使用，完成了对二叉树基本的链表操作，主要有二叉树的建立，前序、中序、后序遍历，求树的高度，每层结点数（包含树的最大宽度），左右结点对换，二叉树的内存释放，求解树的叶子数。 #include 作业-树和二叉树 树 (树根结点的高度为1) 一、选择题 3．以下说法错误的是( )。 A．完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B．在三叉链表上，二叉树的求双亲操作很容易实现 C．在二叉链表上，求根以及求左、右孩子等操作很容易实现 D．在二叉链表上，求双亲操作的时间性能很好4．以下说法错误的是( )。 A．一般在哈夫曼树中，权值越大的叶子离根结点越近 B．哈夫曼树中没有度数为1的分支结点C．若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点 D．若初始森林中共有n棵二叉树， 进行2n-1次合并后才能剩下一棵最终的哈夫曼树 5．深度为6的二叉树最多有( )个结点。A．64 B．63 C．32 D．31 6．将含有41个结点的完全二叉树从根结点开始编号，根为1号， 后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为( )。 A．10B．11 C．41 D．20 7．设深度为k的二叉树上只有度为0和度为2的结点， 则这类二叉树上所含结点总数最少( )个。A．k+l B．2k C．2k-1D．2k+1 8．下列说法中正确的是( )。 A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的每个结点的度肯定等于2 D．任何一棵二叉树中的每个结点的度都可以小于2 9．一棵二叉树满足下列条件：对任意结点，若存在左、右子树， 则其值都小于它的左子树上所有结点的值， 而大于右子树上所有结点的值。 现采用( )遍历方式就可以得到这棵二叉树所有结点的递减序列。 A．前序B．中序C．后序D．层次 10．如图6-1所示的二叉树的中序遍历序列是( )。 A．abcdgef B．dfebagc C．dbaefcg D．defbagc 11．已知某二叉树的后序遍历序列是deacb，中序遍历序列是deabc， 它的前序遍历序列是( )。 A．acbed B．baedc C．dceab D．cedba 12．某二叉树的前序遍历的结点访问顺序是abdgcefh， 中序遍历的结点访问顺序是dgbaechf， 则其后序遍历的结点访问顺序是( )。 二叉树的基本操作及实现 二叉树的基本操作及实现的代码如下： #include 数据结构程序报告（3） 2011.3.29 2. 需求分析： （1）功能：表达式可以用二叉树表示，对于简单的四则运算，请实现以下功能 【1】对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号），能够在计算机内部构造出一棵表达式二叉树，并且图示出来（图形的形式）。【2】对于构造好的内部表达式二叉树，按照用户的要求输出相应的前缀表达式（不带括号）、中缀表达式（可以带括号，但不允许冗余括）或后缀表达式（不带括号）。 提示：所谓中缀表达式中的冗余括号，就是去掉括号后不影响表达式的计算顺序。例如：“（c+b）+a”中的括号是冗余的，可以表示成不冗余的“c+b+a”。 （2）输入输出要求：请输入字符串表达式： 树形二叉树（图形显示） 中缀表达式为： 前缀表达式为： 后缀表达式为： 3.概要设计：（算法） 分成两部分完成： 【1】前缀、中缀、后缀表达式->二叉树表达式 前缀表达式->二叉树表达式：（a）碰到操作数则把其值赋给相应的新申请的二叉树结点，地址压栈；（b）碰到操作符则把其值赋给相应的新申请的二叉树，并从栈中弹出两个地址，分别作为其右指针和左指针，然后再把其地址压栈，最后一个地址即为二叉树的根结点地址。 中缀表达式->二叉树表达式：把中缀表达式转换成后缀表达式，然后再建立二叉树。 后缀表达式->二叉树表达式：（a）碰到操作数则把其值赋给相应的新申请的二叉树结点，若栈为空则地址压栈，若非空则取栈顶元素，若栈顶元素的左孩子为空则当前结点设为其左孩子，左孩子为满则设为其右孩子再压栈；（b）碰到操作数则把其值赋给相应的新申请的二叉树结点，取栈顶元素，若栈顶元素的左孩子为空则设为其左孩子，左孩子为满则设为其右孩子开始那个元素地址为根结点地址，开始时用变量root保存。 【1】二叉树表达式->前缀、中缀、后缀表达式 二叉树表达式->前缀表达式：对二叉树表达式进行前序遍历。 二叉树表达式->中缀表达式：对二叉树表达式进行中序遍历，若结点操作符的优先级高于其左或右子树，在打印相应的子树之前先打印开括号，在打印相应的子树最后在打印一个闭括号。 二叉树表达式->后缀表达式：对二叉树表达式进行后序遍历。 创作编号： GB8878185555334563BT9125XW 创作者：凤呜大王* //二叉树的基本操作 #include cout<<"--------------请选择------------"< 二叉树的创建与遍历 一、实验目的 1．学会实现二叉树结点结构和对二叉树的基本操作。 2．掌握对二叉树每种操作的具体实现，学会利用递归和非递归方法编写对二叉树这种递归数据结构进行处理的算法。 二、实验要求 1．认真阅读和掌握和本实验相关的教材内容。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归和非递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历。 四、实验步骤 源程序代码1 #include 第6章树(基础知识)习题练习答案 6.1.假设在树中，结点x是结点y的双亲时,用(x,y)来表示树边.已知一棵树边的集合为{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法出此树，并回答下列问题： (1)哪个是根结点? (2)哪些是叶结点? (3)哪个是g的双亲? (4)哪些是g的祖先? (5)哪些是g的孩子? (6)哪些是e的子孙? (7)哪些是e的兄弟?哪些是f的兄弟? (8)结点b和n的层次各是多少? (9)树的深度是多少? (10)以结点c为根的子树的深度是多少? (11) 树的度数是多少? 答： a是根结点； dmnfjkl是叶结点； c是g的双亲； c,a是g的祖先； j,k是g的孩子； imn是e的子孙； d是e的兄弟；g,h是f的兄弟； b的层次是2；n的层次是5； 树的深度是5； 以c为根的子树深度是3； 树的度数是3； 6.2 一棵度为2的有序树与一棵二叉树有何区别? 答： 一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。 6.3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 答： 三个结点的树如下：只有两种形态 ○○ / \ | ○ ○○ | ○ 三个结点的二叉树如下所示：有五种形态： (1) (2) (3) (4) (5) ○○○○○ / \ / / \ \ ○○○○○○ / \ / \ ○○○○ 6.4 已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，...n m个度为m的结点，问该树中有多少片叶子? 解： 设该树中的叶子数为n0个。该树中的总结点数为n个，则有： n=n0+n1+n2+…+n m (1) 又有除根结点外，树中其他结点都有双亲结点，且是唯一的(由树中的分支表示)，所以，有双亲的结点数为： n-1=0*n0+1*n1+2*n2+…+m*n m (2) 联立(1)(2)方程组可得： 叶子数为：n0=1+0*n1+1*n2+2*n3+...+(m-1)*n m 6.5一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问： (1)各层的结点数目是多少? (2)编号为i的结点的双亲结点(若存在)的编号是多少? 二叉树的基本操作实验报告 学号姓名实验日期 2012-12-26 实验室计算机软件技术实验指导教师设备编号 401 实验内容二叉树的基本操作 一实验题目 实现二叉树的基本操作的代码实现 二实验目的 1、掌握二叉树的基本特性 2、掌握二叉树的先序、中序、后序的递归遍历算法 3、通过求二叉树的深度、度为2的结点数和叶子结点数等算法三实习要求 (1)认真阅读书上给出的算法 (2)编写程序并独立调试 四、给出二叉树的抽象数据类型 ADT BinaryTree{ //数据对象D:D是具有相同特性的数据元素的集合。 //数据关系R: // 若D=Φ，则R=Φ，称BinaryTree为空二叉树; // 若D?Φ，则R={H}，H是如下二元关系; // (1)在D中存在惟一的称为根的数据元素root，它在关系H下无前驱; // (2)若D-{root}?Φ，则存在D-{root}={D1,Dr}，且D1?Dr =Φ; // (3)若D1?Φ，则D1中存在惟一的元素x1， // (4)(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树;(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。 //基本操作: CreateBiTree( &T, definition ) // 初始条件:definition给出二叉树T的定义。 // 操作结果:按definiton构造二叉树T。 BiTreeDepth( T ) // 初始条件:二叉树T存在。 // 操作结果:返回T的深度。 PreOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:先序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 InOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 PostOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 LeafNodes(p) // 初始条件:二叉树T存在。 // 操作结果:返回T的叶子结点数。 第六章树和二叉树 一、应用题 1．已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少？ 2．高度为10的二叉树，其结点最多可能为多少？ 3．任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有（m-1）个度为2，其余度为1。 4. 已知A[1..N]是一棵顺序存储的完全二叉树，如何求出A[i]和A[j]的最近的共同祖先？ 5．已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？ 6．一棵共有n个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。 7．设T是具有n个内结点的扩充二叉树，I是它的内路径长度，E是它的外路径长度。试利用归纳法证明E=I+2n, n>=0. 8．试证明:同一棵二叉树的所有叶子结点，在前序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如前序abc，后序bca，对称序bac。 9. 由二叉树的中序序列及前序序列能唯一的建立二叉树，试问中序序列及后序序列是否也能唯一的建立二叉树，不能则说明理由，若能对中序序列DBEAFGC 和后序序列DEBGFCA构造二叉树。 10. 由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。 二、算法设计题 1. 给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。 2．编程求以孩子—兄弟表示法存储的森林的叶子结点数。 3．要求二叉树按二叉链表形式存储， （1）写一个建立二叉树的算法。 （2）写一个判别给定的二叉树是否是完全二叉树的算法。 完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K 的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。 4．假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。（注:已知树中结点数）第6章 树和二叉树 作业
第6章树和二叉树作业
二叉树的基本 操作
树和二叉树作业(一)
实验三 二叉树的基本操作实现及其应用
实验三二叉树的基本操作
作业-树和二叉树
数据结构——二叉树基本操作源代码
数据结构实验三——二叉树基本操作及运算实验报告
习题6树和二叉树.docx
实验10 二叉树的基本操作
二叉树基本操作经典实例
作业-树和二叉树
二叉树的基本操作及实现.cpp
表达式用二叉树表示
二叉树的基本 操作
C++二叉树的创建与遍历实验报告
中南大学数据结构与算法第6章树和二叉树课后作业答案
二叉树的基本操作实验报告
第六章-树和二叉树-作业
相关主题
文本预览