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. 设给定权值总数
3、有 n 个，其哈夫曼树的结点总数为( ) A不确定 B2n C2n+1 D2n-19二叉树的第 I 层上最多含有结点数为（ ）A2 I B 2 I-1-1 C 2 I-1 D2 I -110一棵二叉树高度为 h,所有结点的度或为 0，或为 2，则这棵二叉树最少有( )结点A2h B2h-1 C2h+1 Dh+1 11. 利用二叉链表存储树，则根结点的右指针是（ ） 。A指向最左孩子 B指向最右孩子 C空 D非空14在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）A都不相同 B完全相同 C先序和中序相同，而与后序不同 D中序和后序相同，而与先序不同 15在完全二叉树中，
4、若一个结点是叶结点，则它没（ ） 。A左子结点 B右子结点 C左子结点和右子结点 D左子结点，右子结点和兄弟结点16在下列情况中，可称为二叉树的是（ ）A每个结点至多有两棵子树的树 B. 哈夫曼树 C每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树 E以上答案都不对 17. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。A. 0 B. 1 C. 2 D. 不确定 18. 引入二叉线索树的目的是（ ）A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结果唯一19n 个结点的线索二叉树上含有的线索数
5、为（ ）A2n Bnl Cnl Dn 21下面几个符号串编码集合中，不是前缀编码的是（ ） 。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(2ilchild=NULL)countleaf(t-lchild,_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 nodeint data ; struct node
8、*lchild, *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 个结点的二叉树的所有不同形态。BAC EDF NPGH JM OLIK3分别给出下图所示二叉树的先根、中根和后根序列。4一个深度为 L 的
9、满 K 叉树有以下性质：第 L 层上的结点都是叶子结点，其余各层上每个结点都有 K 棵非空子树，如果按层次顺序从 1 开始对全部结点进行编号，求：1）各层的结点的数目是多少？ 2）编号为 n 的结点的双亲结点（若存在）的编号是多少？3）编号为 n 的结点的第 i 个孩子结点（若存在）的编号是多少？4）编号为 n 的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？请给出计算和推导过程。5将下列由三棵树组成的森林转换为二叉树。 （只要求给出转换结果）6设二叉树 BT 的存储结构如下:1 2 3 4 5 6 7 8 9 10Lchild 0 0 2 3 7 5 8 0 10 1Data J
10、H F D B A C E G IRchild 0 0 0 9 4 0 0 0 0 0其中 BT 为树根结点的指针，其值为 6,Lchild,Rchild 分别为结点的左、右孩子指针域,data 为结点的数据域。试完成下列各题:（l）画出二叉树 BT 的逻辑结构;（3）画出二叉树的后序线索树。五、算法设计题1要求二叉树按二叉链表形式存储，（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为 K，具有 N 个结点的二叉树的每个结点都与深度为 K 的满二叉树中编号从 1 至 N 的结点一一对应。此题以此定义为准。2设一棵二叉树的结点结构为 (L
11、LINK,INFO,RLINK),ROOT 为指向该二叉树根结点的指针，p 和 q 分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到 p 和 q 的最近共同祖先结点 r。3有一二叉链表，试编写按层次顺序遍历二叉树的算法。4已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。5对于二叉树的链接实现,完成非递归的中序遍历过程。6试写出复制一棵二叉树的算法。二叉树采用标准链接结构。 。7请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为 head。 二叉树按二叉链表方式存储，链接时用
12、叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。8已知二叉树以二叉链表存储，编写算法完成：对于树中每一个元素值为 x 的结点，删去以它为根的子树，并释放相应的空间。9设一棵二叉树的根结点指针为 T，C 为计数变量，初值为 0，试写出对此二叉树中结点计数的算法：BTLC（T，C） 。10分别写出算法，实现在中序线索二叉树 T 中查找给定结点*p 在中序序列中的前驱与后继。在先序线索二叉树 T 中，查找给定结点*p 在先序序列中的后继。在后序线索二叉树 T中，查找给定结点*p 在后序序列中的前驱。第六章 树和二叉树一、单项选择题1.A2.D3A4C5B6D7E 8. D9C10B1
13、1. C12A13D14B15C16B 17. B18. A19C20D21B22. D23C二、判断题（在各题后填写“”或“” ）1. 完全二叉树一定存在度为 1 的结点。2. 对于有 N 个结点的二叉树，其高度为 log2n。3. 二叉树的遍历只是为了在应用中找到一种线性次序。4. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。5. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。6中序遍历一棵二叉排序树的结点就可得到排好序的结点序列 7完全二叉树中，若一个结点没有左孩子，则它必是树叶。8. 二叉树只能用二叉链表表示。9. 给定一棵树，可以找到
14、唯一的一棵二叉树与之对应。10. 用链表(llink-rlink)存储包含 n 个结点的二叉树，结点的 2n 个指针区域中有 n-1 个空指针。11树形结构中元素之间存在一个对多个的关系。12将一棵树转成二叉树，根结点没有左子树。13度为二的树就是二叉树。14. 二叉树中序线索化后，不存在空指针域。15霍夫曼树的结点个数不能是偶数。16哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。三、填空题1p-lchild=null 中根序列：B C D A F E H J I G;后根序列：D C B F J I H G E A。4(1)k h-1(h 为层数)（2）因为该树每层上均有 K
15、h-1个结点，从根开始编号为 1，则结点 i 的从右向左数第个孩子的结点编号为 ki。设 n 为结点 i 的子女，则关系式(i-1)k+21)的前一结点编号为 n-1（其最右边子女编号是(n-1)*k+1） ，故结点 n的第 i 个孩子的编号是(n-1)*k+1+i。(4) 根据以上分析，结点 n 有右兄弟的条件是，它不是双亲的从右数的第一子女，即 (n-1)%k!=0，其右兄弟编号是 n+1。5.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:00
16、0，C:01，D:001五、算法设计题1题目分析二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。BiTree Creat() /建立二叉树的二叉链表形式的存储结构ElemType x；BiTree bt;scanf(“%d”, /本题假定结点数据域为整型if(x=0) bt=null;else if(x0)bt=(BiNode *)malloc(sizeof(BiNode);bt-data=x; bt-lchild=creat(); bt-rchild=creat(); HGDACJIBFEM
17、PONKOL1 359000111else error(“输入错误”)；return(bt);/结束 BiTreeint JudgeComplete(BiTree bt) /判断二叉树是否是完全二叉树,如是，返回 1，否则，返回 0int tag=0; BiTree p=bt, Q; / Q 是队列，元素是二叉树结点指针，容量足够大if(p=null) return (1);QueueInit(Q); QueueIn(Q,p); /初始化队列，根结点指针入队while (!QueueEmpty(Q)p=QueueOut(Q); /出队if (p-lchild /左子女入队else if (p-
18、lchild) return 0; /前边已有结点为空，本结点不空else tag=1; /首次出现结点为空if (p-rchild /右子女入队else if (p-rchild) return 0; else tag=1; /whilereturn 1; /JudgeComplete算法讨论完全二叉树证明还有其它方法。判断时易犯的错误是证明其左子树和右子数都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。2.题目分析后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找 p 和
19、 q 的最近共同祖先结点 r ,不失一般性，设 p 在 q 的左边。后序遍历必然先遍历到结点 p，栈中元素均为 p 的祖先。将栈拷入另一辅助栈中。再继续遍历到结点 q 时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点 p 和 q 的最近公共祖先。typedef structBiTree 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 stop.tag=0; bt=bt-lchild; /沿左分枝向下if(bt=p) /不失一般性，假定 p 在 q 的左侧,遇结点 p 时，栈中元素均为 p 的祖先结点for(i=1;i=top;i+) s1i=si; top1=top; /将栈 s 的元素转入辅助栈 s1 保存if(bt=q) /找到 q 结点。
