第5章参考答案08

1、练习及参考答案一选择题：123可5678910CCBBBCBDAD1112131415DCBB1以下说法正确的选项是C。2以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中n>0，空链域的个数为:C 。A. 2n-1 B. n-1 C. n+1D.2n+13线索化二叉树中，某结点A. p->lchild=NULLC. p -> ltag=0*p没有孩子的充要条件是B。B. p->ltag 二 1 且 p->rtag=1D. p->lchild=NULL 且 p->ltag=14. 如果结点A有3个兄弟，而且 B是A的双亲，贝U B的度是B。A.

2、 3B. 4C. 5D. 15. 某二叉树T有n个结点，设按某种顺序对 T中的每个结点进行编号，编号值为 1,2, n,且有如下性质：T中任意结点v,其编号等于左子树上的最小编号减 1，而v的右子树的 结点中，其最小编号等于 v左子树上结点的最大编号加 1。这是按B编号的。6.设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，B中右指针域为空的结点有C个。A. n-1B. nC. n + 1D. n + 27.棵完全二二叉树上有1001个结点，其中叶子结点的个数是C。A. 500B. 501C. 490D. 4958. 设森林F中有3棵树，第一，第二，第三棵树的结点个数分别为N1

3、，N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是 D。A. N 1B. N1+ N2C. N2D. N2+ N39. 任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序A。A.不发生改变 B发生改变C.不能确定D:以上都不对10. 假设一棵二叉树的后序遍历序列为dabec，中序遍历序列为 debac,那么先序遍历序列为D。A.cbedB.decab C. deabc D.cedba11. 假设一棵二叉树的先序遍历序列为abdgcefh;中序遍历的序列为 dgbaechf,那么后序遍霎历的结果为D。A. gcefha B. gdbecfha C. bdgaechf D.

4、gdbehfca12. 一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，那么该二叉树一定满 足B。13. 引人线索二叉树的目的的是A A：加快查找结点的前驭或后继的速度;B.为了能在二叉树中方便地进行插人与侧除；C为了能方便地找到双亲；D.使二叉树的遍历结果唯；14:设高度为h的二叉树上只有度为 0和度为2的结点，那么此类二叉树中所包含的结点 数至少为B。A. 2h2h-1C. 2h + 1D. h + 115个具有567个结点的二叉树的高h为D。“A. 9B: 10C: 9 566 之间D. 10 567 之间16给定一个整数集合3 , 5, 6, 7, 9,与该整数集合对应的哈夫曼树是

5、图中的 B，判断题12345678910XVXXVXXXVX111213M4151617181920VXVXXXVXXV1.二叉树是树的特殊形式。V2由树转换成二叉树，其根结点的右子树总是空的。VxxV那么它必是该子树的那么它必是该子树的后3.先根遍厉，棵树和先序遍历与该树对应的二叉树，其结果不同。4先根遍历森林和先序遍历与该森林对应的二叉树，其结果不同。5. 完全二叉树中，假设一个结点没有左孩子，那么它必是叶子。6. 对于有N个结点的二叉树，其高度为 log, N+ 1X7. 假设一个结点是某二叉树子树的中序遍历序列中的最后一个结点,先序遍历序列中的最后一个结点。X8. 假设一个结点是某二叉

6、树子树的中序遍历序列中的第一个结点，序遍历序列中的第一个结点。X9. 不使用递归也可实现二叉树的先序、一中序和后序遍历。V10. 先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。X11. 先序和中序遍历用线索树方式存储的二叉树，不必使用栈。V12. 在后序线索二叉树中，在任何情况下都能够很方便地找到任意结点的后继。X13. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。V14. 在哈夫曼编码中，出现频率相同的字符编码长度也一定相同x15. 用一维数组存放二叉树时，总是以先序遍历存储结点。x16. 由先序序列和后序序列能唯一确定一棵二叉树。X17. 由先序序

7、列和中序序列能唯一确定一棵二叉树。V18. 对一棵二叉树进行层次遍历时，应借助于一个栈。X19完全二叉树可采用顺序存储结构实现存储，非完全二叉树那么不能。X20满二叉树一定是完全二叉树，反之未必。V 三问答题1一棵度为2的树与一棵二叉树有何区别？树与二叉树之间有何区别？答：度为2的树至少有一个节点的读为 2,二叉树的度不一定为 2;该树不空，二叉树空以空； 树分为有序树和无序树，二叉树是有序的；二叉树有左右孩子，而树没有；二叉树度为02,而树的度是大于等于0区别：度为2的树有二个分支，没有左右之分；二叉树也有两个分支，但有左右之分，且左 右不能交换。2对于图5.38所示二叉树，试给出：1它的顺

8、序存储结构图。ABCDEFAAAGAAH(2)二叉链表存储结构示意图3双亲数组表示法:A-11B0厶AAtBCAA H AJ r K A A M A NA2C03D24E25F16G17H58I29J410K411M312N86. 证明：在结点数多于 1的哈夫曼树中不存在度为 1的结点。在哈夫曼树 的构造过程中，每次都是由两个权最小的结点构成一个父结点，即任一父结点都有两个子结点，故命题成立。7. 证明：在哈夫曼树中有n个叶结点，那么树一共有 2n-1结点。证明：在二叉树中 n0=n2+1，即n2= n0 -1而n仁0,这里n0 =n那么总结点=n 0+n2=n+n-仁2n-1和中序序列可以惟

9、一确实定一棵二叉树。先序序列的一个结点必然是根结点，而此根结点又将中序序列分成两局部，分别是其左子树和右子树结点，这样递归查找，必然可完成以确定一棵二叉树。9. 一棵度为 m的树中有n1个度为1的结点，n2个度为2的结点，nm个度为m个结点，问，该树共有多少个叶子结点？多少个非终端结点？答：设总结点数为 n,该树中共引出的边有：n1 +2*n2+m*nm,故结点数 n= n1 +2*n2+ +m*nm+1非终端结点数：s=n1 +n2+nm叶子结点p=n_s= n1 +2* n2+ +m*nm+1_ n1 +n2+ +nm=n2+(m-1)*nm10. 在具有n(n>1)个结点的树中，深

10、度最小的那棵树的度是多少？它共有多少叶子和非叶 子结点？深度最大的那棵树的度是多少？它共有多少叶子和非叶子结点？答：深度最小的那棵树的度是2, n-1个叶子和1个非叶子结点。深度最大的那棵树的度是n,1个叶子和n-1个非叶子结点。11. 设度为h的二叉树上只有度为 0和度为2的结点，问该二叉树的结点数可能到达的 最大值和最小值。结点数最大值：2h-1最小值:2h-112. 求表达式(a+b*(c-d)-e/f的波兰式前缀式和逆波兰式后缀式-+a*b-cd/efabcd-*+ef/-树的先根次序访问次序为：GFKDAIEBCHJ树的后根次序访问次序为：DIAEKFCJHBG解：根据树与二叉树的转

11、换关系以及树和二叉树的遍历定义可以推知，树的先根遍历与其转换的相应二叉树的先序遍历的结果序列相同；树的后根遍历与其转换的相应二叉树的中 序遍历的结果序列相同。故可按二叉树的规那么建立二叉树，然后转换成树。二叉树:森林的先根次序访问次序为：ABCDEFGHIJKL森林的后根次序访问次序为：CBEFDGAJIKLH解：根据森林与二叉树的转换关系以及森林和二叉树的遍历定义可以推知，森林的前序遍历和中序遍历与所转换的二叉树的先序遍历和中序遍历的结果序列相同。先画出二叉树t森林HIKJL?对应森林对应二叉树二叉树的层次访问次序为： ABCDEFGHIJKL 二叉树的中序访问次序为： CBEFDGAJIK

12、LH解:对应树16.假设用于通信的电文字符集a,b,c,d,e,f,g,中的字母构成，这率分别为0.31，0.16，0.10，0.08，0.11，0.20，0.04 为这7个字母设计哈夫曼编码。对这7个字母进行等长编码，至少需要几位二进制数? 使电文总长平均压缩多少？7个字母在电文中出现的概(1)(2)哈夫曼编码比等长编码root，试写出求二叉树结点数目的算法。左右孩子指针*/abcdefg000111101110010101111等长码长平均缩了13%四、算法设计题5-1给定一棵用二叉链表表示的二叉树，其根为#i nclude "stdio.h"#include &quo

13、t;alloc.h"#defi ne MAXSIZE 100 typedef char elemtype; typedef struct BiTNodeelemtype data;struct BiTNode *lchild;*rchild; /*BiTNode,*BiTree;elemtype *s="ABC00DE0G00F000" int sum=0;BiTree CreateBinTree()/* 以参加结点的先序序列输入，构造二叉链表 */ BiTree T;elemtype ch; if(*s='0') T=NULL;ch=*s;s+;

14、if (ch='0') T=NULL; /*读入 0 时，将相应结点置空 */生成结点空间 */构造二叉树的左子树 */ 构造二叉树的右子树 */else T=(BiTNode *)malloc(sizeof(BiTNode); /*T->data=ch;T->lchild=CreateBinTree(); /*T->rchild=CreateBinTree(); /* return T;int count(BiTree T)/* 统计叶子结点的个数值，递归程序 */ if (T=NULL)return 0; /*树空，返回 0*/elsereturn(cou

15、nt(T->lchild)+count(T->rchild)+1)/* 树不空，返回子树的结点家1*/int Leaf2(BiTree T)/* 非递归 */BiTree SeqMAXSIZE,p;int pro=-1,rear=0,sum=0;if (T=NULL) return 0;p=T;Seqrear=p;pro+;while(Seqpro) p=Seqpro; if(p->lchild=NULL&&p->rchild=NULL)sum+; if(p->lchild!=NULL) Seq+rear=p->lchild; if(p-&g

16、t;rchild!=NULL) Seq+rear=p->rchild; pro+;return sum;void main() int sum;BiTree bt; bt=CreateBinTree(); sum=Leaf2(bt);printf("Leafagenum:%d",sum); 5.2 请设计一个算法，要求该算法把二叉树的叶结点按从左至右的顺序连成一个单链表。 叉树按 lchild ， rchild 方式存储，连接时用叶结点的 rchild 域存放链指针。Linklist head,per=NULL;Linklist Inorder(BiTree,T)/*

17、 中序遍历二叉树，将叶子结点从左到右链成一个单链表，表头指针为head*/ if(T)Inorder(T->lchild);if(T->lchild=NULL&&T->rchild=NULL)if(pre=NULL)head=T;pre=T; else pre->rchild=T; pre=T; Inorder(T->rchild); pre->rchild=NULL; return;以上是一个独立的算法#include "stdio.h"#include "alloc.h"#define MAXSIZ

18、E 100typedef char elemtype;typedef struct BiTNodeelemtype data;struct BiTNode *lchild;*rchild; /* BiTNode,*BiTree;/* 处理第一个叶子结点 */* 将个叶子结点插入链表尾 */* 设置表尾结点 */左右孩子指针 */elemtype *s="ABD0G000CE00F00" BiTree stackMAXSIZE;int top=-1;void CreateBinTree(BiTree *T)/* 以参加结点的先序序列输入，构造二叉链表 */ elemtype

19、ch;/* if(*s='0') *T=NULL;*/ch=*s;s+;if (ch='0') *T=NULL; /*读入 0 时，将相应结点置空 */生成结点空间 */ 构造二叉树的左子树 */ 构造二叉树的右子树 */建立叶结点链头结点 */else *T=(BiTNode *)malloc(sizeof(BiTNode); /* (*T)->data=ch;CreateBinTree(&(*T)->lchild); /* CreateBinTree(&(*T)->rchild); /* void PreOrder(BiTr

20、ee bt)/* 先序遍历二叉树 bt, 将叶结点入栈 */if(bt=NULL)return; if(bt->lchild=NULL&&bt->rchild=NULL)stack+top=bt; /* 如果是叶结点，那么入栈保存 , 递归结束 */ PreOrder(bt->lchild); /*先序递归遍历 bt 的左子树 */PreOrder(bt->rchild); /*先序递归遍历 bt 的右子树 */BiTree Leaflink(BiTree bt) /* 建立二叉树叶结点链 */BiTree head,s;head=(BiTNode *)

21、malloc(sizeof(BiTNode); head->rchild=NULL; /* if (bt=NULL) return;PreOrder(bt);printf("n");while(top>=0) /* s=stacktop-;/*s->rchild=head->rchild; /*当栈非空 */出栈链 */插入叶结点链头部 */head->rchild=s;void InOrderOut(BiTree T)T 的结点值 */* 中序遍历输出二叉树BiTree l,r;if (T) InOrderOut(T->lchild);

22、 /* printf("n%3c ",T->data);/*InOrderOut(T->rchild); /* 中序遍历二叉树的左子树 */ 访问结点的数据 */中序遍历二叉树的右子树 */void main()BiTree bt,s;CreateBinTree(&bt);printf("n ");InOrderOut(bt);printf("n ");Leaflink(bt);5.3给定一棵用二叉链表表示的二叉树，其根指针为root,试写一个求二叉树深度的算法。#include "stdio.h&quo

23、t;#include "alloc.h"#define MAXSIZE 100typedef char elemtype;typedef struct BiTNodeelemtype data;struct BiTNode *lchild;*rchild; /*左右孩子指针 */BiTNode,*BiTree;elemtype *s="ABD0G000CE00F00"BiTree stackMAXSIZE;int top=-1;void CreateBinTree(BiTree *T)/* 以参加结点的先序序列输入，构造二叉链表 */elemtype c

24、h;/* if(*s='0') *T=NULL;*/ch=*s;s+;if (ch='0') *T=NULL; /*读入 0 时，将相应结点置空 */生成结点空间 */ 构造二叉树的左子树 */ 构造二叉树的右子树 */else *T=(BiTNode *)malloc(sizeof(BiTNode); /* (*T)->data=ch;CreateBinTree(&(*T)->lchild); /*CreateBinTree(&(*T)->rchild); /*int high(BiTree T)/* 求深度算法，递归程序 *

25、/int n1,n2;if(T=NULL)return 0; /* 树空，深度为 0*/else n1=high(T->lchild);n2=high(T->rchild);if(n1>n2) /* 树的高度为其最高子树的高度加本层高度 */ return(n1+1); else return(n2+1);void InOrderOut(BiTree T)/* 中序遍历输出二叉树 T 的结点值 */BiTree l,r;if (T)中序遍历二叉树的左子树中序遍历二叉树的右子树*/*/ printf("n%3c ",T->data);InOrderOu

26、t(T->lchild); /* /* 访问结点的数据 */InOrderOut(T->rchild); /*void main()int n;BiTree bt;CreateBinTree(&bt); n=high(bt); printf("nhigh %d",n);5.4 给定一棵用二叉链表表示的二叉树， 算法。#include "stdio.h"#include "alloc.h"#define MAXSIZE 100typedef char elemtype;typedef struct BiTNodeel

27、emtype data;struct BiTNode *lchild;*rchild; /*其根指针为 root, 试写一个求左右孩子指针 */叉树深各结点层数的BiTNode,*BiTree;elemtype *s="ABC00DE0G00F000"int sum=0;BiTree CreateBinTree()/* 以参加结点的先序序列输入，构造二叉链表 */BiTree T; elemtype ch;if(*s='0') T=NULL;ch=*s;s+;if (ch='0') T=NULL; /*读入 0 时，将相应结点置空 */els

28、e T=(BiTNode *)malloc(sizeof(BiTNode); /*生成结点空间 */T->data=ch;T->lchild=CreateBinTree(); /*构造二叉树的左子树 */T->rchild=CreateBinTree(); /*构造二叉树的右子树 */return T;int chengci(BiTree T,int n)/* 统计结点的层数，递归程序 */ if (T!=NULL) /* 非空 层数加 1*/printf("n node :%c,cangci:%d",T->data,n); if(T->lch

29、ild)chengci(T->lchild,n+1);/*左子树不空，递归统计 */if(T->rchild)chengci(T->rchild,n+1);/*右子树不空，递归统计 */ void main() int sum;BiTree bt;bt=CreateBinTree(); chengci(bt,0);5.5给定一棵用二叉链表表示的二叉树，其根指针为root,试写出将二叉树所有结点的左右子树相互交换的算法。#include "stdio.h"#include "alloc.h"#define MAXSIZE 100typed

30、ef char elemtype;typedef struct BiTNodeelemtype data;struct BiTNode *lchild;*rchild; /* 左右孩子指针 */ BiTNode,*BiTree;elemtype *s="ABC00DE0G00F000"int sum=0;BiTree CreateBinTree()/* 以参加结点的先序序列输入，构造二叉链表 */BiTree T; elemtype ch;if(*s='0') T=NULL;ch=*s;s+;if (ch='0') T=NULL; /*读入

31、0 时，将相应结点置空 */else T=(BiTNode *)malloc(sizeof(BiTNode); /*生成结点空间 */T->data=ch;T->lchild=CreateBinTree(); /*构造二叉树的左子树 */T->rchild=CreateBinTree(); /*构造二叉树的右子树 */return T;void exchange(BiTree T)/* 交换左右子树，递归程序 */BiTree p; if(T=NULL)eturn; /* 结点空返回 */ p=T->lchild;T->lchild=T->rchild;T-

32、>rchild=p;exchange(T->lchild); exchange(T->rchild);void InOrderOut(BiTree T)/* 中序遍历输出二叉树 T 的结点值 */ BiTree p,q;if (T)printf("n%3c",T->data);p=T->lchild;q=T->rchild;if(p)printf("l: %3c",p->data);if(q)printf("r: %3c",q->data);InOrderOut(T->lchild

33、); /* 中序遍历二叉树的左子树 */ /* 访问结点的数据 */InOrderOut(T->rchild); /* 中序遍历二叉树的右子树 */void main() int n;BiTree bt;bt=CreateBinTree();InOrderOut(bt);exchange(bt);printf("nexchange n");InOrderOut(bt);5.6 一棵具有 n 个结点的完全二叉树采用顺序结构存储，试设计非递归算法对其进行先序遍历。#include "stdio.h"#include "alloc.h"

34、;#define MAXSIZE 200 /* 二叉树的最大结点数 */ typedef char elemtype;elemtype *s="0ABCDEFGHIJ"void NRPreOrder(elemtype *bt,int n)/* 非递归先序遍历二叉树 */int stackMAXSIZE,top,p,r,l; top=0;if (n=0) return;p=1;while(p<=n|top>=0)访问结点的数据域 */ 将当前指针 p 压栈 */ while(p<=n) printf(" %3c,",btp) ; /*if

35、 (top<MAXSIZE-1) /* stacktop=p; top+;else printf(" return ; p=2*p; /*栈溢出 ");指针指向 p 的左孩子 */栈空时结束 */ top-;p=stacktop; /*p=p*2+1; /*从栈中弹出栈顶元素 */ 指针指向 p 的右孩子结点 */if (top<=0) return; /* elsevoid main() int sum;printf("n");NRPreOrder(s,10);5.7 在二叉树中查找值为 x 的结点，试设计打印值为 x 的结点的所有祖先的结

36、点。 #include "stdio.h"#include "alloc.h"#define MAXSIZE 100typedef char elemtype;typedef struct BiTNodeelemtype data;struct BiTNode *lchild;*rchild; /* 左右孩子指针 */ BiTNode,*BiTree;elemtype *s="ABC00DE0G00F000"int sum=0;BiTree CreateBinTree()/* 以参加结点的先序序列输入，构造二叉链表 */BiTree

37、T; elemtype ch;if(*s='0') T=NULL;ch=*s;s+;if (ch='0') T=NULL; /* 读入 0 时，将相应结点置空 */ else T=(BiTNode *)malloc(sizeof(BiTNode); /* 生成结点空间 */T->data=ch;T->lchild=CreateBinTree(); /*构造二叉树的左子树 */T->rchild=CreateBinTree(); /*构造二叉树的右子树 */return T;T 的结点值 */void InOrderOut(BiTree T)/*

38、 中序遍历输出二叉树BiTree l,r;if (T)中序遍历二叉树的左子树 */中序遍历二叉树的右子树 */ printf("n%3c<- ",T->data); l=T->lchild;r=T->rchild; if(l!=NULL)printf("L:%3c ",l->data); if(r!=NULL)printf("R:%3c ",r->data); InOrderOut(T->lchild); /*/* 访问结点的数据 */InOrderOut(T->rchild); /*i

39、nt zhuxian(BiTree bt,char x)/* 非递归先序遍历二叉树 */BiTree stackMAXSIZE,p,q;int top,high=0,top2;if (bt=NULL) return; top=top2=0;p=bt;while(p!=NULL|top>0) while(p!=NULL)访问结点的数据域 */从栈中弹出栈顶元素 */将当前指针 p 压栈 */ q=p;if(p->data=x) /* printf("n %c<-",x);while(top>0)top-;p=stacktop; /* printf(&q

40、uot; %c <-",p->data); return 1; if(top<MAXSIZE-1) /* stacktop=p; top+; else printf("栈溢出 "); return ; p=p->lchild ; /* 指针指向 p 的左孩子 */ while(top>0&&(stacktop-1->rchild=NULL|stacktop-1->rchild=q)top-; p=stacktop;q=p;p=p->rchild;/* 从栈中弹出那些没有右孩子，或其右孩子已经查询过的元素，这样在 访问右孩子结点时，其父结点仍在栈中，便于查找其祖先 */ p=stacktop-1;p=p->rchild;/* 指针指向 p 的右孩子结点 */return 0;void main() int sum;BiTree bt; bt=CreateBinTree();InOrderOut(bt); sum=zhuxian