第六章-树和二叉树-作业.doc

《第六章-树和二叉树-作业.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、二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。