第6章习题答案

1、习题61.树与二叉树之间有什么区别与联系？解：树与二叉树逻辑上都是树形结构，区别有三点：（1）二叉树的度至多为2，树无此限制。（2）二叉树有左右子树之分，树无此限制。（3）二叉树允许为空，树一般不允许为空。二叉树不是树的特例。2.高度为的完全二叉树至少有多少个结点？至多有多少个结点？解：至少有个结点，至多有个结点。和结点数之间的关系是ëû+1。3.已知A1.n是一棵顺序存储的完全二叉树，如何求出Ai和Aj的最近的共同祖先？解：根据顺序存储的完全二叉树的性质，编号为i的结点的双亲的编号为ëi/2û，故Ai和Aj的最近的共同祖先可如下求出：while(i/2

2、!j/2)if(i>j)i=i/2;else j=j/2;退出while后，若i/2=0，则最近共同祖先为根结点，否则共同祖先为i/2。4.已知A1.n是一棵顺序存储的完全二叉树，求序号最小的叶子结点的下标。解：根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是ën/2û，这是最后一个分支结点，在它之后是第一个叶子结点，故序号最小的叶子结点的下标是ën/2û+1。5.一棵深度为L的满k叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：(1)各层的结点数是多少？

3、(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)

4、*k+1+i。(4)根据以上分析，结点n有右兄弟的条件是，它不仅双亲的从右边的第一个子女，即(n-1)%k!=0，其右兄弟编号是n+1。6.试证明，在具有n(n1)个结点的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)若中序序列与后

5、序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。(3)若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。(4)若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。8.设有一棵二叉树的层次遍历序列为ABCDEFGHIJ，中序遍历序列为DBGEHJACIF。请画出这棵二叉树。解：按层次遍历，第一个结点（树不空）为根，该结点在中序序列中把序列分成左右两部分左子树和右子树。若左子树不空，层次序列中第二个结点为左子树的根；若左子树为空，则层次序列中第二个结点为右子树的根。对右子树分析类似。层次序列的特点是：从左到右每个结点或是当前情况下子树的

6、根或是叶子。9.用一维数组存放一棵完全二叉树：ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。解：HIDJKEBLFGCA。10.已知一棵二叉树的中序遍历序列为DGBAECHIF，后序遍历序列为：GDBEIHFCA。(1)试画出该二叉树；(2)试画出该二叉树的中序线索树；(3)试画出该二叉树对应的森林。解：（1）（2）略（3）11.设有正文AADBAACACCDACACAAD，字符集为A、B、C、D，设计一套二进制编码，使得上述正文的编码最短。解：字符A、B、C、D出现的次数为9、1、5、3。其哈夫曼编码如下：A：1，B：000，C：01，D：001。其哈夫曼树为：12.假设一

7、个仅包含二元运算符的算术表达式以链表形式存储在二叉树T中，写出计算该算术表达式值的算法。解：typedef struct Node ElemType data; float val; char optr;/只取+、-、*、/ struct Node *lchild,*rchild BiNode,*BiTree;float PostEval(BiTree t)/以后序遍历算法求以二叉树表示的算术表达式的值 float lv,rv; if(t!=NULL) lv=PostEval(t->lchild);/ rv=PostEval(t->rchild);/ switch(t->op

8、tr) case '+': value=lv+rv;break; case '-':value=lv-rv;break; case '*':value=lv*rv;break; case '/':value=lv/rv;break; return value;13.假设二叉链表为二叉树的存储结构，编写判断给定的二叉树是否相似的算法。所谓二叉树t1和t2相似指的是：t1和t2都是空树；或者t1和t2的根结点是相似的，以及t1的左子树和t2的左子树是相似的且t1的右子树和t2的右子树是相似的。解：int Like(BiTree t1,

9、 BiTree t2) int like1,like2; if(t1=NULL&&t2=NULL)return 1; else if(t1=NULL|t2=NULL)return 0; elselike1=Like(t1->lchild,t2->lchild);like2=Like(t1->rchild,t2->rchild);return (like1 & like2); 14.假设二叉链表为二叉树的存储结构，编写递归算法，将二叉树中所有结点的左、右子树相互交换。解：void Exchange(BiTree &t) if(t) BiTr

10、ee s; s=t->lchild;t->lchild=t->rchild;t->rchild=s; Exchange(t->lchild);Exchange(t->rchild);15.编写求双亲表示法表示的树的深度的算法。解：int Depth(PTree t) int maxdepth=0,i,temp,f; for(i=0;i<t.n;i+)temp=0;f=i;while(f>-1)temp+;f=t.nodesf.parent;if(temp>maxdepth)maxdepth=temp; return maxdepth;16.

11、假设二叉链表为二叉树的存储结构，编写按层次遍历方式计算二叉树结点个数的算法。解：int Level(BiTree t) int num=0; LinkQueue Q; BiTree p; 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 return num;17.编写算法，利用叶子结点中的空指针域将所有叶子结点链接为一个带有头

12、结点的双向链表，算法返回头结点的指针。解：BiTree head,pre;/全局变量链表头指针head，prevoid CreateLeafList(BiTree t) if(t)CreateLeafList(t->lchild);/中序遍历左子树if(t->lchild=NULL&&t->rchild=NULL)/叶子结点if(head=NULL)/第一个叶子结点head=new BiTNode; /生成头结点head->lchild=NULL; head->rchild=t;/头结点的左链为空，右链指向第一个叶子结点t->lchild=h

13、ead;pre=t;/第一个叶子结点左链指向头结点，pre指向当前叶子结点elsepre->rchild=t;t->lchild=pre;pre=t; CreateLeafList(t->rchild);pre->rchild=NULL; 18.假设二叉链表为二叉树的存储结构，编写算法，按照括号表示法输出二叉树的所有结点。解：其过程是：对于非空二叉树t，先输出其元素值，当存在左孩子结点或右孩子结点时，输出一个“（”符号，然后递归处理左子树，输出一个“，”符号，递归处理右子树，最后输出一个“）”符号。void DispBiTree(BiTree t) if(t)print

14、f("%c",t->data);if(t->lchild!=NULL|t->rchild!=NULL)printf("(");DispBiTree(t->lchild);if(t->rchild!=NULL) printf(",");DispBiTree(t->rchild);printf(")"); 19.假设二叉链表为二叉树的存储结构，编写算法，输出二叉树的所有叶子结点。解：void DispLeaf(BiTree t) if(t) if(t->lchild=NULL&

15、amp;&t->rchild=NULL)printf("%c ",t->data); DispLeaf(t->lchild); DispLeaf(t->rchild); 20.假设二叉链表为二叉树的存储结构，编写算法，输出值为x的结点的所有祖先。解：int Ancestor(BiTree t,ElemType x) if(t=NULL)return 0; if(t->data=x)return 1; if(Ancestor(t->lchild,x)|Ancestor(t->rchild,x)printf("%c &

16、quot;,t->data);return 1; 21.假设二叉链表为二叉树的存储结构，编写算法，输出所有叶子结点到根结点的路径。解：利用后序非递归遍历的特点，将其中访问结点改为判断结点是否为叶子结点，若是，输出栈中所有结点值void AllPathAncestor(BiTree t) BiTNode *St100; BiTNode *p; int flag,i,top=-1;/栈指针初始化 if(t)dowhile(t) /t的所有左结点进栈top+;Sttop=t;t=t->lchild;p=NULL; /p指向栈顶结点的前一个已访问的结点flag=1; /设置t的访问标记为已

17、访问过while(top!=-1&&flag)t=Sttop; /出栈if(t->rchild=p)if(t->lchild=NULL&&t->rchild=NULL) /若为叶子结点for(i=top;i>0;i-) printf("%c->",Sti->data); /输出栈中所有结点printf("%cn",St0->data);top-;p=t;/p指向刚访问过的结点elset=t->rchild; /t指向右孩子结点flag=0; /设置未访问标记while(top

18、!=-1);printf("n"); 22.编写算法，将二叉树的顺序存储结构转化为二叉链表存储结构。解：typedef char ElemType;typedef struct /结点结构 ElemType *data;/数据元素 int n;/左右孩子指针SqBTree;BiTree Trans(SqBTree a,int i)/数据元素放在数组a的从下标为1开始的单元中 BiTree t; if(i>a.n)return NULL;/当i大于a的结点个数 if(a.datai='#')return NULL;/当i对于的结点为空 t=new BiT

19、Node; t->data=a.datai; t->lchild=Trans(a,2*i); t->rchild=Trans(a,2*i+1); return t;23.写出在中序线索二叉树中找指定结点在后序下的前驱结点的算法。解：在后序序列中，若结点p有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若p左右子女均无，设其中序左线索指向其祖先结点f（p是f右子树中按中序遍历的第一个结点），若f有左子女，则其右子女是p在后序下的前驱，若f无左子女，则顺其前驱找双亲的双亲，一直继续到双亲有左子女（这时左子女是p的前驱）。还有一种情况，若p是中序遍历的第一个结点

20、，p在中序和后序下均无前驱。BiThrTree InPostPre(BiThrTree t,BiThrTree p)BiThrNode *q; if(p->RTag=0)q=p->rchild;/若p有右子女，则右子女是其后序前驱 else if(p->LTag=0)q=p->lchild; /若p无右子女而有左子女，则左子女是其后序前驱 else if(p->lchild=NULL)q=NULL;/p是中序序列第一个结点，无后序前驱 else /顺左线索向上找p的祖先，若存在，再找祖先的左子女while(p->LTag=1&&p->l

21、child!=NULL)p=p->lchild;if(p->LTag=0)q=p->lchild; /p结点的祖先的左子女是其后序前驱else q=NULL; /仅右单支树（p是叶子），已上到根结点，p结点无后序前驱 return q;24.写出按后序序列遍历中序线索二叉树的算法。解：BiThrTree LeftMost(BiThrTree t)/求结点t的最左子孙的左线索BiThrTree p=t; while(p->LTag=0)p=p->lchild; if(p->lchild!=NULL&&p->lchild!=t)return

22、(p->lchild); else return NULL;BiThrTree RightMost(BiThrTree t)/求结点t的最右子孙的右线索 BiThrTree p=t; while(p->RTag=0)p=p->rchild; if(p->rchild!=NULL&&p->rchild!=t)return(p->rchild); else return NULL;int ISRightChild(BiThrTree t,BiThrTree &father)/若t是father的右孩子，返回1，否则返回0 father=L

23、eftMost(t); if(father&&father->rchild=t)return 1; else return 0;void PostOrderInThr(BiThrTree t)/后序遍历中序线索二叉树t BiThrTree father,p=t->lchild; int flag; while(p!=t)while(p->LTag=0)p=p->lchild;/沿左分子向下if(p->RTag=0)flag=0;/左孩子为线索，右孩子为链，相当从左返回，p为叶子，相当从右返回else flag=1;while(flag=1)printf("%c",p->data); /访问结点if(ISRightChild(p,father)p=father;flag=1; /修改p指向双亲else/p是左孩子，用最右子孙的右线索找双