欢迎来到天天文库
浏览记录
ID:59464646
大小:16.50 KB
页数:5页
时间:2020-11-02
《第六章-树和二叉树-作业.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第六章树和二叉树一、应用题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是它的
2、外路径长度。试利用归纳法证明E=I+2n,n>=0.8.试证明:同一棵二叉树的所有叶子结点,在前序序列、中序序列以及后序序列中都按相同的相对位置出现(即先后顺序相同),例如前序abc,后序bca,对称序bac。9.由二叉树的中序序列及前序序列能唯一的建立二叉树,试问中序序列及后序序列是否也能唯一的建立二叉树,不能则说明理由,若能对中序序列DBEAFGC和后序序列DEBGFCA构造二叉树。10.由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH,中序序列为:DGBEAFHC。试画出该二叉树。二、算法设计题1.给出算法将二叉树
3、表示的表达式二叉树按中缀表达式输出,并加上相应的括号。2.编程求以孩子—兄弟表示法存储的森林的叶子结点数。3.要求二叉树按二叉链表形式存储,(1)写一个建立二叉树的算法。(2)写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为:深度为K,具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。4.假设以双亲表示法作树的存储结构,写出双亲表示的类型说明,并编写求给定的树的深度的算法。(注:已知树中结点数)5.二叉树采用二叉链表存储:(1)编写计算整个二叉树高度的算法(二叉树的高度也叫二叉树的深度)。(2)编写计算
4、二叉树最大宽度的算法(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。
此文档下载收益归作者所有