1、习题六 树和二叉树一、单项选择题1 以下说法错误的是 ( )A树形结构的特点是一个结点可以有多个直接前趋B线性结构中的一个结点至多只有一个直接后继C树形结构可以表达(组织)更复杂的数据D树(及一切树形结构)是一种分支层次结构E任何只含一个结点的集合是一棵树2下列说法中正确的是 ( )A任何一棵二叉树中至少有一个结点的度为2B任何一棵二叉树中每个结点的度都为2C任何一棵二叉树中的度肯定等于2D任何一棵二叉树中的度可以小于23讨论树、森林和二叉树的关系，目的是为了（ ）A借助二叉树上的运算方法去实现对树的一些运算B将树、森林按二叉树的存储方式进行存储C将树、森林转换成二叉树D体现一种技巧，没有什么
2、实际意义4树最适合用来表示 ( )A有序数据元素 B无序数据元素C元素之间具有分支层次关系的数据 D元素之间无联系的数据5若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A9 B11 C15 D不确定 6设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。AM1 BM1+M2 CM3 DM2+M37一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）A 250 B 500 C254 D505 E以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A不确定
3、 B2n C2n+1 D2n-19二叉树的第I层上最多含有结点数为（ ）A2I B 2I-1-1 C 2I-1 D2I -110一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A2h B2h-1 C2h+1 Dh+1 11. 利用二叉链表存储树，则根结点的右指针是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空14在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）A都不相同 B完全相同 C先序和中序相同，而与后序不同 D中序和后序相同，而与先序不同 15在完全二叉树中，若一个结点是叶结点，则它没（ ）。A左子结点 B右子结点 C左子结点和
4、右子结点 D左子结点，右子结点和兄弟结点16在下列情况中，可称为二叉树的是（ ）A每个结点至多有两棵子树的树 B. 哈夫曼树 C每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树 E以上答案都不对 17. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。A. 0 B. 1 C. 2 D. 不确定 18. 引入二叉线索树的目的是（ ）A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结果唯一19n个结点的线索二叉树上含有的线索数为（ ）A2n Bnl Cnl Dn 21下面几个符号串编码集合中，不是前
5、缀编码的是（ ）。A0,10,110,1111 B11,10,001,101,0001 C00,010,0110,1000 Db,c,aa,ac,aba,abb,abc 22. 一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A1.n中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（ ）AA2i(2i=n) BA2i+1(2i+1lchild=NULL)&(t-rchild=NULL)_; countleaf(t-lchild,&count); _ 13以下程序是二叉链表树中序遍历的非递归算法，请填空使之完善。二叉树链表的结点类型的定义如下
6、： typedef struct node /*C语言/ char data; struct node *lchild,*rchild;*bitree;void vst(bitree bt) /*bt为根结点的指针*/ bitree p; p=bt; initstack(s); /*初始化栈s为空栈*/while(p | !empty(s) /*栈s不为空*/ if(p) push (s,p); (1)_ ; /*P入栈*/else p=pop(s); printf(“%c”,p-data);(2)_ _; /*栈顶元素出栈*/ 14二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填
7、空完善之。 int depth(bitree bt) /*bt为根结点的指针*/int hl,hr; if (bt=NULL) return(1)_ _); hl=depth(bt-lchild); hr=depth(bt-rchild); if(2)_ _) (3)_ _； return(hr+1); 15将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。typedef struct node int data ; struct node *lchild
8、, *rchild; btnode; void EXCHANGE(btnode *bt)btnode *p, *q; if (bt)ADDQ(Q,bt); while(!EMPTY(Q) p=DELQ(Q); q=(1)_ _; p-rchild=(2)_ _; (3)_ _=q;if(p-lchild) (4)_ _; if(p-rchild) (5)_ _; /四、应用题1树和二叉树之间有什么样的区别与联系？2分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。3分别给出下图所示二叉树的先根、中根和后根序列。4一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每
9、个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：1）各层的结点的数目是多少？ 2）编号为n的结点的双亲结点（若存在）的编号是多少？3）编号为n的结点的第i 个孩子结点（若存在）的编号是多少？4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？请给出计算和推导过程。5将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）NPGHJMOLIKEDFBAC6设二叉树BT的存储结构如下: 1 2 3 4 5 6 7 8 9 10Lchild 0 0 2 3 7 5 8 0 10 1DataJ H F D B A C E G IRchild 0 0 0 9
10、4 0 0 0 0 0其中BT为树根结点的指针，其值为6,Lchild,Rchild分别为结点的左、右孩子指针域,data为结点的数据域。试完成下列各题:（l）画出二叉树BT的逻辑结构;（3）画出二叉树的后序线索树。五、算法设计题1要求二叉树按二叉链表形式存储，（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。2设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中
11、任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。3有一二叉链表，试编写按层次顺序遍历二叉树的算法。4已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。5对于二叉树的链接实现,完成非递归的中序遍历过程。6试写出复制一棵二叉树的算法。二叉树采用标准链接结构。7请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。8已知二叉树以二叉链表存储，编写算法完成：对于树中每一个
12、元素值为x的结点，删去以它为根的子树，并释放相应的空间。9设一棵二叉树的根结点指针为T，C为计数变量，初值为0，试写出对此二叉树中结点计数的算法：BTLC（T，C）。10分别写出算法，实现在中序线索二叉树T中查找给定结点*p在中序序列中的前驱与后继。在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。第六章 树和二叉树一、单项选择题1.A2.D3A4C5B6D7E 8. D9C10B11. C12A13D14B15C16B 17. B18. A19C20D21B22. D23C二、判断题（在各题后填写“”或“”）1. 完全二叉树一
13、定存在度为1的结点。2. 对于有N个结点的二叉树，其高度为log2n。3. 二叉树的遍历只是为了在应用中找到一种线性次序。4. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。5. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。6中序遍历一棵二叉排序树的结点就可得到排好序的结点序列 7完全二叉树中，若一个结点没有左孩子，则它必是树叶。8. 二叉树只能用二叉链表表示。9. 给定一棵树，可以找到唯一的一棵二叉树与之对应。10. 用链表(llink-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。11树形结构中元素之间存在一
14、个对多个的关系。12将一棵树转成二叉树，根结点没有左子树。13度为二的树就是二叉树。14. 二叉树中序线索化后，不存在空指针域。15霍夫曼树的结点个数不能是偶数。16哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。三、填空题1p-lchild=null & p-rchlid=null 2.(1)2k-1 (2)2k-13644. 2n n-1 n+1 5 先序遍历 后序遍历 中序遍历 6.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) log2i+1748任何结点至多只有右子女的二叉树。9二叉排序树10前序116912 *coun
15、t+, countleaf(l-rchile,count)13(1) p=p-lchild / 沿左子树向下 （2）p=p-rchild 14(1)0 （2）hlhr (3)hr=hl15(1)p-rchild (2)p-lchild (3)p-lchild (4)ADDQ(Q,p-lchild) (5)ADDQ(Q,p-rchild)四、应用题1树和二叉树逻辑上都是树形结构，树和二叉树的区别有三：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下， 也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。二叉树
16、不是树的特例。2【解答】具有3个结点的树 具有3个结点的二叉树3解答：先根序列：A B C D E F G H I J;中根序列：B C D A F E H J I G;后根序列：D C B F J I H G E A。4(1)kh-1(h为层数)（2）因为该树每层上均有Kh-1个结点，从根开始编号为1，则结点i的从右向左数第个孩子的结点编号为ki。设n 为结点i的子女，则关系式(i-1)k+2=n1)的前一结点编号为n-1（其最右边子女编号是(n-1)*k+1），故结点 n的第 i个孩子的编号是(n-1)*k+1+i。(4) 根据以上分析，结点n有右兄弟的条件是，它不是双亲的从右数的第一子女
17、，即 (n-1)%k!=0，其右兄弟编号是n+1。HGDACJIBFEMPONKOL5.6（l）图略；（2）前序序列：J 中序序列： E C B H F D J I G A 后序序列： （3）图略。7字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下A:1，B:000，C:01，D:0011359000111五、算法设计题1题目分析二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。BiTree Creat() /建立二叉树的二叉链表形式的存储结构ElemType x；BiTree b
18、t;scanf(“%d”,&x); /本题假定结点数据域为整型if(x=0) bt=null;else if(x0) bt=(BiNode *)malloc(sizeof(BiNode);bt-data=x; bt-lchild=creat(); bt-rchild=creat(); else error(“输入错误”)；return(bt);/结束 BiTreeint JudgeComplete(BiTree bt) /判断二叉树是否是完全二叉树,如是，返回1，否则，返回0int tag=0; BiTree p=bt, Q; / Q是队列，元素是二叉树结点指针，容量足够大if(p=null)
19、 return (1);QueueInit(Q); QueueIn(Q,p); /初始化队列，根结点指针入队while (!QueueEmpty(Q)p=QueueOut(Q); /出队 if (p-lchild & !tag) QueueIn(Q,p-lchild); /左子女入队 else if (p-lchild) return 0; /前边已有结点为空，本结点不空 else tag=1; /首次出现结点为空 if (p-rchild & !tag) QueueIn(Q,p-rchild); /右子女入队 else if (p-rchild) return 0; else tag=1;
20、/whilereturn 1; /JudgeComplete算法讨论完全二叉树证明还有其它方法。判断时易犯的错误是证明其左子树和右子数都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。2.题目分析后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和
21、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 |top0)while(bt!=null & bt!=p & bt!=q) /结点入栈s+top.t=bt; stop.tag=0; bt=bt-lchild; /沿左分枝向下if(bt=p) /不失一般性，假定p在q的
22、左侧,遇结点p时，栈中元素均为p的祖先结点for(i=1;i0;i-)/；将栈中元素的树结点到s1去匹配pp=si.t;for (j=top1;j0;j-)if(s1j.t=pp) printf(“p 和q的最近共同的祖先已找到”)；return (pp);while(top!=0 & stop.tag=1) top-; /退栈if (top!=0)stop.tag=1;bt=stop.t-rchild; /沿右分枝向下遍历/结束while(bt!=null |top0)return(null);/、p无公共祖先/结束Ancestor3解答：本算法要借用队列来完成，其基本思想是，只要队列不为空
23、，就出队列，然后判断该结点是否有左孩子和右孩子，如有就依次输出左、右孩子的值，然后让左、右孩子进队列。void layorder (bitreptr T) initqueue (q) /*队列初始化*/ if(T!=NULL) printf(“%f”, T-data); enqueue (q, T); /*入队列*/ while (not emptyqueue (q) ) /*若队列非空*/ outqueue (q, p) ; /*出队*/ if (p-lchild!=NULL) printf(“%f”, p-lchild-data); enqueue (q, p-lchild); /*入队列
24、*/ if (p-rchild!=NULL) printf(“%”, p-rchild-data); enqueue (q, p-rchild); /*入队列*/ 4【解答】Void PreOrder(BiTree root) /*先序遍历二叉树的非递归算法*/ InitStack(&S); p=root; while(p!=NULL | !IsEmpty(S) ) if(p!=NULL) Visit(p-data);push(&S,p);p=p-Lchild; else Pop(&S,&p); p=p-RChild;5void InOrder(BiTree bt) BiTree s,p=bt
25、; /s是元素为二叉树结点指针的栈，容量足够大int top=0;while(p | top0) while(p) s+top=p; bt=p-lchild; /中序遍历左子树 if(top0)p=stop-; printf(p-data); p=p-rchild; /退栈，访问，转右子树 6BiTree Copy(BiTree t)/复制二叉树tBiTree bt; if (t=null) bt=null; elsebt=(BiTree)malloc(sizeof(BiNode); bt-data=t-data;bt-lchild=Copy(t-lchild);bt-rchild=Copy(
26、t-rchild); return(bt); /结束Copy7.题目分析叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。LinkedList head,pre=null; /全局变量LinkedList InOrder(BiTree bt)/中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head if(bt)InOrder(bt-lchild); /中序遍历左子树 if(bt-lchild=null & bt-rchil
27、d=null) /叶子结点 if(pre=null) head=bt; pre=bt; /处理第一个叶子结点 elsepre-rchild=bt; pre=bt; /将叶子结点链入链表 InOrder(bt-rchild); /中序遍历左子树 pre-rchild=null; /设置链表尾 return(head); /InOrder时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)8.题目分析 删除以元素值x为根的子树，只要能删除其左右子树，就可以释放值为x的根结点，因此宜采用后序遍历。删除值为x结点，意味着应将其父结点的左(右)子女指针置空，用层次遍历易于找到某结点的
28、父结点。本题要求删除树中每一个元素值为 x的结点的子树，因此要遍历完整棵二叉树。void DeleteXTree(BiTree bt) /删除以bt为根的子树 DeleteXTree(bt-lchild); DeleteXTree(bt-rchild);/删除bt的左子树、右子树 free(bt); / DeleteXTree /释放被删结点所占的存储空间void Search(B:Tree bt,ElemType x)/在二叉树上查找所有以x为元素值的结点，并删除以其为根的子树BiTree Q;/Q是存放二叉树结点指针的队列，容量足够大 if(bt) if(bt-data=x) Delete
29、XTree(bt); exit(0);/若根结点的值为x，则删除整棵树 QueueInit(Q); QueueIn(Q,bt); while(!QueueEmpty(Q)p=QueueOut(Q);if(p-lchild) / 若左子女非空 if(p-lchild-data=x) /左子女结点值为 x,应删除当前结点的左子树 DeleteXTree(p-lchild); p-lchild=null; /父结点的左子女置空else Enqueue (Q,p-lchild);/ 左子女入队列if(p-rchild) / 若右子女非空 if(p-rchild-data=x) /右子女结点值为 x,应
30、删除当前结点的右子树 DeleteXTree(p-rchild); p-rchild=null; /父结点的右子女置空else Enqueue (Q,p-rchild);/ 右子女入队列 /while /if(bt) /search9int BTLC(BiTree T,int *c)/对二叉树T的结点计数if(T) *c+;BTLC(T-lchild,&c); /统计左子树结点 BTLC(T-rchild,&c); /统计右子树结点 /结束Count,调用时*c=010（1）找结点的中序前驱结点BiTNode *InPre (BiTNode *p)/*在中序线索二叉树中查找p的中序前驱结点，并
31、用pre指针返回结果*/ if (p-Ltag= =1) pre = p-LChild; /*直接利用线索*/ else /*在p的左子树中查找“最右下端”结点*/ for ( q=p-LChild; q-Rtag= =0; q=q-RChild); pre = q; return (pre); （2）找结点的中序后继结点BiTNode *InSucc (BiTNode *p)/*在中序线索二叉树中查找p的中序后继结点，并用succ指针返回结果*/ if (p-Rtag= =1) succ = p-RChild; /*直接利用线索*/ else /*在p的右子树中查找“最左下端”结点*/ fo
32、r ( q=p-RChild; q-Ltag= =0; q=q-LChild); succ= q; return (succ); (3) 找结点的先序后继结点BiTNode *PreSucc (BiTNode *p)/*在先序线索二叉树中查找p的先序后继结点，并用succ指针返回结果*/ if (p-Ltag= =0) succ = p-LChild; else succ= p-RChild; return (succ); (4) 找结点的后序前驱结点BiTNode *SuccPre (BiTNode *p)/*在后序线索二叉树中查找p的后序前驱结点，并用pre指针返回结果*/ if (p-Ltag= =1) pre = p-LChild; else pre= p-RChild; return (pre);
