第6章习题答案

第6章 树与二叉树

习题6

1.树与二叉树之间有什么区别与联系？

解：树与二叉树逻辑上都是树形结构，区别有三点： （1）二叉树的度至多为2，树无此限制。 （2）二叉树有左右子树之分，树无此限制。 （3）二叉树允许为空，树一般不允许为空。 二叉树不是树的特例。

2.高度为h的完全二叉树至少有多少个结点？至多有多少个结点？ 解：至少有2h?1h个结点，至多有2?1个结点。h和结点数n之间的关系是h??log2n?+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; else j=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)k(h为层数)。

(2)因为该树上每层上均有k个结点，从根开始编号为1，则结点i的从右向左数第2个孩子的结点编号为ki。设n为结点i的子女，则关系式(i-1)*k+2?n?i*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，

1

h-1

h-1

第6章 树与二叉树

其右兄弟编号是n+1。

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.设有一棵二叉树的层次遍历序列为ABCDEFGHIJ，中序遍历序列为DBGEHJACIF。请画出这棵二叉树。 解：按层次遍历，第一个结点（树不空）为根，该结点在中序序列中把序列分成左右两部分——左子树和右子树。若左子树不空，层次序列中第二个结点为左子树的根；若左子树为空，则层次序列中第二个结点为右子树的根。对右子树分析类似。层次序列的特点是：从左到右每个结点或是当前情况下子树的根或是叶子。

IBCDFHEGA9.用一维数组存放一棵完全二叉树：ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。 解：HIDJKEBLFGCA。

10.已知一棵二叉树的中序遍历序列为DGBAECHIF，后序遍历序列为：GDBEIHFCA。 (1)试画出该二叉树；

(2)试画出该二叉树的中序线索树； (3)试画出该二叉树对应的森林。 解：（1）

2

第6章 树与二叉树

（2）略 （3）

DGBHEIACFIDGEHFBAC11.设有正文AADBAACACCDACACAAD，字符集为A、B、C、D，设计一套二进制编码，使得上述正文的编码最短。

解：字符A、B、C、D出现的次数为9、1、5、3。其哈夫曼编码如下： A：1，B：000，C：01，D：001。 其哈夫曼树为：

101500191312.假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树T中，写出计算该算术表达式值的算法。

解：typedef struct Node{ ElemType data; float val;

char optr;//只取+、-、*、/ struct Node *lchild,*rchild }BiNode,*BiTree;

3

第6章 树与二叉树

float PostEval(BiTree t){//以后序遍历算法求以二叉树表示的算术表达式的值 float lv,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; } }

return value; }

13.假设二叉链表为二叉树的存储结构，编写判断给定的二叉树是否相似的算法。所谓二叉树t1和t2相似指的是：t1和t2都是空树；或者t1和t2的根结点是相似的，以及t1的左子树和t2的左子树是相似的且t1的右子树和t2的右子树是相似的。

解：

int Like(BiTree t1, BiTree t2){ int like1,like2;

if(t1==NULL&&t2==NULL)return 1; else if(t1==NULL||t2==NULL)return 0; else{ } }

14.假设二叉链表为二叉树的存储结构，编写递归算法，将二叉树中所有结点的左、右子树相互交换。 解：

void Exchange(BiTree &t){ if(t){ BiTree s;

s=t->lchild;t->lchild=t->rchild;t->rchild=s;

4

like1=Like(t1->lchild,t2->lchild); like2=Like(t1->rchild,t2->rchild); return (like1 & like2);

第6章 树与二叉树

Exchange(t->lchild);

Exchange(t->rchild); } }

15.编写求双亲表示法表示的树的深度的算法。 解：

int Depth(PTree t){ int maxdepth=0,i,temp,f; for(i=0;i

return maxdepth; }

16.假设二叉链表为二叉树的存储结构，编写按层次遍历方式计算二叉树结点个数的算法。 解：

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); temp=0;f=i;

while(f>-1){temp++;f=t.nodes[f].parent;} if(temp>maxdepth)maxdepth=temp;

}//while

}//if return num; }

17.编写算法，利用叶子结点中的空指针域将所有叶子结点链接为一个带有头结点的双向链表，算法返回头结点的指针。

解：BiTree head,pre;//全局变量链表头指针head，pre

5

本文来源：https://www.bwwdw.com/article/0ygf.html