第5章树与二叉树习题参考答案

一、 单项选择题（每题2分，共26分）1) 树最适合用来表示（ C ）A ．有序数据元素 B.无序数据元素C. 元素之间具有分支层次关系的数据D.元素之间无联系的数据2) 如图所示的4棵二叉树中，（ C ）不是完全二叉树。

3) 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法（ B ）A. 正确B.错误4) 如图1-1所示二叉树的中序遍历序列是（ B ）。

A. abdgcefhB. dgbaechfC. gdbehfcaD. abcdefgh5) 如果是T2是由有序树T1转换而来的二叉树，那么T1中结点的先序就是T2中结点的（ A ）。

A. 先序B. 中序C. 后序D. 层次序6) 某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（ D ）。

A. 空或只有一个结点B. 完全二叉树C. 二叉排序树D. 高度等于其结点数7) 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。

这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。

结论（ A ）是正确的。

A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同。

B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同。

（a ） （b ） 9 （d ）C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同。

D. 以上都不对8) 如图所示的T2是由森林T1转换而来的二叉树，那么森里T1有（ C ）个叶子结点。

A. 4B. 5C. 6D. 79) 深度为5的二叉树至多有（ C ）个结点。

A. 16B. 32C. 31D. 1010) 在一非空二叉树的中序遍历序列中，根结点的右边（ A ）。

A. 只有右子树上的所有结点B. 只有右子树的部分结点C. 只有左子树上的部分结点D. 只有左子树上的所有结点11) 设n ，m 为一棵二叉树上的两个结点，在中序遍历时，n 在m 前的条件是（ C ）。

一、填空题1. 不相交的树的聚集称之为森林。

2. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_树可采用孩子-兄弟链表（二叉链表）做存储结构，目的是利用二叉树的已有算法解决树的有关问题。

3. 深度为k的完全二叉树至少有2 k-1个结点。

至多有2 k-1个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是2 k-2+1。

4. 在一棵二叉树中，度为零的结点的个数为n，度为2的结点的个数为n2，则有n= n2+1。

5. 一棵二叉树的第i（i≥1）层最多有2 i-1个结点；一棵有n（n>0）个结点的满二叉树共有（n+1）/2个叶子和（n-1） /2个非终端结点。

6.现有按中序遍历二叉树的结果为abc，问有5种不同形态的二叉树可以得到这一遍历结果。

7. 哈夫曼树是带权路径最小的二叉树。

8. 前缀编码是指任一个字符的编码都不是另一个字符编码的前缀的一种编码方法，是设计不等长编码的前提。

9. 以给定的数据集合{4，5，6，7，10，12，18}为结点权值构造的Huffman树的加权路径长度是 165 。

10. 树被定义为连通而不具有回路的（无向）图。

11. 若一棵根树的每个结点最多只有两个孩子，且孩子又有左、右之分，次序不能颠倒，则称此根树为二叉树。

12. 高度为k，且有个结点的二叉树称为二叉树。

2k-1 满13. 带权路径长度最小的二叉树称为最优二叉树，它又被称为树。

Huffman14. 在一棵根树中，树根是为零的结点，而为零的结点是结点。

入度出度树叶15. Huffman树中，结点的带权路径长度是指由到之间的路径长度与结点权值的乘积。

结点树根16. 满二叉树是指高度为k，且有个结点的二叉树。

二叉树的每一层i上，最多有个结点。

2k-12i-1二、单选题1. 具有10个叶结点的二叉树中有 (B) 个度为2的结点。

(A)8 (B)9 (C)10 (D)112．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_（3）次序的遍历实现编号。

第5章树和二叉树一、填空题1、指向结点前驱和后继的指针称为线索。

二、判断题1、二叉树是树的特殊形式。

（）2、完全二叉树中，若一个结点没有左孩子，则它必是叶子。

（）3、对于有N个结点的二叉树，其高度为。

（）4、满二叉树一定是完全二叉树，反之未必。

（）5、完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。

（）6、若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。

（）7、不使用递归也可实现二叉树的先序、中序和后序遍历。

（）8、先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。

（）9、赫夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

（）110、在赫夫曼编码中，出现频率相同的字符编码长度也一定相同。

（）三、单项选择题1、把一棵树转换为二叉树后，这棵二叉树的形态是（A）。

A．唯一的Ｂ．有多种C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。

2、由3个结点可以构造出多少种不同的二叉树？（D）A．2 B．3 C．4 D．5解释：五种情况如下：3、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（D）。

A．250 B． 500 C．254 D．501解释：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉树的性质可得B=0或1，又因为C为整数，所以B=0，C=500，A=501，即有501个叶子结点。

4、一个具有1025个结点的二叉树的高h为（C）。

A．11 B．10 C．11至1025之间 D．10至1024之间解释：若每层仅有一个结点，则树高h为1025；且其最小树高为⎣log21025⎦ + 1=11，即h在11至1025之间。

一、单选题1、已知一算术表达式的中缀形式为 A-B/C+D*E，前缀形式为+-A/BC*DE，其后缀形式为( )。

A.ABC/-DE*+B.AB/C-D*E+C. A-BC/DE*+D. ABCDE/-*+正确答案：A2、有关二叉树下列说法正确的是（）。

A.二叉树中任何一个结点的度都为2B.一棵二叉树的度可以小于2C.二叉树中每个结点的度都为2D.二叉树中至少有一个结点的度为2正确答案：B3、在一棵高度为k的满二叉树中，结点总数为（）。

A.2k-1B. 2k-1C. 2k-1+1D.2k正确答案：B4、某二叉树中有60个叶子结点，则该二叉树中度为2的结点个数为（）。

A.不确定B.60C.59D.61正确答案：C解析：任意二叉树中，n0=n2+15、高度为7的完全二叉树，最少有（）个结点。

A.127B.128C.63D.64正确答案：D解析：前6层都是满的，最后一层（第7层）近1个结点。

可保证题目条件。

6、高度为7的二叉树，最少有（）个结点。

A.7B.127C.13D.64正确答案：A解析：每层只有1个结点。

共7个即可构成一个高度为7的二叉树。

7、对任意一棵有n个结点的树，这n个结点的度之和为( )。

A.n-1B.2*nC.n+2D.n正确答案：A解析：所有结点的度之和为分支个数，分支个数即为结点个数-18、在下列存储形式中，（）不是树的存储形式。

A.双亲表示法B.孩子-兄弟表示法C.孩子链表表示法D.顺序存储表示法正确答案：D9、对二叉树中的结点进行编号，要求根结点的编号最小，左孩子结点编号比右孩子结点编号小。

则应该采用（）遍历方法对其进行编号。

A.层次B.先序C.后序D.中序正确答案：B10、某二叉树中有60个叶子结点，则该二叉树中度为2的结点个数为（）。

A. 59B.61C.60D.不一定正确答案：A11、树的后根遍历，相当于对应二叉树的（）遍历。

A.中序B.后序C.层次D.先序正确答案：A二、判断题1、完全二叉树一定存在度为1的结点。

第5章树和⼆叉树习题答案第6章树和⼆叉树⼀．选择题（1）由3 个结点可以构造出多少种不同的⼆叉树？（ D ）A．2 B．3 C．4 D．5（2）⼀棵完全⼆叉树上有1001个结点，其中叶⼦结点的个数是（D ）。

A．250 B． 500 C．254 D．501（3）⼀个具有1025个结点的⼆叉树的⾼h为（ C ）。

A．11 B．10 C．11⾄1025之间 D．10⾄1024之间（4）深度为h的满m叉树的第k层有（ A ）个结点。

(1=A．mk-1 B．mk-1 C．mh-1 D．mh-1（5）对⼆叉树的结点从1开始进⾏连续编号，要求每个结点的编号⼤于其左、右孩⼦的编号，同⼀结点的左右孩⼦中，其左孩⼦的编号⼩于其右孩⼦的编号，可采⽤（ C ）遍历实现编号。

A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历（6）若⼆叉树采⽤⼆叉链表存储结构，要交换其所有分⽀结点左、右⼦树的位置，利⽤（ D ）遍历⽅法最合适。

A．前序 B．中序 C．后序 D．按层次（7）⼀棵⾮空的⼆叉树的先序遍历序列与后序遍历序列正好相反，则该⼆叉树⼀定满⾜（ B ）。

A．所有的结点均⽆左孩⼦ B．所有的结点均⽆右孩⼦C．只有⼀个叶⼦结点 D．是任意⼀棵⼆叉树（8）某⼆叉树的前序序列和后序序列正好相反，则该⼆叉树⼀定是（ C ）的⼆叉树。

A．空或只有⼀个结点 B．任⼀结点⽆左⼦树C．⾼度等于其结点数 D．任⼀结点⽆右⼦树（9）若X是⼆叉中序线索树中⼀个有左孩⼦的结点，且X不为根，则X的前驱为（ C ）。

A．X的双亲 B．X的右⼦树中最左的结点C．X的左⼦树中最右结点 D．X的左⼦树中最右叶结点（10）引⼊⼆叉线索树的⽬的是（ A ）。

A．加快查找结点的前驱或后继的速度 B．为了能在⼆叉树中⽅便的进⾏插⼊与删除C．为了能⽅便的找到双亲 D．使⼆叉树的遍历结果唯⼀⼆．简答题（1）试找出满⾜下列条件的⼆叉树①先序序列与后序序列相同②中序序列与后序序列相同③先序序列与中序序列相同④中序序列与层次遍历序列相同答：（1）若先序序列与后序序列相同，则或为空树，或为只有根结点的⼆叉树（２）若中序序列与后序序列相同，则或为空树，或为任⼀结点⾄多只有左⼦树的⼆叉树．（３）若先序序列与中序序列相同，则或为空树，或为任⼀结点⾄多只有右⼦树的⼆叉树．（４）若中序序列与层次遍历序列相同，则或为空树，或为任⼀结点⾄多只有右⼦树的⼆叉树2. 试写出如图所⽰的⼆叉树分别按先序、中序、后序遍历时得到的结点序列。

第5章树和二叉树一、单项选择题1.以下说法错误的是（B ）。

A. 存在这样的二叉树，对其采用任何次序的遍历其结点访问序列均相同B. 二叉树是树的特殊情形C. 满二叉树中所有叶结点都在同一层上D. 在二叉树只有一棵子树的情况下，也要指出是左子树还是右子树2.树最适合用来表示( C)。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据3.下列叙述正确的是（C ）。

A. 二叉树是度为2的有序树B. 完全二叉树一定存在度为1的结点C. 深度为k的二叉树中结点总数≤2k-1D. 对于有n个结点的二叉树，其高度为⎣log2n⎦+14.按照二叉树的定义，具有三个节点的二叉树有( C )种。

A.3B.4C.5D.65.下列叙述中正确的是（C ）。

A. 二叉树是度为2的有序树B. 二叉树中的结点只有一个孩子时无左右之分C. 二叉树中每个结点最多只有两棵子树，并且有左右之分D. 二叉树若存在两个结点，则必有一个为根，另一个为左孩子6.设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（ C ）。

A.N0=N1+1 B.N=Nl+N2C.N=N2+1 D.N=2N1+17.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ B ）。

A. 2i+1B.2iC.i/2D.2i-18.有100个结点的完全二叉树由根开始从上到下从左到右对结点进行编号，根结点的编号为1，编号为46的结点的右孩子的编号为（ C ）A．50 B．92 C．93 D．869.若一棵有n个结点的树，则该树中的度之和为（C ）。

A. n+1B. nC. n-1D. 不确定10.已知完全二叉树有90个结点，则整个二叉树有（ B ）个度为1的结点。

A 0B 1C 2D 不确定11.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（C ）。

习题五树与二叉树一、选择题1、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足。

A、所有的结点均无左孩子B、所有的结点均无右孩子C、只有一个叶子结点D、是任意一棵二叉树2、一棵完全二叉树上有1001个结点，其中叶子结点的个数是。

A、250B、500C、254D、505E、以上答案都不对3、以下说法正确的是。

A、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点B、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点C、在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点D、在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点4、以下说法错误的是。

A、哈夫曼树是带权路径长度最短得数，路径上权值较大的结点离根较近B、若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历序列中的第一个结点C、已知二叉树的前序遍历和后序遍历并不能唯一地确定这棵树,因为不知道树的根结点是哪一个D、在前序遍历二叉树的序列中,任何结点其子树的所有结点都是直接跟在该结点之后的5、一棵有124个叶结点的完全二叉树，最多有个结点。

A、247B、248C、249D、250E、2516、任何一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次序。

A、不发生变化B、发生变化C、不能确定7、设a、b为一棵二叉树上的两个结点。

在中序遍历时，a在b前面的条件是。

A、a在b的右方B、a在b的左方C、a是b的祖先D、a 是b的子孙8、设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为。

A、不确定B、2kC、2k-1D、2k+19、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有个结点。

A、13B、12C、26 D、2510、下面几个符号串编码集合中，不是前缀编码的是。

习题五参考答案一、选择题1．对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行（ B ）遍历操作相同。

A．先根 B. 中根 C. 后根 D. 层次2．在哈夫曼树中，任何一个结点它的度都是（ C ）。

B．0或1 B. 1或2 C. 0或2 D. 0或1或23．对一棵深度为h的二叉树，其结点的个数最多为（ D ）。

A．2h B. 2h-1 C. 2h-1 D. 2h-14．一棵非空二叉树的先根遍历与中根遍历正好相同，则该二叉树满足（ A ）A．所有结点无左孩子 B. 所有结点无右孩子C. 只有一个根结点D. 任意一棵二叉树5．一棵非空二叉树的先根遍历与中根遍历正好相反，则该二叉树满足（ B ）B．所有结点无左孩子 B. 所有结点无右孩子C. 只有一个根结点D. 任意一棵二叉树6．假设一棵二叉树中度为1的结点个数为5，度为2的结点个数为3，则这棵二叉树的叶结点的个数是（ C ）A．2 B. 3 C. 4 D. 57．若某棵二叉树的先根遍历序列为ABCDEF，中根遍历序列为CBDAEF，则这棵二叉树的后根遍历序列为（ B ）。

A．FEDCBA B. CDBFEA C. CDBEFA D. DCBEFA8．若某棵二叉树的后根遍历序列为DBEFCA，中根遍历序列为DBAECF，则这棵二叉树的先根遍历序列为（ B ）。

A．ABCDEF B. ABDCEF C. ABCDFE D. ABDECF9．根据以权值为{2，5，7，9，12}构造的哈夫曼树所构造的哈夫曼编码中最大的长度为（ B ）A．2 B. 3 C. 4 D. 510．在有n个结点的二叉树的二叉链表存储结构中有（ C ）个空的指针域。

A．n-1 B. n C. n+1 D. 0二、填空题1.在一棵度为m的树中，若度为1的结点有n1个，度为2的结点有n2个，……，度为m的结点有n m个，则这棵树中的叶结点的个数为1+n2+2n3+3n4+…+(m-1)n m。

page: 1The Home of jetmambo - 第 5 章树和二叉树第 5 章树和二叉树(1970-01-01) -第 5 章树和二叉树课后习题讲解1. 填空题⑴树是n（n≥0）结点的有限集合，在一棵非空树中，有（）个根结点，其余的结点分成m （m＞0）个（）的集合，每个集合都是根结点的子树。

【解答】有且仅有一个，互不相交⑵树中某结点的子树的个数称为该结点的（），子树的根结点称为该结点的（），该结点称为其子树根结点的（）。

【解答】度，孩子，双亲⑶一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。

【解答】2i-1，(n+1)/2，(n-1)/2【分析】设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。

⑷设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。

【解答】2h -1，2h-1【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。

⑸深度为k的二叉树中，所含叶子的个数最多为（）。

【解答】2k-1【分析】在满二叉树中叶子结点的个数达到最多。

⑹具有100个结点的完全二叉树的叶子结点数为（）。

【解答】50【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。

⑺已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。

则该树中有（）个叶子结点。

【解答】12【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。

⑻某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（）。

第五章 树(答案)一、选择题1、二叉树的第i 层最多有（ ）个结点。

A ．2i B. 2i C. 2i-1 D.2i -12.对于一棵满二叉树，高度为h ，共有n 个结点，其中有m 个叶子结点，则（ ）A ．n=h+m B.h+m=2n C.m=h-1 D.n=2h -1 3.在一棵二叉树中，共有16个度为2的结点，则其共有（ ）个叶子结点。

A ．15 B.16 C.17 D.184. 一棵完全二叉树中根结点的编号为1，而且编号为23的结点有左孩子但没有右孩子，则此树中共有（ ）个结点。

A ．24 B.45 C.46 D.47 5.下述编码那一组不是前缀码（ ）A ．00,01,10,11 B.0,1,00,11 C.0,10,110,111 D.1,01,001,000 6.某二叉树的中序序列和后序序列相同，则这棵二叉树必然是（ ）A ．空树B ．空树或任一结点均无左孩子的非空二叉树C ．空树或任一结点均无右孩子的非空二叉树D ．空树或仅有一个结点的二叉树7.设n,m 为一棵二叉树上的两个结点，在中序遍历时，n 在m 前的条件是（ ）A ．n 在m 的右边 B.n 是m 的祖先C ．n 在m 的左边 D.n 是m 的子孙8、假定中根遍历二叉树的定义如下：若二叉树为非空二叉树，则中根遍历根的右子树；访问根结点；中根遍历根的左子树。

按此定义遍历下图所示的二叉树，遍历的结果为： A 、 DBEAFHGC A B 、 C GHFADBE B C C 、 E BDAFHGC E D FD 、 FHGCADBE GH9、文中出现的字母为A 、B 、C 、D 和E ，每个字母在电文中出现的次数分别为9、27、3、5和11。

按哈夫曼编码（构造时左小右大），则字母C 的编码应是：A 、10B 、0110C 、1110D 、1100 10、设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）A ．5B ．6C ．7D ．8 11．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ ）A ．ab+cde/*B ．abcde/+*+C ．abcde/*++D ．12. 设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（ ）A. A*B+C/(D*E)+(F-G)B. (A*B+C)/(D*E)+(F-G)C. (A*B+C)/(D*E+（F-G ）)D. A*B+C/D*E+F-G13．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( ) A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE14．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A ．9B ．11C ．15D ．不确定15．树的后根遍历序列等同于该树对应的二叉树的( ).A. 先序序列B. 中序序列C. 后序序列16．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。

第五部分 树、选择题1．高度为 h(h>0) 的二叉树最少有 ( A ) 个结点-1 C2．树型结构最适合用来描述 ( C )A. 有序的数据元素B.C.数据元素之间的具有层次关系的数据 3．有 n(n>0) 个结点的完全二叉树的深度是A.log 2(n)B. log 2(n)+14. ( B ) 又是一 棵满二叉树。

A. 二叉排序树C. 有 15 个结点的二叉树D.哈夫曼 (Huffman) 树5. 深度为 k 的满二叉树有 ( B ) 个分支结点。

-1 C +16. 若已知一棵二叉树先序序列为 ABCDEF ，G 中序序列为 CBDAEG ，F 则其后序序列为 ( A )A CDBGFEAB CDBFGEAC CDBAGFED BCDAGFE7. 二叉树第 i(i>=1) 层上至多有 ( C ) 结点。

A 、２ i b 、２ic 、２i－１d 、２ －１8. 在一棵具有5 层的满二叉树中结点总数为 (A ）。

A. 31B. 32C. 33D. 169. 一个二叉树按顺序方式存储在一个维数组中，如图0 1 2 3 4 5 6 7 8 9 10 11 12 1314A B C D E F G H I J则结点 E 在二叉树的第 ( C ) 层。

10．一棵度为 3 的树中，度为 3 的结点个数为 2，度为 2 的结点个数为 1，则度为 0 的结点无序的数据元素D. 数据元素之间没有关系的数据( D ) 。

C.log 2(n+1)D.log 2(n)+1B.深度为 5 有31 个结点的二叉树A 、1B 、2C 、3D 、4个数为( C )D ．711. 在一棵二叉树上第 5 层的结点数最多是 ( B )A 8B 16C 32D 1512. 设一棵完全二叉树共有 699 个结点，则在该二叉树中的叶子结点数为 ( B ) 。

A. 349B. 350C. 255D. 35113. 有 n(n>0) 个结点的完全二叉树的深度是 ( D ) 。

练习及参考答案一选择题：A．二叉树中任何一个结点的度都为2.＿B.二叉树的度为2C.一棵二叉树的度可小于2D.任何一棵二叉树中至少有一个结点的度为22.以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n＞0），空链域的个数为（:C )。

A. 2n-1B. n-1C. n+1D. 2n+13.线索化二叉树中，某结点*p没有孩子的充要条件是（B)。

A. p->lchild=NULLB. p->ltag二1且p->rtag=1C. p -> ltag=0D. p->lchild=NULL且p->ltag=14.如果结点A有3个兄弟，而且B是A的双亲，则B的度是（B)。

A. 3B. 4C. 5D. 15.某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1,2，…，n，且有如下性质：T中任意结点v，其编号等于左子树上的最小编号减1，而v的右子树的结点中，其最小编号等于v左子树上结点的最大编号加1。

这是按（B)编号的。

A.中序遍历序列B.先序遍历序列．C.后序遍历序列D.层次顺序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，N2和N3。

与森林F 对应的二叉树根结点的右子树上的结点个数是（D)。

A. N1B. N1＋N2C. N2D. N2＋N39.任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序（A)。

A.不发生改变B发生改变 C.不能确定D:以上都不对10.若一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，则先序遍历序列为（D)。

A. cbedB. decabC. deabcD. cedba11.若一棵二叉树的先序遍历序列为abdgcefh;中序遍历的序列为dgbaechf,则后序遍霎历的结果为（D）。

第5章树【例5-1】写出如图5-1所示的树的叶子结点、非终端结点、每个结点的度及树深度。

AB C D EF G H I J图5-1解：（1）叶子结点有：B、D、F、G、H、I、J。

（2）非终端结点有：A、C、E。

（3）每个结点的度分别是：A的度为4，C的度为2，E的度为3，其余结点的度为0。

（4）树的深度为3。

【例5-2】一棵度为2的树与一棵二叉树有什么区别？解：度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能交换。

【例5-3】树与二叉树有什么区别？解：区别有两点：（1）二叉树的一个结点至多有两个子树，树则不然；（2）二叉树的一个结点的子树有左右之分，而树的子树没有次序。

【例5-4】分别画出具有3个结点的树和三个结点的二叉树的所有不同形态。

解：如图5-2(a)所示，具有3个结点的树有两种不同形态。

图5-2(a)如图5-2(B)所示，具有3个结点的二叉树有以下五种不同形态。

图5-2(b)【例5-5】如图5-3所示的二叉树，试分别写出它的顺序表示和链接表示（二叉链表）。

解：（1）顺序表示。

（2）该二叉树的二叉链表表示如图5-4所示。

【例5-6】试找出满足下列条件的所有二叉树：（1）先序序列和中序序列相同； （2）中序序列和后序序列相同； （3）先序序列和后序序列相同。

解：（1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树；（2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树；（3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。

【例5-7】如图5-5所示的二叉树，要求：（1）写出按先序、中序、后序遍历得到的结点序列。

（2）画出该二叉树的后序线索二叉树。

解： （1） 先序遍历序列：ABDEFC 中序遍历序列：DEFBAC 后序遍历序列：FEDBCA （2）其后序线索二叉树如图5-6所示。