数据结构二叉树习题含答案

1、2.1 创建一颗二叉树创建一颗二叉树，可以创建先序二叉树，中序二叉树，后序二叉树。我们在创建的时候为了方便，不妨用#表示空节点，这时如果先序序列是：6 4 2 3 # # # # 5 1 # # 7 # #，那么创建的二叉树如下：下面是创建二叉树的完整代码：穿件一颗二叉树，返回二叉树的根2.2 二叉树的遍历二叉树的遍历分为：先序遍历，中序遍历和后序遍历，这三种遍历的写法是很相似的，利用递归程序完成也是灰常简单的：2.3 层次遍历层次遍历也是二叉树遍历的一种方式，二叉树的层次遍历更像是一种广度优先搜索（BFS）。因此二叉树的层次遍历利用队列来完成是最好不过啦，当然不是说利用别的数据结构不能完成。

2、2.4 求二叉树中叶子节点的个数树中的叶子节点的个数 = 左子树中叶子节点的个数 + 右子树中叶子节点的个数。利用递归代码也是相当的简单，2.5 求二叉树的高度求二叉树的高度也是非常简单，不用多说：树的高度 = max(左子树的高度，右子树的高度) + 1 2.6 交换二叉树的左右儿子交换二叉树的左右儿子，可以先交换根节点的左右儿子节点，然后递归以左右儿子节点为根节点继续进行交换。树中的操作有先天的递归性。2.7 判断一个节点是否在一颗子树中可以和当前根节点相等，也可以在左子树或者右子树中。 2.8 求两个节点的最近公共祖先求两个节点的公共祖先可以用到上面的：判断一个节点是否在一颗子

3、树中。（1）如果两个节点同时在根节点的右子树中，则最近公共祖先一定在根节点的右子树中。（2）如果两个节点同时在根节点的左子树中，则最近公共祖先一定在根节点的左子树中。（3）如果两个节点一个在根节点的右子树中，一个在根节点的左子树中，则最近公共祖先一定是根节点。当然，要注意的是：可能一个节点pNode1在以另一个节点pNode2为根的子树中，这时pNode2就是这两个节点的最近公共祖先了。显然这也是一个递归的过程啦：可以看到这种做法，进行了大量的重复搜素，其实有另外一种做法，那就是存储找到这两个节点的过程中经过的所有节点到两个容器中，然后遍历这两个容器，第一个不同的节点的父节点就是我们要找的节点

4、啦。 实际上这还是采用了空间换时间的方法。2.9 从根节点开始找到所有路径，使得路径上的节点值和为某一数值（路径不一定以叶子节点结束）这道题要找到所有的路径，显然是用深度优先搜索（DFS）啦。但是我们发现DFS所用的栈和输出路径所用的栈应该不是一个栈，栈中的数据是相反的。看看代码：注意使用的两个栈。结点的度: 结点下面关联几个节点 就是结点的度树的度: 结点度最高的度为树的度叶子结点: 结点下面没子结点 度为0的结点分支标点: 不是叶子结点的结点内部结点:不是最顶层也是不是最底层的结点父结点, 兄弟结点, 子结点都是相对的.层次: 顶层为0层(有些定为1层)下面依次加一层树的结点总数

5、(n)=总度数(k)+1            1         |        2       3      4  |             5  6  7              8   

6、                                    9    10树的遍历:前序遍历: 根->最左子结点->再最左边(先访问根, 再访问子结点, 子结点, 可以看作一个子树)后序遍历: 先子节点, 再根节点层次遍历: 是分层一个一个来.前: 1, 2, 5, 6, 7, 3, 4, 8, 9, 10后: 5, 6, 7, 2, 3, 9, 10, 8, 4, 1层:

7、 1, 2, 3, 4, 5, 6, 7, 8, 9, 10二叉树:二叉树最多只能有两个结点. 二叉树分左子右子, 一般树不分.满二叉树: 每个节点都是两个节点完全二叉树: 如果一个二叉树有n层, n-1层是满树, 最后一层要从左到右排列.特性:1.二叉树第i层, 最多只能有2(i-1)个结点(i>=1)2.深度为k的二叉树最多有2k-1个结点(k>=1)3.对任何一棵二叉树, 如果其叶子结点数为n0, 度为2的结点数为n2, 则n0 = n2 + 14.如果一个完全二叉树的结点按层次编号.1)如果i=1,则结点i无父结点, 是二叉树的根; 如果i > 1, 则父结点是 i/

8、2 向下取整 ;2)如果2i > n, 则结点i为叶子结点, 无左子结点; 否则, 其左子结点是结点2i;3)如2i + 1 > n, 则结点i无右子叶点, 否则, 其右子结点是结点2i+1.二叉树多一个中序遍历:先左再根再右树与二叉树转换:一棵树转成等价的二叉树任意结点的孩子结点转成二叉树的左子树结点, 兄弟结点转为二叉树的右子结点画图时可以断开除最左边的结点, 然后水平连结点兄弟结点(共同父结点, 唐兄节点不连)原来左边连线就是左结点, 先连成的是右结点（2）由3 个结点可以构造出多少种不同的二叉树？（ ）A2 B3 C4 D5 （3）一棵完全二叉树上有1001个结点，其中叶子

9、结点的个数是（ ）。A250 B 500 C254 D501 （4）一个具有1025个结点的二叉树的高h为（ ）。A11 B10 C11至1025之间 D10至1024之间（5）深度为h的满m叉树的第k层有（ ）个结点。(1=<k=<h) Amk-1 Bmk-1 Cmh-1 Dmh-1（6）利用二叉链表存储树，则根结点的右指针是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空（7）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号。A先序 B. 中序 C. 后序 D. 从

10、根开始按层次遍历（8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。A前序 B中序 C后序 D按层次（9）在下列存储形式中，（ ）不是树的存储形式？A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法（10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）。A所有的结点均无左孩子 B所有的结点均无右孩子C只有一个叶子结点 D是任意一棵二叉树（11）某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。A空或只有一个结点 B任一结点无左子树 C高度等于其结点数 D任一结点无右子树（12）若

11、X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（ ）。AX的双亲 BX的右子树中最左的结点 CX的左子树中最右结点 DX的左子树中最右叶结点（13）引入二叉线索树的目的是（ ）。A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结果唯一（14）线索二叉树是一种（ ）结构。A逻辑 B 逻辑和存储 C物理 D线性（15）设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。A n-1 Bn C n+1 D n+2判断 1. 二叉树是度为2的有序树。

12、15; 2. 完全二叉树一定存在度为1的结点。× 3. 对于有N个结点的二叉树，其高度为log2n。× 4深度为K的二叉树中结点总数2k-1。 22完全二叉树中，若一个结点没有左孩子，则它必是树叶。 23. 二叉树只能用二叉链表表示。× 27. 用链表(llink-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。× 28. 二叉树中每个结点至多有两个子结点,而对一般树则无此限制.因此,二叉树是树的特殊情形.

13、 × 30在二叉树的第i层上至少有2i-1个结点(i>=1)。× 34在二叉树中插入结点，则此二叉树便不再是二叉树了。× 35二叉树是一般树的特殊情形。× 36树与二叉树是两种不同的树型结构。 39度为二的树就是二叉树。× 41.下面二叉树的定义只有一个是正确的，请在正确的地方画“”。 （1）它是由一个根和两株互不相交的、称为左子树和右子树的二叉树组成。 （2）（a）在一株二叉树的级i上，最大结点数是2i-1（i1） （b）在一棵深度为k的

14、二叉树中，最大结点数是2k-1+1（k1）。 （3）二叉树是结点的集合，满足如下条件： （a）它或者是空集； （b）或者是由一个根和两个互不相交的、称为左子树和右子树的二叉树组成。 50. 用链表（llink-rlink）存储包含n个结点的二叉树时，结点的2n个指针区域中有n+1个空指针。)2应用题（1）试找出满足下列条件的二叉树 先序序列与后序序列相同 中序序列与后序序列相同 先序序列与中序序列相同 中序序列与层次遍历序列相同先序遍历二叉树的顺序是“根左子树右子树”，中序遍历“左子树根右子树”，后序遍历顺序是：“左子树右子树根，根据以上原则，

15、本题解答如下：（）  若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树（）  若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树（）  若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树（）  若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树（2）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C画出这棵二叉树。画出这棵二叉树的后序线索树。将这棵二叉树转换成对应的树（或森林）。  ABMFD(3)CEMHG&#

16、160;       (1) (2)（3） 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 试为这8个字母设计赫夫曼编码。 试设计另一种由二进制表示的等长编码方案。 对于上述实例，比较两种方案的优缺点。解：方案1；哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。 w=7,19,2,6,32,3,21,10，按哈夫曼规则：【（2,3），6, (7,10)】, 19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0

17、 17 10 6 0 12 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3方案比较：字母编号对应编码出现频率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10字母编号对应编码出现频率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案1的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2

18、.61方案2的WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3结论：哈夫曼编码优于等长二进制编码 （4）已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。初态: weightparentlchildrchild13000212000370004400052000680007110008 0009 00010 00011 00012 00013 000 weightparentlc

19、hildrchild13800212120037100044900528006810007111100859519911481015123611201397122713210134701112终态3算法设计题以二叉链表作为二叉树的存储结构，编写以下算法：（1）统计二叉树的叶结点个数。int LeafNodeCount(BiTree T)if(T=NULL)return 0; /如果是空树，则叶子结点个数为0else if(T->lchild=NULL&&T->rchild=NULL)return 1; /判断该结点是否是叶子结点（左孩子右孩子都为空），若是则返回1e

20、lsereturn LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);（2）判别两棵树是否相等。（3）交换二叉树每个结点的左孩子和右孩子。void ChangeLR(BiTree &T)BiTree temp;if(T->lchild=NULL&&T->rchild=NULL)return;elsetemp = T->lchild;T->lchild = T->rchild;T->rchild = temp;ChangeLR(T->lchild);ChangeLR(T

21、->rchild);（4）设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。void DoubleTraverse(BiTree T)if(T = NULL)return;else if(T->lchild=NULL&&T->rchild=NULL)cout<<T->data;elsecout<<T->data;DoubleTraverse(T->lchild);cout<<T->data;D

22、oubleTraverse(T->rchild);（5）计算二叉树最大的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。题目分析 求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。int Width(BiTree bt)/求二叉树bt的最大宽度if (bt=null) return (0); /空二叉树宽度为0else BiTree Q;/Q是队列，元素为二叉树结点指针，容量足够大 front=1;rear=1;last=1;/front队头指针,rear队尾指针,last同层最右结点在队列中的位

23、置 temp=0; maxw=0; /temp记局部宽度, maxw记最大宽度 Qrear=bt; /根结点入队列 while(front<=last) p=Qfront+; temp+; /同层元素数加1 if (p->lchild!=null) Q+rear=p->lchild; /左子女入队if (p->rchild!=null) Q+rear=p->rchild; /右子女入队 if (front>last) /一层结束， last=rear;if(temp>maxw) maxw=temp;/last指向下层最右元素, 更新当前最大宽度 tem

24、p=0; /if /while return (maxw);/结束width（6）用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目。int Level(BiTree bt) /层次遍历二叉树，并统计度为1的结点的个数int num=0; /num统计度为1的结点的个数 if(bt)QueueInit(Q); QueueIn(Q,bt)；/Q是以二叉树结点指针为元素的队列 while(!QueueEmpty(Q)p=QueueOut(Q); printf(p->data); /出队,访问结点if(p->lchild && !p->rchild |!p-

25、>lchild && p->rchild)num+;/度为1的结点if(p->lchild) QueueIn(Q,p->lchild); /非空左子女入队if(p->rchild) QueueIn(Q,p->rchild); /非空右子女入队 /if(bt) return(num); /返回度为1的结点的个数 （7）求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。题目分析因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长

26、路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。void LongestPath(BiTree bt)/求二叉树中的第一条最长路径长度BiTree p=bt,l,s; /l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点 int i，top=0,tag,longest=0; while(p | top>0) while(p) s+top=p；tagtop=0; p=p->Lc; /沿左分枝向下 if(tagtop=1) /当前结点的右分枝已遍历 if(!stop->Lc && !stop->Rc) /只有到叶子结点时，才查看路径

27、长度if(top>longest) for(i=1;i<=top;i+) li=si; longest=top; top-;/保留当前最长路径到l栈，记住最高栈顶指针，退栈 else if(top>0) tagtop=1; p=stop.Rc; /沿右子分枝向下 /while(p!=null|top>0)/结束LongestPath（8）输出二叉树中从每个叶子结点到根结点的路径。题目分析采用先序遍历的递归方法，当找到叶子结点*b时，由于*b叶子结点尚未添加到path中，因此在输出路径时还需输出b->data值。对应的递归算法如下：void AllPath(BTNo

28、de *b,ElemType path,int pathlen) int i; if (b!=NULL) if (b->lchild=NULL && b->rchild=NULL) /*b为叶子结点 cout << " " << b->data << "到根结点路径:" << b->data; for (i=pathlen-1;i>=0;i-) cout << endl; else pathpathlen=b->data; /将当前结点放入路径

29、中 pathlen+; /路径长度增1 AllPath(b->lchild,path,pathlen); /递归扫描左子树 AllPath(b->rchild,path,pathlen); /递归扫描右子树 pathlen-; /恢复环境 已知二叉树的先序序列:  CBHEGAF,   中序序列: HBGEACF, 试构造该二叉树 【北京理工大学 2001 八、2 （4分）】已知一棵二叉树的先序遍历序列为：AEFBGCDHIKJ，中序遍历序列为：EFAGBCHKIJD。试写

30、出此二叉树的后序遍历序列，并用图画出它的后序线索二叉树。【同济大学 2000 一、 (10分)】 73一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少？ 【西安电子科技大学 2000计应用 一、2 （5分）】 1 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。【东北大学 2000 三、2 （10分）2010年C语言程序设计试卷 1. 给出年、月、日，计算该日是该年的第几天。（15分） 

31、2. 有几个学生，每个学生考m门课，要求编一函数，能检查n个学生有无不及格的课程，如有某个学生有一门或一门以上课程不及格，就输出该学生的学号（学号从0开始）和其全部课程成绩。（15分） 3. 用二分法求方程2x3-4x2+3x-6=0在（-10,10）之间的根。（20分） 4. 请写出判断“点是否在简单多边形内部”的算法。（20分） 5. 从平均时间、最坏情况、辅助存储和稳定性的角度，对各种内部排序方法进行比较。（建议用表格方式进行比较）（20分） 6. 定义一个双向循环链表，并写出其定位、插入和删除算法。（20分） 7. 编写一个程序以模拟银行窗口接待客户的排队业务活动（每个窗口在某个时刻只能接待一个客户；窗口空闲则可上前办理业务；窗口均被占，则新客户便会排