作业5树和二叉树.doc

《作业5树和二叉树.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5树和二叉树班级姓名学号成绩批改时间选择填空题1、若一棵完全二叉树中某结点无左孩子，则该结点一定是。A.度为1的结点B．度为2的结点C．分支结点D．叶子结点2、遍历一棵具有n个结点的二叉树，在前序序列、中序序列和后序序列中所有叶子结点的相对次序。A.都不相同B．完全相同C．前序和中序相同D．中序与后序相同3、将一棵树转换成二叉树，树的前根序列与其对应的二叉树的相等。树的后根序列与其对应的二叉树的相同。（A）前序序列（B）中序序列（C）后序序列（D）层次序列4、对于树中任一结点x，在前根序列中序号为pre(x)，在后根序列中序号为post(x)，若树中结点x是

2、结点y的祖先，下列条件是正确的。A.pre(x)post(y)C.pre(x)>pre(y)且post(x)pre(y)且post(x)>post(y)5、已知一棵完全二叉树的第6层上有6个结点(根结点的层数为1)，则总的结点个数至少是，其中叶子结点个数是。6、若树T中度为1、2、3、4的结点个数分别为4、3、2、2，则T中叶子结点的个数是。简答题1、假设*代表空结点，每一个非*字符代表一个二叉树的结点值，请画出使用字符串“ab*c

3、**d*ef**g**”先序创建的二叉树，若该二叉树采用顺序存储结构，每个结点占用一个字节空间，则至少需要多少个字节的存储空间。2、已知二叉树的前序、中序和后序遍历序列如下，其中有一些看不清的字母用*表示，请先填写*处的字母，再构造一棵符合条件的二叉树。(1)前序遍历序列是：*BC***G*(2)中序遍历序列是：CB*EAGH*(3)后序遍历序列是：*EDB**FA(4)画出该二叉树的后序线索二叉树3、给出下图中树的双亲孩子表示法。4、在二叉链表的二叉树结构中实现判别两棵二叉树是否相等的算法。方法定义：boolisEqual（BitreeT1,BitreeT

4、2）