单元7练习参考答案

单元练习7一．判断题（下列各题，对的的请在前面的括号内打√；错误的打╳）（√）（1）树构造中每个结点最多只有一种直接前驱。（ㄨ）（2）完全二叉树一定是满二查树。（ㄨ）（3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。（√）（4）一棵二叉树中序遍历序列的最终一种结点，必然是该二叉树前序遍历的最终一种结点。（√）（5）二叉树的前序遍历中，任意一种结点均处在其子女结点的前面。（√）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。（√）（7）在完全二叉树中，若一种结点没有左孩子，则它必然是叶子结点。二．填空题在树中，一种结点所拥有的子树数称为该结点的度。度为零的结点称为叶（或叶子，或终端）结点。树中结点的最大层次称为树的深度（或高度）。对于二叉树来说，第i层上至多有2i-1个结点。深度为h的二叉树至多有2h-1个结点。由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。有20个结点的完全二叉树，编号为10的结点的父结点的编号是5。由二叉树的后序和中序遍历序列，可以唯一确定一棵二叉树。某二叉树的中序遍历序列为:DEBAC，后序遍历序列为：EBCAD。则前序遍历序列为：DABEC。设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则二叉树中叶结点是：E、F、H。已知完全二叉树的第8层有8个结点，则其叶结点数是68。采用二叉链表存储的n个结点的二叉树，一共有2n个指针域。采用二叉链表存储的n个结点的二叉树，共有空指针n+1个。前序为A，B，C且后序为C，B，A的二叉树共有4种。AACBABCABCACB（18）将一棵完全二叉树按层次编号，对于任意一种编号为i的结点，其左孩子结点的编号为：2*i。（19）给定如下图所示的二叉树，其前序遍历序列为：ABEFHCG。AABFGHDCE（20）给定如下图所示的二叉树，其层次遍历序列为：ABCEFGH。AABFGHDCE三．选择题（1）树最适合用来表达（D）。A．有序数据元素B．无序数据元素C．元素之间无联络的数据D．元素之间有分支的层次关系（2）前序为A，B，C的二叉树共有（D）种。A．2 B．3 C．4 D（3）根据二叉树的定义，具有3个结点的二叉树有（C）种树型。A．3 B．4 C．5 D．6（4）在一棵具有五层的满二叉树中，结点的总数为（B）A．16B．31C．32D．33（5）具有64个结点的完全二叉树的深度为（C）A．5 B．6 C．7 D．8（6）任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（A）。A．不发生变化B．发生变化C．不能确定D．以上都不对（7）A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是（C）。A．A在B右方B．A是B祖先C．A在B左方D．A是B子孙（8）下列4棵树中，（B）不是完全二叉树。A．B．C．D．ABECABECDABCDABEFCDABEGFDCD（9）如右图所示的二叉树，后序遍历的序列是（D）ABADECFGHIA．A、B、C、D、ABADECFGHIB．A、B、D、H、I、E、C、F、GC．H、D、I、B、E、A、F、C、GD．H、I、D、E、B、F、G、C、A（10）对于下边的二叉树，其中序序列为（A）A．DBEHAFCGB．DBHEAFCGC．ABDEHCFGD．ABCDEFGH（11）某二叉树的后序遍历序列为：DABEC，中序遍历序列为:DEBAC，则前序遍历序列为（D）。A．ACBED B．DECAB C．DEABCD．CEDBA（12）具有n（n>1）个结点的完全二叉树中，结点i（2i>n）的左孩子结点是（D）。A．2i B．2i+1 C．2i-1 D．不存在（若2i<=n，则答案为A）（13）把一棵树转换为二叉树后，这棵二叉树的形态是（A）。A．唯一的B．有多种C．有多种，但根结点都没有左孩子D．有多种，但根结点都没有右孩子（14）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子编号为（B）。A．46 B．47 C．90 D（15）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的右孩子编号为（B）。A．98 B．99 C．50 D．100（17）下列陈说对的的是（D）。A．二叉树是度为2的有序树 B．二叉树中结点只有一种孩子时无左右之分C．二叉树中必有度为2的结点 D．二叉树中最多只有两棵子树，且有左右子树之分（20）二叉树的叶结点个数比度为2的结点的个数（C）。A．无关 B．相等 C．多一种 D．少一种五.应用题1．已知一棵二叉树的后序遍历和中序遍历的序列分别为：A，C，D，B，G，I，H，F，E和A，B，C，D，E，F，G，H，I。请画出该二叉树，并写出它的前序遍历的序列。BCHDDBCHDDFGEIA其前序遍历的序列为：EBADCFHGI2．已知一棵二叉树的前序遍历和中序遍历的序列分别为：A，B，D，G，H，C，E，F，I和G，D，H，B，A，E，C，I，F。请画出此二叉树，并写出它的后序遍历的序列。。GHAGHABDCEFI其后序遍历的序列为：GHDBEIFCA3．已知一棵树的层次遍历的序列为：ABCDEFGHIJ，中序遍历的序列为：DBGEHJACIF，请画出该二叉树，并写出它的后序遍历的序列。ABABCHDDFGEIJ后序遍历的序列：DGJHEBIFCA7．某二叉树的结点数据采用次序存储，其构造如下：1234567891011121314151617181920EAFDHCGIB（1）画出该二叉树（3分）（2）写出按层次遍历的结点序列（2分）解：ADADHFGECBI（2）层次遍历的结点序列：EAFDHCGIB8．某二叉树的存储如下：12345678910lchild00237580101dataJHFDBACEGIrchild0009400000 其中根结点的指针为6，lchild、rchild分别为结点的左、右孩子的指针域，data为数据域。（1）画出该二叉树（3分）（2）写出该树的前序遍历的结点序列（2分）解：BDBDJHGACFEIABCEDFHGIJ六．算法设计题以二叉链表为存储构造，设二叉树BT构造为：typedefstructBT{ chardata; BT*lchild; BT*rchild;}BT;1．求二叉树中的度数为2的结点。2．求二叉树中值为最大的元素。3．将二叉树各结点存储到一维数组中。4．前序输出二叉树中各结点及其结点所在的层号。5．求二叉树的宽度6．互换二叉树各结点的左右子树。7．写出在二叉树中查找值为x的结点在树中层数的算法。解：求二叉树中的度数为2的结点。voidcount(BTt){if(t){if(t->lchild&&t->rchild)k++;count(t->lchild);count(t->rchild);}}求二叉树中值为最大的元素。intmaxnode(BTt,intmax){if(t){if(t->data>max)max=t->data;max=maxnode(t->lchild,max);max=maxnode(t->rchild,max);}}3．将二叉树各结点存储到一维数组中。voidcreate(BTt,inta[],inti){if(t){a[i]=t->data;create(t->lchild,a,2*i);create(t->rchild,a,2*i+1);}}4．前序输出二叉树中各结点及其结点所在的层号。voidpreorderlevel(BTt,inth)//t的层数为h{if(t!=NULL){printf(“%d,%d”,t->data,h);preorderlevel(t->lchild,h+1);preorderlevel(t->rchild,h+1);}}求二叉树的宽度思想：按层遍历二叉树，采用一种队列q，让根结点入队列，最终出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。intWidth(BT*T){intfront=-1,rear=-1;//队列初始化intflag=0,count=0,p;//p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值if(T!=NULL){rear++;q[rear]=T;flag=1;p=rear;}while(front<p){front++;T=q[front];if(T->lchild!=NULL){rear++;q[rear]=T->lchild;count++;}if(T->rchild!=NULL){rear++;q[rear]=T->rchild;count++;}if(front==p) //目前层已遍历完毕{if(flag<count)flag=count;count=0;p=rear; //p指向下一层最右边的结点}} //endwhilereturn(flag);}6．解：借助栈来进行对换。Swap(BinTree*T){BinTree*stack[100],*temp;inttop=-1;root=T;if(T!=NULL){top++;stack[top]=T;while(top>-1){T=stack[top];top--;if(T->child!=NULL||T->rchild!=NULL){//互换结点的左右指针temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;}if(T->lchild!=NULL){top++;stack[top]=T->lchild;}if(T->rchild!=NULL){top++;stack[top]=T->rchild;}}}}main(){intI,j,k,l;printf(“\n”);root=CreateBinTree();Inorder(root);i=CountNode(root);j=CountLeafs(root);k=Depth(