第6章 综合练习

6.2综合练习

1. 设在树中，结点x 是结点y 的双亲时，用<x,y>来表示边。已知一棵树边的集合为：{<a,b>,<a,c>,<a,d>,<a,e>,<c,f>,<c,g>,<c,h>,<d,i>,<e,j>,<e,k>,<g,l>,<l,m>,<l,n>}，用树形表示法画出此树，并回答下列问题：

(1)哪个是根结点？ (2)哪些是叶子结点？

(3)哪个是e的孩子？ (4)哪些是g的祖先？

(5)哪些是c的子孙？ (6)哪些是f的兄弟？

(7)结点b和j的层次各是多少？ (8)树的深度是多少？

(9)树的度数是多少？

【解答】

(1)a是根结点 （2）b,f,h,i,j,k,l,m,n是叶结点

(3)j,k是e的孩子 (4) a,c是g的祖先

(5)f,g,h,l,m,n是c的子孙 (6) g,h是f的兄弟

(7)b的层次是2，j的层次是3 (8)树的深度是5。

(9)树的度是4

2．列出图6.12所示二叉树的叶结点、分支结点和每个结点的层次。

【解答】

E、I、H是叶结点；A、B、C、D、F、G是分支结点；

A的层次是1，B、F的层次是2，C、G、H的层次是3，D、I的层次是4，E的层次是5。

3．使用 (1) 顺序表示 (2) 二叉链表表示法(3)三叉链表分别画出图6.13所示二叉树的存储表示。

1 2 3 4 5 6 7 8 9 10 11 12 13

A B D C φ E F φ φ φ φ φ G

4 某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数是多少。

【解答】

∵ n=n0+n1+n2 且 n2=n0-1

∴ n=2n0+n1-1=2*20+30-1=69

5. 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是多少。

【解答】

H=ëlog₃244û+1=6

6. 在结点个数为n(n>1)的四叉树中，高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？

【解答】

最大高度为n；有1个叶结点；n-1个分支结点；

最小高度为；

叶结点的个数为；

分支结点的个数为。

7．试分别找出满足以下条件的所有二叉树：

(1) 二叉树的前序序列与中序序列相同， 则或为空树，或为任一结点至多只有右子树的二叉树；

(2) 二叉树的中序序列与后序序列相同， 则或为空树，或为任一结点至多只有左子树的二叉树；

(3) 二叉树的前序序列与后序序列相同， 则或为空树，或为只有根结点的二叉树。

8． 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，试画出这棵二叉树。

【解答】

9． 已知一棵二叉树的后序遍历序列为EICBGAHDF，同时知道该二叉树的中序遍历序列为CEIFGBADH，试画出该二叉树。

【解答】

10. 设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用#表示，现前序遍历二叉树，访问的结点序列为ABD##C#E##F##，写出中序和后序遍历二叉树时结点的访问序列。

【解答】

该二叉树为

中序遍历序列为：DBCEAF

后序遍历序列为：DECBFA

11. 有n个结点的k叉树中（k≥2）的k叉链表表示中，有多少个空指针？

【解答】

(k-1)n+1个空指针。

12. 假定某二叉树的前序遍历序列为ABCDEFGHIJ，后序遍历序列为CEFDBJIHGA，据此两个序列能否唯一确定此二叉树? 若不能，试画出两样具有同样上述遍历序列的二叉树。

【解答】不能。

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

【解答】

后序遍历序列为：HIDJKEBLFGCA

14.画出图6.14二叉树的后序线索二叉树表示法。

【解答】

15. 已知二叉树T的前序遍历序列和中序遍历序列分别为E D C H A B F G I和D H C E F B G I A 。（1）试求出(画出)二叉树T；（2）画出与二叉树T对应的中序线索二叉树。

【解答】

16. 已知二叉树如图6.15所示，

（1）写出二叉树先序遍历的结果序列；

（2）给出二叉树转化成的森林；

（3）在二叉树上加上相应的后序线索，使其成为后序线索二叉树（线索用带箭头的虚线表示）。

【解答】

(1)前序遍历序列为：ABDECFGH

（2）转化的森林为：

(3)

17. 画出图6.16所示的树所对应的二叉树。

【解答】

对应的二叉树：

18.如图6.17所示的森林，回答下列问题：

（1）画出与之等价的二叉树；

（2）画出相应二叉树的前序线索树；

（3）画出相应二叉树的中序后继线索树。

【解答】

19. 试用三种表示法画出图6.18所示的树的存储结构， (1) 双亲表示法：(2) 孩子表示法；(3)孩子兄弟表示法。

【解答】

孩子兄弟链表： 双亲链表：

20. 某通信电文由Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ六个字符组成，它们在电文中出现的次数分别是16,5,9,3,20,1。试画出其哈夫曼树并确定其对应的哈夫曼编码。

【解答】

哈夫曼编码为：

A：10

B：1101

C：111

D：11001

E：0

F：11000

21．以二叉链表作为存储结构，设计算法求出二叉树T中度为2的结点数。

【解答】

int Count(BitTree T)

{//求二叉树中度为2的结点数目

if(!T) return 0; //空树没有叶子

else if(T->lchild&&T->rchild) return 1; //2度结点

else return Count(T->lchild)+Count(T->rchild);

//左子树2度结点数加上右子树2度结点数

}

22．以二叉链表作为存储结构，设计算法求二叉树T中的结点数。

【解答】

计算二叉树的结点数的递归模型如下：

int NodeCount(BitTree T)

{//求二叉树中结点的数目

if(!T) return 0; //空树没有结点

else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;

//左、右子树结点数加根结点

}

23．假设二叉树T采用如下定义的存储结构：
typedef struct Node

{DataType data;
struct Node *lchild,*rchild,*parent;
}PBinTree;

其中，结点的lchild域和rchild域已分别填有指向其左、右孩子结点的指针，而parent域中

的值为空指针(拟作为指向双亲结点的指针域)。请编写一个算法，将该存储结构中各结点的

parent域的值修改成指向其双亲结点的指针。

【解答】

PBinTree creat(PBinTree T)

{PBinTree p,Q[ ]; //Q是二叉树结点指针的一维数组，足够大

int front,rear=0; //置队列为空

p=T;

rear++;

Q[rear]=p; //根结点入队列

while(rear!=front) //队列不为空时

{if(rear!=1) Q[rear]->parent=Q[rear/2];

front++; //队头元素出队列

if(Q[front].lchild) //左孩子入队列

{Q.rear++;

Q[rear]=Q[front].lchild;

}

if(Q[front].rchild) //右孩子入队列

{Q.rear++;

Q[rear]=Q[front].rchild);

}

}

}

24. 若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：

(1) 统计二叉树中叶结点的个数。

(2) 交换每个结点的左子女和右子女。

若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：

【解答】

(1) 统计二叉树中叶结点的个数。

void Count(BiTree bt,int *n0) //统计二叉树bt上叶子结点数n0和非叶子结点数n

{if(bt)

{if (bt->lchild==null && bt->rchild==null) *n0++；//叶子结点

Count(bt->lchild,&n0);

Count(bt->rchild,&n0);

}

}//结束 Count

(2) 交换每个结点的左子女和右子女。

void Exchange(BiTree bt)

//交换每个结点的左子女和右子女

{if(bt)

{Exchange(bt->lchild); // 递归交换左子树上每个结点的左子女和右子女

Exchange (bt->rchild); // 递归交换右子树上每个结点的左子女和右子女

p=bt->lchild; //// 交换根结点的左子女和右子女

bt->lchild=bt->rchild;

bt->rchild=p;

}

}//结束 Count

25. 二叉树的双序遍历(Double-order traversal)是指：对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树。试写出执行这种双序遍历的算法。

【解答】

void D_O_Traversal(BiTree t)

{if (t)

{visit(*t); //如输出结点的值，可用printf(t->data)

D_O_Traversal(t-lchild);

visit(*t);

D_O_Traversal(t-rchild);

}

}

26. 已知在二叉树中，*root为根结点，*p和*q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。

【题目分析】后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。

【解答】

typedef struct

{BiTree t;int tag;//tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问

}stack;

stack s[],s1[];//栈，容量够大

BiTree Ancestor(BiTree root,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。

{top=0; bt=root;

while(bt!=null ||top>0)

{while(bt!=null && bt!=p && bt!=q) //结点入栈

{s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下

if(bt==p) //不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点

{for(i=1;i<=top;i++) s1[i]=s[i]; top1=top; }//将栈s的元素转入辅助栈s1 保存

if(bt==q) //找到q 结点。

for(i=top;i>0;i--)//；将栈中元素的树结点到s1去匹配

{pp=s[i].t;

for (j=top1;j>0;j--)

if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”)；return (pp);}

｝

while(top!=0 && s[top].tag==1) top--; //退栈

if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ //沿右分枝向下遍历

}//结束while(bt!=null ||top>0)

return(null);//ｑ、p无公共祖先

｝//结束Ancestor

27. 以二叉链表作为存储结构，设计按层次遍历二叉树的算法。

【解答】

void Level(BiTree bt) //层次遍历二叉树

{if(bt){QueueInit(Q); QueueIn(Q,bt)；//Q是以二叉树结点指针为元素的队列

while(!QueueEmpty(Q))

{p=QueueOut(Q); printf(p->data); //出队,访问结点

if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入队

if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入队

}

}//if(bt)

}

28. 编写算法查找二叉链表中数据域值为x的结点（假定各结点的数据域值各不相同），并打印出x所有祖先的数据域值（提示：利用后序遍历非递归算法）。

【解答】 后序遍历最后访问根结点，当访问到值为x的结点时，栈中所有元素均为该结点的祖先。

void Search(BiTree bt,ElemType x) //在二叉树bt中，查找值为x的结点，并打印其所有祖先

{typedef struct

{BiTree t; int tag; }stack;//tag=0表示左子女被访问，tag=1表示右子女被访问

stack s[]; //栈容量足够大

top=0;

while(bt!=null||top>0)

{while(bt!=null && bt->data!=x) //结点入栈

{s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下

if(bt->data==x){ printf(“所查结点的所有祖先结点的值为:\n”); //找到x

for(i=1;i<=top;i++) printf(s[i].t->data); return; } //输出祖先值后结束

while(top!=0 && s[top].tag==1) top--; //退栈（空遍历）

if(top!=0) {s[top].tag=1;bt=s[top].t->rchild;} //沿右分枝向下遍历

}// while(bt!=null||top>0)

}//结束search

因为查找的过程就是后序遍历的过程，使用的栈的深度不超过树的深度，算法复杂度为O(logn)。

29. 试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的数目。

【解答】当森林（树）以孩子兄弟表示法存储时，若结点没有孩子（fch=null）,则它必是叶子，总的叶子结点是孩子子树（fch）上的叶子数和兄弟（nsib）子树上叶结数之和。

typedef struct node

{ElemType data;//数据域

struct node *fch, *nsib;//孩子与兄弟域 }*Tree;

int Leaves (Tree t)

//计算以孩子-兄弟表示法存储的森林的叶子数

{if (t) if (t->fch==null) //若结点无孩子，则该结点必是叶子

return(1+Leaves(t->nsib)); //返回叶子结点和其兄弟子树中的叶子结点数

else return (Leaves(t->fch)+Leaves(t->nsib)); //孩子子树和兄弟子树中叶子数之和

}//结束Leaves

30． 已知一棵二叉树的中序序列和后序序列分别为存于两个一维数组中，试编写算法建立该二叉树的二叉链表。

【解答】

（1）递归算法

BiTree IntoPost(ElemType in[],post[],int l1,h1,l2,h2)

//in和post是二叉树的中序序列和后序序列,l1,h1,l2,h2分别是两序列第一和最后结点的下标

{BiTree bt=(BiTree)malloc(sizeof(BiNode));//申请结点

bt->data=post[h2];//后序遍历序列最后一个元素是根结点数据

for(i=l1;i<=h1;i++)

if(in[i]==post[h2]) break;//在中序序列中查找根结点

L=i-l1;// 左子树的长度

if(i==l1) bt->lchild=null; //处理左子树

else bt->lchild=IntoPost(in,post,l1,i-1,l2,l2+L-1)；

if(i==h1) bt->rchild=null; //处理右子树

else bt->rchild=IntoPost(in,post,i+1,h1,l2+L,h2-1);

return(bt);

}

（2）非递归算法

void InPostCreat(ElemType IN[],POST[],int l1,h1,l2,h2)

//由二叉树的中序序列IN[]和后序序列POST[]建立二叉树，l1,h1和l2,h2分别是中序序列和

//后序序列第一和最后元素的下标，初始调用时，l1=l2=1,h1=h2=n。

{typedef struct {int l1,h1,l2,h2; BiTree t; }node;

node s[],p;//s为栈，容量足够大

BiTree bt=(BiNode *)malloc(sizeof(BiNode));

int top=0,i;

p.l1=l1; p.h1=h1; p.l2=l2; p.h2=h2; p.t=bt;

s[++top]=p;//初始化

while(top>0)

{p=s[top--]; //取出栈顶数据

bt=p.t; l1=p.l1; h1=p.h1; l2=p.l2; h2=p.h2;

for(i=l1;i<=h1;i++) //在中序序列中查等于POST[h2]的结点

if(IN[i]==POST[h2]) break;

bt->data=POST[h2]; //根结点的值

L=i-l1;

if(i==l1) bt->lchild=null; //bt无左子树

else //将建立左子树的数据入栈

{bt->lchild=(BiNode *)malloc(sizeof(BiNode));

p.t=bt->lchild;p.l1=l1; p.h1=i-1; p.l2=l2; p.h2=l2+L-1;

s[++top]=p;

}

if(i==h1) bt->rchild=null; //bt无右子树

else {bt->rchild=(BiNode *)malloc(sizeof(BiNode));

p.t=bt->rchild; p.l1=i+1; p.h1=h1; p.l2=l2+L; p.h2=h2-1;

s[++top]=p; //右子树数据入栈

}

}// while(top>0)

}结束InPostCreat

31. 分别编写二叉树中序遍历在下列存储结构上的非递归算法：

(1)二叉链表；

(2)三叉链表（提示：考虑是否需要引入工作栈）；

【解答】

（1）分析：在以二叉链表为存储结构的二叉树上非递归中序遍历时要引入栈保存返回的结点，先使根结点的所有左结点进栈，出栈一个结点则访问之，然后使该结点的右结点入栈再使该右结点的所有左结点入栈，重复此工作，直到栈空为止。

void InorderStack(BitTree T)

{BitTree s[10];

top=0; p=T;

while(p||top!=0)

if(p)

{top++; s[top]=p; //从根结点开始向左走到尽头，经过的结点依次入栈

p=p->lchild;

}

else {printf(p->data);

top--; //出栈

p=s[top]->rchild; //遍历栈顶指针所指结点的右子树

}

}

（2）分析：因为每个结点多了指向双亲的指针，因此在遍历结点的右兄弟时可利用指向双亲的指针找到它。这样在处理过程中就不用设栈。

typedef struct

{ int data;

PBTNode *lchild, *rchild;

PBTNode *parent;

}PBTNode,*PBiTree; //有双亲指针域的二叉树结点类型

void InorderNoStack(PBitree T)

{//不设栈非递归中序遍历有双亲指针的二叉树

p=T;

while(p->lchild) p=p->lchild; //向左走到尽头

while(p)

{printf(p);

if(p->rchild) //当有右子树时寻找中序后继

{p=p->rchild;

while(p->lchild) p=p->lchild; //后继就是在右子树中向左走到尽头

}

else if(p->parent->lchild==p)

p=p->parent; //当自己是双亲的左孩子时后继就是双亲

else

{p=p->parent;

while(p->parent&&p->parent->rchild==p) p=p->parent;

p=p->parent;

}//当自己是双亲的右孩子时后继就是向上返回直到遇到自己在其左子树中的祖先

}

}

=======================================================================

void InorderNoStack(PBitree T)

{//不设栈非递归中序遍历有双亲指针的二叉树

PBitree q=T, p=null;

while(q)

{while(q!=null)

{p=q; q=q->lchild; } //向左走到尽头

if(p)

{ printf(p->data); q=p->rchild; }//右转

寻找中序后继

while(p!=null && q==null)

{while(p!=null && q=p->rchild)

{q=p;

p=q->parent;

}

if(p!=null)

{ printf(p->data);

q=q->rchild;

}

}

}

}