单元7练习参考答案.doc

单元练习7一判断题（下列各题，正确的请在前面的括号内打；错误的打 ）（）（1）树结构中每个结点最多只有一个直接前驱。（）（2）完全二叉树一定是满二查树。（）（3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。（）（4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。（）（5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。（）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。（）（7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。二填空题（1） 在树中，一个结点所拥有的子树数称为该结点的 度 。（2） 度为零的结点称为 叶（或叶子，或终端） 结点。（3） 树中结点的最大层次称为树的 深度（或高度） 。（4） 对于二叉树来说，第i层上至多有 2i-1 个结点。（5） 深度为h的二叉树至多有 2h-1 个结点。（6） 由一棵二叉树的前序序列和 中序 序列可唯一确定这棵二叉树。（7） 有20个结点的完全二叉树，编号为10的结点的父结点的编号是 5 。（8） 由二叉树的后序和 中序 遍历序列，可以唯一确定一棵二叉树。（9） 某二叉树的中序遍历序列为: DEBAC，后序遍历序列为：EBCAD。则前序遍历序列为：DABEC 。（10） 设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则二叉树中叶结点是： E、F、H 。（11） 已知完全二叉树的第8层有8个结点，则其叶结点数是 68 。（12） 采用二叉链表存储的n个结点的二叉树，一共有 2n 个指针域。（13） 采用二叉链表存储的n个结点的二叉树，共有空指针 n+1 个。（14） 前序为A，B，C且后序为C，B，A的二叉树共有 4 种。ACBABCABCACB（18）将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其左孩子结点的编号为： 2*i 。（19）给定如下图所示的二叉树，其前序遍历序列为： ABEFHCG 。ABFGHDCE（20）给定如下图所示的二叉树，其层次遍历序列为： ABCEFGH 。ABFGHDCE三选择题（1）树最适合用来表示（ D ）。 A有序数据元素 B无序数据元素 C元素之间无联系的数据 D元素之间有分支的层次关系（2）前序为A，B，C的二叉树共有（ D ）种。 A2 B3 C4 D5（3）根据二叉树的定义，具有3个结点的二叉树有（ C ）种树型。 A3 B4 C5 D6（4）在一棵具有五层的满二叉树中，结点的总数为（ B ） A16 B31 C32 D33（5）具有64个结点的完全二叉树的深度为（ C ） A5B6 C7 D8（6）任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（ A ）。 A不发生改变 B发生改变 C不能确定 D以上都不对（7）A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是（ C ）。 AA在B右方 BA是B祖先 CA在B左方 DA是B子孙（8）下列4棵树中，（ B ）不是完全二叉树。 A B C DABECDABCDABEFCDABEGFDCD（9）如右图所示的二叉树，后序遍历的序列是（ D ）ABADECFGHI A A、B、C、D、E、F、G 、H、I B A、B、D、H、I、E、C、F、G C H、D、I、B、E、A、F、C、G D H、I、D、E、B、F、G、C、A（10）对于下边的二叉树，其中序序列为 （ A ）ADBEHAFCG BDBHEAFCG CABDEHCFG DABCDEFGH （11）某二叉树的后序遍历序列为：DABEC，中序遍历序列为: DEBAC，则前序遍历序列为（ D ）。 A ACBEDBDECABCDEABC DCEDBA（12）具有n（n1）个结点的完全二叉树中，结点i（2in）的左孩子结点是（ D ）。A2iB2i+1C2i-1 D不存在（若2ilchild & t-rchild) k+; count(t-lchild); count(t-rchild);2. 求二叉树中值为最大的元素。int maxnode(BT t, int max) if (t) if (t-datamax) max=t-data;max=maxnode(t-lchild,max);max=maxnode(t-rchild,max);3将二叉树各结点存储到一维数组中。void create(BT t,int a ,int i) if (t) ai=t-data; create (t-lchild, a, 2*i); create (t-rchild, a, 2*i+1);4前序输出二叉树中各结点及其结点所在的层号。void preorderlevel (BT t,int h) / t的层数为h if (t!=NULL) printf (“%d,%d”,t-data, h); preorderlevel (t-lchild, h+1); preorderlevel (t-rchild, h+1);5. 求二叉树的宽度 思想：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。 int Width(BT *T) int front=-1,rear=-1; / 队列初始化 int flag=0,count=0,p; / p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值 if (T!=NULL) rear+; qrear=T; flag=1; p=rear; while (frontlchild!=NULL) rear+; qrear=T-lchild; count+; if (T-rchild!=NULL) rear+; qrear=T-rchild; count+; if (front=p) / 当前层已遍历完毕 if (flag-1) T=stacktop; top-; if (T-child!=NULL|T-rchild!=NULL) / 交换结点的左右指针 temp=T-lchild; T-lchild=T-rchild; T-rchild=temp; if (T-lchild!=NULL) top+; stacktop=T-lchild; if (T-rchild!=NULL) top+; stacktop=T-rchild; main() int I,j,k,l; printf(“n”); root=CreateBinTree(); Inorder (root);i=CountNode (root); j=CountLeafs (root);k=Depth (root); l=Width (root); printf(“nThe Node s Number:%d”,i); printf(“nThe Leafss Number:%d”,j); printf(“nThe Depth is:%d”,k); printf(“nThe width is:%d”,l); Swap(root); Printf(“nThe swapTree is:”);Inorder(root);7解：int h=-1,lh=1,count=0;charx=c; / 赋初值Level (BinTree T,int h,int lh) / 求X结点在树只的层树 if (T=Null) h=0; else if (T-data=x) h=lh; count=h; else h+; Level(T-lc