《第六章-树和二叉树-作业》由会员分享，可在线阅读，更多相关《第六章-树和二叉树-作业（2页珍藏版）》请在金锄头文库上搜索。
1、第六章 树和二叉树一、应用题1已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少？2高度为10的二叉树，其结点最多可能为多少？3任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有（m-1）个度为2，其余度为1。4. 已知A1.N是一棵顺序存储的完全二叉树，如何求出Ai和Aj的最近的共同祖先？5已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？6一棵共有n个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。7设T是具有n个内结点的扩充二叉树，I是它的内路径长度，E是它的外路径长度。试利用归纳法证明E=I+2n, n=0
2、.8试证明:同一棵二叉树的所有叶子结点，在前序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如前序abc，后序bca，对称序bac。9. 由二叉树的中序序列及前序序列能唯一的建立二叉树，试问中序序列及后序序列是否也能唯一的建立二叉树，不能则说明理由，若能对中序序列DBEAFGC和后序序列DEBGFCA构造二叉树。 10. 由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。二、算法设计题1. 给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。2编程求以孩子兄弟表示法存储的森林的叶子结点数。3要求二叉树按二叉链表形式存储，（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。4假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。（注:已知树中结点数）5二叉树采用二叉链表存储：（1）编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度）。（2）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。
