第6章习题答案.docx
- 文档编号:7474646
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:12
- 大小:66.53KB
第6章习题答案.docx
《第6章习题答案.docx》由会员分享,可在线阅读,更多相关《第6章习题答案.docx(12页珍藏版)》请在冰点文库上搜索。
第6章习题答案
习题6
1.树与二叉树之间有什么区别与联系?
解:
树与二叉树逻辑上都是树形结构,区别有三点:
(1)二叉树的度至多为2,树无此限制。
(2)二叉树有左右子树之分,树无此限制。
(3)二叉树允许为空,树一般不允许为空。
二叉树不是树的特例。
2.高度为h的完全二叉树至少有多少个结点?
至多有多少个结点?
解:
至少有2h1个结点,至多有2h1个结点。
h和结点数n之间的关系是hlog2n+1。
3.已知A[1..n]是一棵顺序存储的完全二叉树,如何求出A[i]和A[j]的最近的共同祖先?
解:
根据顺序存储的完全二叉树的性质,编号为i的结点的双亲的编号为i/2,故A[i]和A[j]的最近的共同祖先可如下求出:
while(i/2!
j/2)
if(i>j)i=i/2;
elsej=j/2;
退出while后,若i/2=0,则最近共同祖先为根结点,否则共同祖先为i/2。
4.已知A[1..n]是一棵顺序存储的完全二叉树,求序号最小的叶子结点的下标。
解:
根据完全二叉树的性质,最后一个结点(编号为n)的双亲结点的编号是n/2,这是最后一个分
支结点,在它之后是第一个叶子结点,故序号最小的叶子结点的下标是n/2+1。
5.一棵深度为L的满k叉树有以下性质:
第L层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树,如果按层次顺序从1开始对全部结点进行编号,求:
(1)各层的结点数是多少?
(2)编号为n的结点的双亲结点(若存在)的编号是多少?
(3)编号为n的结点的第i个孩子结点(若存在)的编号是多少?
(4)编号为n的结点有左右兄弟结点的条件是什么?
如果有,其右兄弟结点的编号是多少?
解:
(1)kh-1(h为层数)。
(2)因为该树上每层上均有kh-1个结点,从根开始编号为1,则结点i的从右向左数第2个孩子的结点编号为ki。
设n为结点i的子女,则关系式(i-1)*k+2ni*k+1成立,因i是整数,故结点n的双亲i的编号为n/k+1。
(3)结点(n>1)的前一结点编号为n-1(其最右边子女编号是(n-1)*k+1),故结点n的第i个孩子的编号是(n-1)*k+1+i。
(4)根据以上分析,结点n有右兄弟的条件是,它不仅双亲的从右边的第一个子女,即(n-1)%k!
=0,
6.试证明,在具有n(n≥1)个结点的m叉树中,有n(m-1)+1个指针域是空的。
解:
具有n个结点的m叉树共用n*m个指针。
除根结点外,其余n-1个结点均有指针所指,故空指针数为n*m-(n-1)=n*(m-1)+1。
7.试找出满足下列条件的二叉树:
(1)先序序列与后序序列相同;
(2)中序序列与后序序列相同;
(3)先序序列与中序序列相同;
(4)中序序列与层次遍历序列相同。
解:
(1)若先序序列与后序序列相同,则或为空树,或为只有根结点的二叉树。
(2)若中序序列与后序序列相同,则或为空树,或为任一结点至多只有左子树的二叉树。
(3)若先序序列与中序序列相同,则或为空树,或为任一结点至多只有右子树的二叉树。
(4)若中序序列与层次遍历序列相同,则或为空树,或为任一结点至多只有右子树的二叉树。
8.设有一棵二叉树的层次遍历序列为ABCDEFGHI,J中序遍历序列为DBGEHJACI。
F请画出这棵二叉树。
解:
按层次遍历,第一个结点(树不空)为根,该结点在中序序列中把序列分成左右两部分——左子树和右子树。
若左子树不空,层次序列中第二个结点为左子树的根;若左子树为空,则层次序列中第二个结点为右子树的根。
对右子树分析类似。
层次序列的特点是:
从左到右每个结点或是当前情况下子树的根或是叶子。
9.用一维数组存放一棵完全二叉树:
ABCDEFGHIJK。
L请写出后序遍历该二叉树的访问结点序列。
解:
HIDJKEBLFGC。
A
10.已知一棵二叉树的中序遍历序列为DGBAECHI,F后序遍历序列为:
GDBEIHFC。
A
(1)试画出该二叉树;
(2)试画出该二叉树的中序线索树;
(3)试画出该二叉树对应的森林。
解:
(1)
2)略
3)
A
码最短。
解:
字符A、B、C、D出现的次数为9、1、5、3。
其哈夫曼编码如下:
A:
1,B:
000,C:
01,D:
001。
其哈夫曼树为:
12.
T中,写出计算该算术表达式
假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树值的算法。
解:
typedefstructNode{
ElemTypedata;
floatval;
charoptr;//只取+、-、*、/
structNode*lchild,*rchild
}BiNode,*BiTree;
floatPostEval(BiTreet){//以后序遍历算法求以二叉树表示的算术表达式的值floatlv,rv;
if(t!
=NULL){
lv=PostEval(t->lchild);//rv=PostEval(t->rchild);//switch(t->optr){
case'+':
value=lv+rv;break;
case'-':
value=lv-rv;break;
case'*':
value=lv*rv;break;
case'/':
value=lv/rv;break;
}
}
returnvalue;
}
13.假设二叉链表为二叉树的存储结构,编写判断给定的二叉树是否相似的算法。
所谓二叉树t1和t2相似指的是:
t1和t2都是空树;或者t1和t2的根结点是相似的,以及t1的左子树和t2的左子树是相似的且t1的右子树和t2的右子树是相似的。
解:
intLike(BiTreet1,BiTreet2){
intlike1,like2;
if(t1==NULL&&t2==NULL)return1;
elseif(t1==NULL||t2==NULL)return0;
else{
like1=Like(t1->lchild,t2->lchild);like2=Like(t1->rchild,t2->rchild);
return(like1&like2);
}
}
14.假设二叉链表为二叉树的存储结构,编写递归算法,将二叉树中所有结点的左、右子树相互交换。
解:
voidExchange(BiTree&t){
if(t){
BiTrees;
s=t->lchild;t->lchild=t->rchild;t->rchild=s;
Exchange(t->lchild);
Exchange(t->rchild);
}
}
15.编写求双亲表示法表示的树的深度的算法。
解:
intDepth(PTreet){
intmaxdepth=0,i,temp,f;
for(i=0;i temp=0;f=i; while(f>-1){temp++;f=t.nodes[f].parent;}if(temp>maxdepth)maxdepth=temp; } returnmaxdepth; } 16.假设二叉链表为二叉树的存储结构,编写按层次遍历方式计算二叉树结点个数的算法。 解: intLevel(BiTreet){ intnum=0; LinkQueueQ; BiTreep; if(t){ InitQueue(Q);EnQueue(Q,t); while(! QueueEmpty(Q)){ DeQueue(Q,p);num++; if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild); }//while }//if returnnum; } 17.编写算法,利用叶子结点中的空指针域将所有叶子结点链接为一个带有头结点的双向链表,算法返回头结点的指针。 解: BiTreehead,pre;//全局变量链表头指针head,pre voidCreateLeafList(BiTreet){ if(t){ CreateLeafList(t->lchild);//中序遍历左子树if(t->lchild==NULL&&t->rchild==NULL)//叶子结点 if(head==NULL){//第一个叶子结点 head=newBiTNode;//生成头结点 head->lchild=NULL;head->rchild=t;//头结点的左链为空,右链指向第一个叶子结点t->lchild=head;pre=t;//第一个叶子结点左链指向头结点,pre指向当前叶子结点 } else{pre->rchild=t;t->lchild=pre;pre=t;}; CreateLeafList(t->rchild); pre->rchild=NULL; } } 18.假设二叉链表为二叉树的存储结构,编写算法,按照括号表示法输出二叉树的所有结点。 解: 其过程是: 对于非空二叉树t,先输出其元素值,当存在左孩子结点或右孩子结点时,输出一个”符号,然后递归处理左子树,输出一个“,”符号,递归处理右子树,最后输出一个“)”符号。 voidDispBiTree(BiTreet){ if(t){ printf("%c",t->data); if(t->lchild! =NULL||t->rchild! =NULL){ printf("("); DispBiTree(t->lchild); if(t->rchild! =NULL)printf(","); DispBiTree(t->rchild); printf(")"); } } } 19.假设二叉链表为二叉树的存储结构,编写算法,输出二叉树的所有叶子结点。 解: voidDispLeaf(BiTreet){ if(t){ if(t->lchild==NULL&&t->rchild==NULL)printf("%c",t->data); DispLeaf(t->lchild); DispLeaf(t->rchild); } } 20.假设二叉链表为二叉树的存储结构,编写算法,输出值为x的结点的所有祖先。 解: intAncestor(BiTreet,ElemTypex){ if(t==NULL)return0; if(t->data==x)return1; if(Ancestor(t->lchild,x)||Ancestor(t->rchild,x)){ printf("%c",t->data); return1; } } 21.假设二叉链表为二叉树的存储结构,编写算法,输出所有叶子结点到根结点的路径。 解: 利用后序非递归遍历的特点,将其中访问结点改为判断结点是否为叶子结点,若是,输出栈中所有结点值 voidAllPathAncestor(BiTreet){ BiTNode*St[100]; BiTNode*p; intflag,i,top=-1;//栈指针初始化 if(t){ do{ while(t){//t的所有左结点进栈 top++; St[top]=t; t=t->lchild; } p=NULL;//p指向栈顶结点的前一个已访问的结点 flag=1;//设置t的访问标记为已访问过while(top! =-1&&flag){ t=St[top];//出栈 if(t->rchild==p){ if(t->lchild==NULL&&t->rchild==NULL){//若为叶子结点 for(i=top;i>0;i--)printf("%c->",St[i]->data);//输出栈中所有结点 printf("%c\n",St[0]->data); } top--; p=t;//p指向刚访问过的结点 } else{ t=t->rchild;//t指向右孩子结点flag=0;//设置未访问标记 } } }while(top! =-1); printf("\n"); } } 22.编写算法,将二叉树的顺序存储结构转化为二叉链表存储结构。 解: typedefcharElemType; typedefstruct{//结点结构 ElemType*data;//数据元素 intn;//左右孩子指针 }SqBTree; BiTreeTrans(SqBTreea,inti){//数据元素放在数组a的从下标为1开始的单元中 BiTreet; if(i>a.n)returnNULL;//当i大于a的结点个数if(a.data[i]=='#')returnNULL;//当i对于的结点为空t=newBiTNode; t->data=a.data[i];t->lchild=Trans(a,2*i); t->rchild=Trans(a,2*i+1); returnt; } 23.写出在中序线索二叉树中找指定结点在后序下的前驱结点的算法。 解: 在后序序列中,若结点p有右子女,则右子女是其前驱,若无右子女而有左子女,则左子女是其前驱。 若p左右子女均无,设其中序左线索指向其祖先结点f(p是f右子树中按中序遍历的第一个结点)若f有左子女,则其右子女是p在后序下的前驱,若f无左子女,则顺其前驱找双亲的双亲,一直继续到双亲有左子女(这时左子女是p的前驱)。 还有一种情况,若p是中序遍历的第一个结点,p在中序和后序下均无前驱。 BiThrTreeInPostPre(BiThrTreet,BiThrTreep){ BiThrNode*q; if(p->RTag==0)q=p->rchild;//若p有右子女,则右子女是其后序前驱 elseif(p->LTag==0)q=p->lchild;//若p无右子女而有左子女,则左子女是其后序前驱 elseif(p->lchild==NULL)q=NULL;//p是中序序列第一个结点,无后序前驱 else{//顺左线索向上找p的祖先,若存在,再找祖先的左子女while(p->LTag==1&&p->lchild! =NULL)p=p->lchild; if(p->LTag==0)q=p->lchild;//p结点的祖先的左子女是其后序前驱 elseq=NULL;//仅右单支树(p是叶子),已上到根结点,p结点无后序前驱 } returnq; } 24.写出按后序序列遍历中序线索二叉树的算法。 解: BiThrTreeLeftMost(BiThrTreet){//求结点t的最左子孙的左线索 BiThrTreep=t; while(p->LTag==0)p=p->lchild; if(p->lchild! =NULL&&p->lchild! =t)return(p->lchild); elsereturnNULL; } BiThrTreeRightMost(BiThrTreet){//求结点t的最右子孙的右线索 BiThrTreep=t; while(p->RTag==0)p=p->rchild; if(p->rchild! =NULL&&p->rchild! =t)return(p->rchild); elsereturnNULL; } intISRightChild(BiThrTreet,BiThrTree&father){//若t是father的右孩子,返回1,否则返回0 father=LeftMost(t); if(father&&father->rchild==t)return1; elsereturn0; } voidPostOrderInThr(BiThrTreet){//后序遍历中序线索二叉树t BiThrTreefather,p=t->lchild; intflag; while(p! =t){ while(p->LTag==0)p=p->lchild;//沿左分子向下if(p->RTag==0)flag=0;//左孩子为线索,右孩子为链,相当从左返回,p为叶子,相当从右返回elseflag=1; while(flag==1){ printf("%c",p->data);//访问结点if(ISRightChild(p,father)){p=father;flag=1;}//修改p指向双亲else{//p是左孩子,用最右子孙的右线索找双亲 p=RightMost(p);if(p&&p->RTag==1)flag=1;elseflag=0; } }//while(flag==1) if(flag==0&&p! =t)p=p->rchild;//转向当前结点的右分支 } } 25.已知中序线索二叉树T的右子树不空。 设计算法,将s所指结点作为T的右子树的一个叶子结点插入进去,并使之成为T的右子树的(中序序列)第一个结点。 解: 若使新插入的结点S成T右子树中序序列的第一个结点,则应在T的右子树中最左边的结点(设 为p)处插入,使S成为结点p的左孩子。 则S的前驱是T,后继是p。 voidThrTreeInsert(BiThrTreeT,BiThrTreeS){ BiThrTreep=T->rchild;//用p指向T的右子树中最左边的结点 while(p->LTag==0)p=p->lchild; S->LTag=1;S->RTag=1;//S是叶子结点,其左右标记均为1 S->lchild=p->lchild;S->rchild=p;//S的前驱是根结点T,后继是结点pp->lchild=S;p->LTag=0;//将p的左指针指向S,并修改左标记为0 } 26.写出在中序线索二叉树中找指定结点在中序下的前驱结点的算法。 解: BiThrTreeInorderPre(BiThrTreep){ BiThrTreeq; if(p->LTag==1)//结点的左子树为空,结点左指针域为左线索,指向其前驱 return(p->lchild); else{ p结点的中序前驱 q=p->lchild;//p结点左子树最右边结点时while(q->RTag)q=q->rchild; returnq; }//if }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 习题 答案