习题五及上机答案.doc

习题五
5.1 已知一棵树边的集合为(I,M),(I,N),(E,I),(B,E),(B,D),(A,B),(G,J),(G,K),(C,G),(C,F),(TABLE,L),(C,TABLE),(A,C)，画出这棵树，并回答下列问题：
⑴哪个是根结点？
⑵哪些是叶子结点？
⑶哪个是结点Ｇ的双亲？
⑷哪些是结点Ｇ的祖先？
⑸哪些是结点Ｇ的孩子？
⑹哪些是结点Ｅ的子孙？
⑺哪些是结点Ｅ的兄弟？哪些是结点Ｆ的兄弟？
⑻结点Ｂ和Ｎ的层次号分别是什么？
⑼树的深度是多少？
⑽以结点Ｃ为根的子树的深度是多少？
解：依题意，树的表示如图 8.23 所示。

（1）根结点是：a
（2）叶子结点是：d，m，n，f，j，k，l
（3）g 的双亲是：c
（4）g 的祖先是：a，c
（5）g 的孩子是：j，k
（6）e 的子孙是：i，m，n
（7）e 的兄弟是 d，f 的兄弟是 g，h
（8）b 的层次是 2，n 的层次是 5
（9）树的深度是 5
（10）以结点 c 为根的子树的深度是 3
（11）树的度数是 3
5.2 一棵度为2的树与一棵二叉树有何区别？
解：二叉树的度也可以为1。
5.3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
解：二叉树：

5.4 一棵深度为N的满Ｋ叉树有如下性质：第N层上的结点都是叶子结点，其余各层上每个结点都有Ｋ棵非空子树。如果按层次顺序从１开始对全部结点编号，问
⑴各层的结点数目是多少？
⑵编号为n 的结点的父结点（若存在）的编号是多少？
⑶编号为n 的结点的第i个儿子（若存在）的编号是多少？
⑷编号为n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？
解：
（1）第 i 层的结点数为 ki-1。
（2）编号为 n 的结点的双亲点为：「(n-2)/k」+1。
（3）编号为 n 的结点的第 i 个孩子结点为：(n-1)*k+i+1。
（4）编号为 n 的结点有右兄弟的条件是(n-1) % k≠0，其右兄弟的编号是 n+1。

5.5 已知一棵度为m的树中有n1个度为１的结点，n2个度为２的结点，．．．，nm个度为m的结点，问该树中有多少个叶子结点？
解：依题意：设 n 为总的结点个数，n0为叶子结点（即度为 0 的结点）的个数，则有：n=n+ n+n+...+n ①
又有：n-1=度的总数，即：
n-1= n*1+ n*2+...+ n*m ②
①-②式得：
1= n- n-2n-...-(m-1) n
则有： n=1+ n+2n+...+(m-1) n
=1+

5.6 试列出下列二叉树的终端结点、非终端结点以及每个结点的层次

题5.6
解：
终端结点：E、G、H
非终端结点：A、B、C、D、F
结点
A
B
C
D
E
F
G
H
层次
1
2
2
3
3
3
4
4

5.7 对于5.6题中给出的二叉树，分别列出先根次序、中根次序、后根次序的结点序列。
解：
先根次序：ABDGCEFH
中根次序：DGBAECHF
后根次序：GDBEHFCA
5.8 在二叉树的顺序存储结构中，实际上隐含着双亲的信息，因此可和三叉链表对应。假设每个指针域占４个字节的存储空间，每个信息占Ｋ个字节的存储空间。试问对于一棵有n个结点的二叉树，且在顺序存储结构中最后一个结点的下标为m，在什么条件下顺序存储结构比二叉链表更节省空间？
解：（K+4）*n<(m+1)*4
5.9 假定用两个一维数组L(1:n)和R(1:n)作为有n个结点的二叉树的存储结构，L(i)和R(i)分别指示结点i的左孩子和右孩子，0表示空。
⑴试写一个算法判别结点u是否为结点v的子孙；
⑵先由L和R建立一维数组T(1:n)，使T中第i (i=1,2,...,n)个分量指示结点i的双亲，然后写判别结点u是否为结点v的子孙的算法。
解：（1）、
int Is_Descendant_C(int u,int v)
//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0
{
if(u==v) return 1;
else
{
if(L[v])
if (Is_Descendant(u,L[v])) return 1;
if(R[v])
if (Is_Descendant(u,R[v])) return 1; //这是个递归算法
}
return 0;
}//Is_Descendant_C
（2）、
int Is_Descendant_P(int u,int v)
//在双亲存储结构上判断u是否v的子孙,是则返回1,否则返回0
{
for(p=u;p!=v&&p;p=T[p]);
if(p==v) return 1;
else return 0;
}//Is_Descendant_P

5.10 假设n和m为二叉树中的两结点，用“１”、“０”“Φ”（分别表示肯定、恰 恰相反和不一定）填写下表：

前序遍历时
中序遍历时
后序遍历时
已知
n在m前？
n在m前？
n在m前？
n在m的左方
1
1
1
n在m的右方
0
0
0
n是m的祖先
1
Φ
0
n是m的子孙
0
Φ
1

注：⑴如果离a和b最近的共同祖先p存在，且⑵a在p的左子树中，b在p的右子树中，则称a在b的左方（即b在a的右方）。

5.11 假设以二叉链表作存储结构，试分别写出前序和后序遍历的非递归算法,可直接利用栈的基本运算。
解：前序遍历：
依题意，使用一个栈 stack 实现非递归的前序遍历。
void preorder(b)
btree *b;
{
btree *stack[Maxsize],*p;
int top;
if (b!=NULL)
{
top=1; /*根结点入栈*/
stack[top]=b;
while (top>0) /*栈不为空时循环*/
{
p=stack[top]; /*退栈并访问该结点*/
top--;
printf("%d "，p->data);
if (p->right!=NULL) /*右孩子入栈*/
{
top++;
stack[top]=p->right;
}
if (p->left!=NULL) /*左孩子入栈*/
{
top++;
stack[top]=p->left;
}
}
}
}
后序遍历：
根据后序遍历二叉树的递归定义，转换成非递归函数时采用一个栈保存返回的结点，先扫描根结点的所有左结点并入栈，出栈一个结点，然后扫描该结点的右结点并入栈，再扫描该右结点的所有左结点并入栈，当一个结点的左右子树均访问后再访问该结点，如此这样，直到栈空为止。在访问根结点的右子树后，当指针 p 指向右子树树根时，必须记下根结点的位置，以便在遍历右子树之后正确返回，这就产生了一个问题：在退栈回到根结点时如何区别是从左子树返回还是从右子树返回。这里采用两个栈 stack 和 tag，并用一个共同的栈顶指针，一个存放指针值，一个存放左右子树标志（0 为左子树，1 为右子树）。退栈时在退出结点指针的同时区别是遍历左子树返回的还是遍历右子树返回的，以决定下一步是继续遍历右子树还是访问根结点。
因此，实现本题功能的函数如下：
void postorder(btree *b)
{
btree* stack[Maxsize],*p;
int tag[Maxsize];
int top=0;
p=b;
do
{
while(p!=NULL) /*扫描左结点,入栈*/
{
top++;
stack[top]=p;
tag[top]=0;
p=p->left;
}
if(top>0)
{
if(tag[top]==1) /*左右结点均已访问过,则访问该结点*/
{
printf("%c ",stack[top]->data);
top--;
}
else
{
p=stack[top];
if(top>0)
{
p=p->right; /*扫描右结点*/
tag[top]=1; /*表示当前结点的右子树已访问过*/
}
}
}
} while(p!=NULL||top!=0);
}
5.12 假设在二叉链表中增设两个域：双亲域（parent）以指示其双亲结点；标志域（mark）：０．．２，以区分在遍历过程中到达该结点时应该继续向左或向右或访问该结点。试以此存储结构编写不用栈的后序遍历的算法。
解：
typedef struct {
int data;
EBTNode *lchild;
EBTNode *rchild;
EBTNode *parent;
enum {0,1,2} mark;
} EBTNode,EBitree; //有mark域和双亲指针域的二叉树结点类型
void PostOrder_Nonrecursive(EBitree T)//后序遍历二叉树的非递归算法,不用栈
{
p=T;
while(p)
switch(p->mark)
{
case 0:
p->mark=1;
if(p->lchild) p=p->lchild; //访问左子树
break;
case 1:
p->mark=2;
if(p->rchild) p=p->rchild; //访问右子树
break;
case 2:
visit(p);
p->mark=0; //恢复mark值
p=p->parent; //返回双亲结点
}
}//PostOrder_Nonrecursive
分析:本题思路与上一题完全相同,只不过结点的mark值是储存在结点中的,而不是暂存在堆栈中,所以访问完毕后要将mark域恢复为0,以备下一次遍历.
5.13 试编写算法在一棵以二叉链表存储的二叉树中求这样的结点：它在前序序列中处第Ｋ个位置。
解：
int c,k; //这里把k和计数器c作为全局变量处理
void Get_PreSeq(Bitree T)//求先序序列为k的结点的值
{
if(T)
{
c++; //每访问一个子树的根都会使前序序号计数器加1
if(c==k)
{
printf("Value is %d\n",T->data);
exit (1);
}
else
{
Get_PreSeq(T->lchild); //在左子树中查找
Get_PreSeq(T->rchild); //在右子树中查找
}
}//if
}//Get_PreSeq
main()
{
...
scanf("%d",&k);
c=0; //在主函数中调用前,要给计数器赋初值0
Get_PreSeq(T,k);
}//main
5.14 试以二叉链表作存储结构，编写计算二叉树中叶子结点数目的递归算法。
解：依题意：计算一棵二叉树的叶子结点数的递归模型如下：

因此，实现本题功能的函数如下：
int leafs(btree *b)
{
int num1，num2;
if (b==NULL) return(0);
else if (b->left==NULL && b->right==NULL) return(1);
else
{
num1=leafs(b->left);
num2=leafs(b->right);
return(num1+num2);
}
}

5.15 以二叉链表作存储结构，编定算法将二叉树中所有结点的左、右子树相互交换。
解：依题意：交换二叉树的左、右子树的递归模型如下：

因此，实现本题功能的函数如下：
btree *swap(btree *b)
{ btree *t，*t1，*t2;
if (b==NULL) t=NULL;
else
{
t=(btree *)malloc(sizeof(btree)); /*复制一个根结点*/
t->data=b->data;
t1=swap(b->left);
t2=swap(b->right);
t->left=t2;
t->right=t1;
}
return(t);
}

5.16 已知一棵二叉树以二叉链表作存储结构，编写完成下列操作的算法：对于树中每个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
解：依题意：设 print 是以嵌套括号表示输出一个二叉树，本题的算法是：先判定根结点数据域是否为 x，若是则直接输出该二叉树；否则调用的函数对应的递归模型如下：
因此，实现本题功能的函数如下：
btree *delsubtree(btree *b，int x)
{ btree *s;
if (b!=NULL)
if (b->data==x) /*根结点值等于 x 的情况，直接删除*/
{ print(b);
s=NULL;
}
else s=finddel(b，x);
return(s);
}
btree *finddel(btree *p，int x)
{ btree *s;
if (p!=NULL)
{
if (p->left!=NULL && p->left->data==x)
{ print(p->left);
p->left=NULL;
}
if (p->right!=NULL && p->right->data==x)
{ print(p->right);
p->right=NULL;
}
s=finddel(p->left，x);
p->left=s;
s=finddel(p->right，x);
p->right=s;
}
return(p);
}
void print(btree *b)
{ if (b!=NULL)
{
printf("%d"，b->data);
if (b->left!=NULL || b->right!=NULL)
{
printf("(");
print(b->left);
if (b->right!=NULL) printf("，");
print(b->right);
printf(")");
}
}
}
5.17 已知一棵以二叉链表作存储结构的二叉树，试编写复制这棵二叉树的非递归算法。
解：依题意：复制一棵二叉树的递归模型如下：

因此，实现本题功能的递归函数如下：
btree *copy(btree *b)
{ btree *p;
if (b!=NULL)
{
p=(btree *)malloc(sizeof(btree));
p->data=b->data;
p->left=copy(b->left);
p->right=copy(b->right);
return(p);
}
else return(NULL);
}
5.18 已知一棵以二叉链表为存储结构的二叉树，试编写层次顺序（同一层自左向右）遍历二叉树的算法。
解：依题意：本算法要采用一个队列 q，先将二叉树根结点入队列，然后退队列，输出该结点，若它有左子树，便将左子树根结点入队列，若它有右子树，便将右子树根结点入队列，如此直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树的目的。
因此，实现本题功能的函数如下：
#define MAXLEN 100
void translevel(btree *b)
{
struct node
{
btree *vec[MAXLEN];
int f，r;
} q;
q.f=0; /*置队列为空队列*/
q.r=0;
if (b!=NULL) printf("%d "，b->data);
q.vec[q.r]=b; /*结点指针进入队列*/
q.r=q.r+1;
if (b!=NULL) printf("%d "，b->data);
q.vec[q.r]=b; /*结点指针进入队列*/
q.r=q.r+1;
while (q.f<q.r) /*队列不为空*/
{
b=q.vec[q.f]; /*队头出队列*/
q.f=q.f+1;
if (b->left!=NULL) /*输出左孩子，并入队列*/
{
printf("%d "，b->left->data);
q.vec[q.r]=b->left;
q.r=q.r+1;
}
if (b->right!=NULL) /*输出右孩子，并入队列*/
{
printf("%d "，b->right->data);
q.vec[q.r]=b->right;
q.r=q.r+1;
}
}
}
5.19 试以二叉链表作存储结构，编写算法判别给定二叉树是否为完全二叉树。
解：
int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0
{
InitQueue(Q);
flag=0;
EnQueue(Q,T); //建立工作队列
while(!QueueEmpty(Q))
{
DeQueue(Q,p);
if(!p) flag=1;
else if(flag) return 0;
else
{
EnQueue(Q,p->lchild);
EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列
}
}//while
return 1;
}//IsFull_Bitree
分析:该问题可以通过层序遍历的方法来解决.与62.相比,作了一个修改,不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针.

5.20 已知一棵完全二叉树存在于顺序存储结构A(1:max)中，A[1:n]含结点值。试编写算法由此顺序结点建立该二叉树的二叉链表。
解：Status CreateBitree_SqList(Bitree &T,SqList A)//根据顺序存储结构建立二叉链表
{
Bitree ptr[A.last+1]; //该数组储存与sa中各结点对应的树指针
if(!A.last)
{
T=NULL; //空树
return;
}
ptr[1]=(BTNode*)malloc(sizeof(BTNode));
ptr[1]->data=A.elem[1]; //建立树根
T=ptr[1];
for(i=2;i<=A.last;i++)
{
if(!A.elem[i]) return ERROR; //顺序错误
ptr[i]=(BTNode*)malloc(sizeof(BTNode));
ptr[i]->data=A.elem[i];
j=i/2; //找到结点i的双亲j
if(i-j*2) ptr[j]->rchild=ptr[i]; //i是j的右孩子
else ptr[j]->lchild=ptr[i]; //i是j的左孩子
}
return OK;
}//CreateBitree_SqList
5.21 编写一个算法，输出以二叉树表示的算术表达式，若该表达式中含有括号，则在输出时应该添上，已知二叉树的存储结构为二叉链表。
解：
Status Print_Expression(Bitree T)//按标准形式输出以二叉树存储的表达式
{
if(T->data是字母) printf("%c",T->data);
else if(T->data是操作符)
{
if(!T->lchild||!T->rchild) return ERROR; //格式错误
if(T->lchild->data是操作符&&T->lchild->data优先级低于T->data)
{
printf("(");
if(!Print_Expression(T->lchild)) return ERROR;
printf(")");
} //注意在什么情况下要加括号
else if(!Print_Expression(T->lchild)) return ERROR;
if(T->rchild->data是操作符&&T->rchild->data优先级低于T->data)
{
printf("(");
if(!Print_Expression(T->rchild)) return ERROR;
printf(")");
}
else if(!Print_Expression(T->rchild)) return ERROR;
}
else return ERROR; //非法字符
return OK;
}//Print_Expression
5.22 一棵二叉树的直径定义为，从二叉树的根结点到所有叶子结点的路径长度的最大值。假设以二叉链表作存储结构，试编写算法求给定二叉树的直径和其长度等于直径的一条路径（即从根到该叶子结点的序列）。
解：
int maxh;
Status Printpath_MaxdepthS1(Bitree T)//求深度等于树高度减一的最靠左的结点
{
Bitree pathd;
maxh=Get_Depth(T); //Get_Depth函数见6.44
if(maxh<2) return ERROR; //无符合条件结点
Find_h(T,1);
return OK;
}//Printpath_MaxdepthS1
void Find_h(Bitree T,int h)//寻找深度为maxh-1的结点
{
path[h]=T;
if(h==maxh-1)
{
for(i=1;path[i];i++) printf("%c",path[i]->data);
exit; //打印输出路径
}
else
{
if(T->lchild) Find_h(T->lchild,h+1);
if(T->rchild) Find_h(T->rchild,h+1);
}
path[h]=NULL; //回溯
}//Find_h

5.23 试分别画出下列各二叉树的先序、中序、后序的线索二叉树。

(a) (b) (c) (d) (e)
A
题5.23
解：（a）先序、中序、后序的线索二叉树都是：
（b）前序： 中序和后序（一样）：
A
B
C
A
B
C

（c）前序和中序（一样）： 后序：
A
B
C
A
B
C

（d）前序： 中序：
A
B
C
A
B
C

后序：
A
B
C

（e）前序：
B
C
D
E
F
I
G
H
J
K
M
A

中序：
B
C
D
E
F
I
G
H
J
K
M
A

后序：
B
C
D
E
F
I
G
H
J
K
M
A

5.24 试编写一个算法，在中序线索二叉树中，结点p↑之下插入一棵以结点x↑为根，只有左子树的中序全线索化二叉树，使x↑为根的二叉树成为p↑的左子树，若p↑原来有左子树，则令它为x↑的右子树。完成插入之后二叉树应保持线索化特性。
解：
Status Insert_BiThrTree(BiThrTree &T,BiThrTree &p,BiThrTree &x)//在中序线索二叉树T的结点p下插入子树x
{
if(!p->ltag&&!p->rtag) return INFEASIBLE; //无法插入
if(p->ltag) //x作为p的左子树
{
s=p->lchild; //s为p的前驱
p->ltag=Link;
p->lchild=x;
q=x;
while(q->lchild) q=q->lchild;
q->lchild=s; //找到子树中的最左结点,并修改其前驱指向s
q=x;
while(q->rchild) q=q->rchild;
q->rchild=p; //找到子树中的最右结点,并修改其前驱指向p
}
else //x作为p的右子树
{
s=p->rchild; //s为p的后继
p->rtag=Link;
p->rchild=x;
q=x;
while(q->rchild) q=q->rchild;
q->rchild=s; //找到子树中的最右结点,并修改其前驱指向s
q=x;
while(q->lchild) q=q->lchild;
q->lchild=p; //找到子树中的最左结点,并修改其前驱指向p
}
return OK;
}//Insert_BiThrTree

5.25 已知一棵以线索链表作存储结构的中序线索二叉树，试编写在此二叉树上找后序后继的算法。
解：在中序线索二叉树中求结点后继的算法：由于是中序线索二叉树，后继有时可直接利用线索得到，rtag 为 0 时需要查找，即右子树中最左下的子孙便为后继结点。本函数如下：
tbtree *succ(tbtree *p)
{ btree *q;
if (p->rtag==1) return(p->right); /*由后继线索直接得到*/
else
{ q=p->right;
while (q->ltag==0) q=q->left;
return(q);
}
}
以此给出中序遍历二叉树的非递归算法：只要从头结点出发，反复找到结点的后继，直至结束。本函数如下：
void thinorder(tbtree)
btree *t，*h; /*t：原二叉树的根结点指针，h：中序线索二叉树头结点*/
{
if (t!=NULL)
{
p=h;
do
{ printf("%d "，p->data);
p=succ(p);
}
while (p!=NULL);
}
}
5.26 将下列森林转化为相应的二叉树，并按中序遍历进行线索化：

题5.26
解：二叉树：
1
2
9
3
4
10
12
14
13
11
5
15

线索二叉树：
1
2
9
3
4
10
12
14
13
11
5
15

5.27 画出和题5.23所示各二叉树相应的森林：
解：
A
B
C
(c)
A
B
C
(d)
B
E
H
K
G
J
C
F
I
M
D
A
(e)

5.28 对以下存储结构分别写出计算树的深度的算法：
⑴ 双亲表示法； ⑵ 孩子链表表示法； ⑶ 孩子兄弟表示法。
解：（1）
int GetDepth_PTree(PTree T)//求双亲表表示的树T的深度
{
maxdep=0;
for(i=0;i<T.n;i++)
{
dep=0;
for(j=i;j>=0;j=T.nodes[j].parent) dep++; //求每一个结点的深度
if(dep>maxdep) maxdep=dep;
}
return maxdep;
}//GetDepth_PTree
（2）
int GetDepth_CTree(CTree A)//求孩子链表表示的树A的深度
{
return SubDepth(A.r);
}//GetDepth_CTree
int SubDepth(int T)//求子树T的深度
{
if(!A.nodes[T].firstchild) return 1;
for(sd=1,p=A.nodes[T].firstchild;p;p=p->next)
if((d=SubDepth(p->child))>sd) sd=d;
return sd+1;
}//SubDepth
（3）
int GetDepth_CSTree(CSTree T)//求孩子兄弟链表表示的树T的深度
{
if(!T) return 0; //空树
else
{
for(maxd=0,p=T->firstchild;p;p=p->nextsib)
if((d=GetDepth_CSTree(p))>maxd) maxd=d; //子树的最大深度
return maxd+1;
}
}//GetDepth_CSTree
5.29 假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。
解：
A
B
E
G
D
C
I
F
H
J

5.30 证明：树中结点u是结点v的祖先，当且仅当在先序序列中u在v之前，且在后序序列中u在v之后。

5.31 证明：在结点数大于１的哈夫曼树中不存在度为１的结点。

5.32 设有一组权ＷＧ＝1,4,9,16,25,36,49,64,81,100，试画出其哈夫曼树，并计算加权的路径长度。
解：
385
4
166
1
9
219
81
85
100
119
36
49
55
64
25
30
14
16
5

WPL=1*7+4*7+9*6+16*5+25*4+36*3+49*3+64*3+81*2+100*2=1108
5.33 假设用于通讯的电文仅由８个字母组成，字母在电文中出现的频率分别为７，１９，２，６，３２，３，２１，１０。试为这８个字母设计哈夫曼编码，使用０～７的二进制表示形式是另一编码方案。对于上述实例，比较两这方案的优缺点。
解：设这8个字母分别是：A、B、C、D、E、F、G、H。
哈夫曼树：如下图。
所以：A：0010 B：10 C：00000 D：0001
E：01 F：00001 G：11 H：0011
100
40
21
6
60
28
11
32
19
5
17
3
7
10
2

5.34 证明：由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。
证明：采用递归法证明。
当 n