树和二叉树(习题及作业2)

一、判断题（√）1.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

（×）2.二叉树中每个结点的两棵子树的高度差等于1。

（√）3.二叉树中每个结点的两棵子树是有序的。

（×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。

（×）5.二叉树中所有结点个数是2k-1-1，其中k是树的深度。

（应2i-1）（×）6.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

（×）7.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。

（应2i-1）（√）（√）( )10( )11( )12（√）(√)14(√)15(╳)16（√）（√）（√）（╳）12.345.1答：20所以有1个非空左子树。

完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.6.一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为2。

7.若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是FEGHDCB。

8.在二叉树中，指针p所指结点为叶子结点的条件是_p->lchild==null&&p->rchlid==null?。

三、选择题1．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为（C）A）3 B）2 C）4D）52．二叉树是非线性数据结构，所以（C）。

Ａ、它不能用顺序存储结构存储;Ｂ、它不能用链式存储结构存储;Ｃ、顺序存储结构和链式存储结构都能存储;Ｄ、顺序存储结构和链式存储结构都不能使用3.具有n(n>0)个结点的完全二叉树的深度为（C）。

(Ａ)?log2(n)?(Ｂ)?log2(n)?(Ｃ)?log2(n)?+1(Ｄ)?log2(n)+1?4．把一棵树转换为二叉树后，这棵二叉树的形态是（A）。

习题五树与二叉树一、选择题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、26D、2510、下面几个符号串编码集合中，不是前缀编码的是。

第五章树和二叉树一．选择题1．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（）A．4个B．5个C．6个D．7个2．某二叉树结点的中序序列为a、b、c、d、e、f、g，后序序列为b、d、c、a、f、g、e，则其左子树中结点数目为（）A．3 B．2 C．4 D．53．设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。

与森林F对应的二叉树根结点的左子树上的结点个数是（）A．M1 B．M1+M2 C．M3 D．M2+M34。

对于一棵具有n个结点、度为4的树来说，（）A．树的高度至多是n-3 B．树的高度至多是n-3C．第i 层上至多有4*(i-1)个结点D．至少在某一层上正好有4个结点5．在下列存储结构中，（）不是树的存储形式A．双亲表示法B．孩子链表示法C．孩子兄弟链表示法D．顺序存储表示法6．二叉树若用顺序方法存储，则下列4种运算中的（）最容易实现。

A．先序遍历二叉树B．判断两个指定结点是不是在同一层上C．层次遍历二叉树D．根据结点的值查找其存储位置7．一个完全二叉树上有1001个结点，其中叶子结点的个数是（）A．250 B．501 C．254 D。

5058．在高度为h的完全二叉树中（）A．度为0的结点都在第h 层上B．第I (1<=i<=h)层上结点都是度为2的结点C．第I (1<=i<=h-1)层上有2i-1个结点D．不存在度为1的结点9．若一刻二叉树具有10个度为2的节点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定10．若二叉树的中序遍历序列是abcdef，且c为根结点，则（）A．结点c有两个孩子B．二叉树有两个度为0的结点C．二叉树的高度为5 D．以上都不对11．在任何一棵二叉树中，如果结点a 有左孩子b、右孩子c，则在结点的先序序列、中序序列、后序序列中，（）A．结点b一定在结点a的前面B．结点a一定在结点c的前面C．结点b一定在结点c的前面D．结点a一定在结点b的前面12．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。

1、一颗二叉树的括号表示为“1(2(4，5(6，7))，3)”）。

设N代表二叉树的根，L代表根节点的左子树，R代表根节点的右子树。

若遍历后的节点序列为3，1，7，5，6，2，4，则其遍历方式是（）。

A.NRLB.RLNC.LRND.RNL正确答案：D2、若二叉树（每个节点值为单个字符）的中序遍历序列是abcdef，且c为根节点，则（）。

A.二叉树有两个度为0的节点B.二叉树的高度为5C.节点c有两个孩子D.以上都不对正确答案：C解析： C、从中序序列看出，节点c的左右子树均不空。

3、若知道一棵二叉树的（），便可以唯一确定该二叉树。

A.中序序列B.先序和后序序列C.中序和后序序列D.先序序列正确答案：C4、一棵二叉树的先序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。

A.ADCFEGB.ABCDEFGC.DACEFBGD.CABDEFG正确答案：B解析： B、当一棵二叉树所有节点的左子树为空时，先序遍历序列和中序遍历序列相同。

先序序列和中序序列可以确定一棵二叉树，这里由选项A、C和D的中序序列无法确定一棵二叉树。

5、一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为（）A.FEDCBAB.CBEFDAC.CBEDFAD.不确定正确答案：B6、某棵二叉树中，X节点有左孩子Y节点，则在其先序遍历中（）。

A.访问Y节点后，接着遍历Y节点的左子树，然后访问X节点B.访问X节点后，接着遍历Y节点的左子树，然后访问Y节点C.访问Y节点后立即访问X节点D.访问X节点后立即访问Y节点正确答案：D解析： D、其先序遍历序列为…XY…。

7、关于二叉树（含2个以上的节点）的先序遍历序列中，以下正确的是（）。

A.先序遍历序列的最后一个节点是根节点B.先序遍历序列的最后一个节点一定是叶子节点C.以上都不对D.先序遍历序列的第一个节点一定是叶子节点正确答案：B解析： B、先序遍历过程是：NLR，最后访问的节点的L、R均为空，所以为叶子节点。

第6章+树和二叉树(习题)2021信息与计算科学专业数据结构习题第六章树和二叉树一、选择题1．已知一算术表达式的中缀形式为a+b*c-d/e，后缀形式为abc*+de/-，其前缀形式为()a．-a+b*c/deb.-a+b*cd/ec．-+*abc/ded.-+a*bc/de2．算术表达式a+b*（c+d/e）变为后缀表达式后为（）a．ab+cde/*b．abcde/+*+c．abcde/*++d．abcde*/++3.设树t的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则t中的叶子数为（）a．5b．6c．7d．84.在下列结论中，恰当的就是（）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为k的完全二叉树的结点个数小于或等于深度相同的满二叉树。

a．①②③b．②③④c．②④d．①④5.设森林f对应的二叉树为b，它有m个结点，b的根为p,p的右子树结点个数为n,森林f中第一棵树的结点个数是（）a．m-nb．m-n-1c．n+1d．条件严重不足，无法确认6．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）a．9b．11c．15d．不确认7．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个a．4b．5c．6d．78．设森林f中有三棵树，第一，第二，第三棵树的结点个数分别为m1，m2和m3。

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

a．m1b．m1+m2c．m3d．m2+m39．具备10个叶结点的二叉树中存有（）个度为2的结点。

a．8b．9c．10d．ll10．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）562021信息与计算科学专业数据结构习题a．250b．500c．254d．505e．以上答案都不对11.设取值权值总数存有n个，其哈夫曼一棵的结点总数为()a．不确认b．2nc．2n+1d．2n-112.存有n个叶子的哈夫曼一棵的结点总数为（）。

习题5 树和二叉树一、选择题：1．在具有n个结点的完全二叉树中，结点i（i>1）的父结点是（）A．2i B．不存在C．2i+1 D．⌊ i/2⌋2. 有m个叶结点的哈夫曼树所具有的结点数为（）A．m B．m+1 C．2m D．2m - 13. 下列陈述中正确的（）A．二叉树是度为2的有序树B．二叉树中结点只有一个孩子时无左右之分C．二叉树中必有度为2的结点D．二叉树中最多只有两棵子树，并且有左右之分4. 以二叉链表作为二叉树的存储结构，在具有ｎ个结点的二叉链表中(n>0)，空链域的个数为（）A．2n - 1 B．n - 1 C．n + 1 D．2n + 15. 将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）A．99 B．98 C．50 D．486. 在一棵具有五层的满二叉树中，结点总数为（）A．31 B．32 C．33 D．167. 在一棵二叉树中，第5层上的结点数最多为（）A．8 B．15 C．16 D．328. 由二叉树的（）遍历，可以惟一确定一棵二叉树A．前序和后序B．前序和中序C．后序D．中序9. 具有35个结点的完全二叉树的深度为（）。

A.5B.6C.7D.810. 已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根的右子树的根是（）。

A．E B. F C. G D. J11. 由4个结点构造出的不同的二叉树个数共有（）。

A．8 B. 10 C．12 D．1412. 在完全二叉树中，如果一个结点是叶子结点，则它没有（）。

A.左孩子结点B. 右孩子结点C.左、右孩子结点D.左、右孩子结点和兄弟结点13. 深度为6的二叉树最多有（）个结点。

A．64 B．63 C．32 D．3114. 二叉树使用二叉链表存储，若p指针指向二叉树的一个结点，当p->lchild=NULL时，则（）。

1.若在一棵非空树中，某结点A有3个兄弟结点（包括A自身），B是A的双亲结点，则B的度是（）。

A. 2B. 3C. 4D. 52.有关二叉树下列说法正确的是（）A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为23.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为（）。

A.98B.99C.50D.484.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点至少为（）。

A.hB.2h-1C.2h+1D.h+15.假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点数为。

A. 15B. 16C. 17D. 476.假定一棵二叉树的结点数为18个，则它的最小高度。

A. 4B. 5C. 6D. 187.在一棵二叉树中第五层上的结点数最多为。

A. 8B. 15C. 16D. 328.在一棵具有五层的满二叉树中，结点总数为。

A. 31B. 32C. 33D. 169.一个有31个结点的满二叉树，其深度有（）。

A.5层B. 6层C. 7层D.8层10.一个具有767个结点的完全二叉树，其叶子结点个数为（）。

A. 383B. 384C. 385D. 38611.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 。

则T中的叶子数为（）。

A．5 B．6 C．7 D．812.某二叉树中序序列为abcdefg，后序序列为bdcafge，则前序序列是（）。

A. egfacdbB. eacbdgfC. eagcfbdD.上面的都不对13.设A、B为一棵二叉树上的两个结点。

在中序遍历时，A在B前面的条件是（）。

A. A在B的右方B. A在B的左方C. A是B的祖先D. A是B的子孙14.在N个结点的线索二叉树中，线索的数目为（）A.N-1B.NC.N+1D.2N15.引入二叉线索树的目的是（）A.加快查找结点的前驱或后继的速度B.为了能在二叉树中方便的进行插入与删除C.为了能方便的找到双亲D.使二叉树的遍历结果惟一16.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定17.在有n个叶子结点的哈夫曼树中，其分支结点（非叶子结点）的总数为( )。

第六章树和二叉树作业一、选择题（每题2分，共24分）。

1. 一棵二叉树的顺序存储情况如下：树中，度为2的结点数为（ C ）。

A．1 B．2 C．3 D．42. 一棵“完全二叉树”结点数为25，高度为（B ）。

A．4 B．5 C．6 D．不确定3．下列说法中，（B ）是正确的。

A. 二叉树就是度为2的树B. 二叉树中不存在度大于2的结点C. 二叉树是有序树D. 二叉树中每个结点的度均为24.一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是（B ）。

A. CABDEFGB. BCDAEFGC. DACEFBGD. ADBCFEG5．线索二叉树中的线索指的是（C ）。

A．左孩子 B.遍历 C.指针 D.标志6. 建立线索二叉树的目的是（A ）。

A. 方便查找某结点的前驱或后继B. 方便二叉树的插入与删除C. 方便查找某结点的双亲D. 使二叉树的遍历结果唯一7. 有 D ）示意。

A.B.C.D.8. 一颗有2046个结点的完全二叉树的第10层上共有（B ）个结点。

A. 511B. 512C. 1023D. 10249. 一棵完全二叉树一定是一棵（A ）。

A. 平衡二叉树B. 二叉排序树C. 堆D. 哈夫曼树10．某二叉树的中序遍历序列和后序遍历序列正好相反，则该二叉树一定是（ C ）的二叉树。

A ．空或只有一个结点B ．高度等于其结点数C ．任一结点无左孩子D ．任一结点无右孩子11．一棵二叉树的顺序存储情况如下：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15A B C D E 0 F 0 0 G H 0 0 0 X结点D 的左孩子结点为（ D ）。

A ．EB ．C C ．FD ．没有12．一棵“完全二叉树”结点数为25，高度为（ B ）。

A ．4B ．5C ．6D ．不确定二、填空题（每空3分，共18分）。

1. 树的路径长度：是从树根到每个结点的路径长度之和。

对结点数相同的树来说，路径长度最短的是 完全 二叉树。

树和二叉树习题及答案一、填空题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-1 2i-1二、单选题1. 具有10个叶结点的二叉树中有 (B) 个度为2的结点。

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

n-，由于1 、【答案】B。

如果根结点的深度为1，则满二叉树结点总数为2111-=2048-1=2047<2381，故整个树高为11（满二叉树）+1=12。

由于本题设定的根结点21深度为0，故该题的树高为11。

2、【答案】BC。

不论先根、中序和后根，左子树的结点总是出现在右子树结点的前面。

①先根: 123456，后根:325641，则1是根；②先根：与1相连的是2，后根以2为界，得到1的左右两棵子树，左子树：32，右子树564。

③递归求解，先根: 23，后根32，得到：3既可以是2的左子树，也可以是右子树④先根：456，后根：564，得到：先根、后根遍历得到的二叉树不唯一⑤对生成的二叉树（两种情况）中根遍历，得到答案B和C。

关于先根、中根和后根遍历求解问题，需要大家重点掌握。

3、【答案】ABD。

①先根：124563 后根：4652731 得到：根结点为1。

②先根1后为2，后根以2为分界，4652是根结点的左子树（其中2是左结点），73是根结点的右子树。

③继续递归求解，先根：456 后根：465，则4为2的左子树，56为2的右子树。

④先根：56 后根：65，则5为2的右子树，6既可以是5的左子树，也可以是右子树。

⑤先根：37 后根：73，则1的右子树为3，7既可以是3的左子树，也可以是右子树，得到全树结构。

最后中根遍历，共4组解。

ABD是其中三种，还是一种：4265137。

4、【答案】C。

设二叉树中度为0的结点(叶子)有N0个，度为1的结点有N1个，度为2的结点有N2个，所有结点个数：N0＋N1＋N2，所有的边数：N0*0+N1*1+N2*2=N1+2N2。

由于每个结点上都有一条边，除根结点外，所以有N0+N1+N2=N1+2N2+1→N0=N2+1 …………①完全二叉树有2*N-1个结点（奇数个），而完全二叉树的上一层是一棵满二叉树，而满二叉树的结点个数是2^k-1（k是层数，是奇数个），所以此二叉树最下一层是偶数个结点，这样的二叉树没有度为1的结点，即N1=0，得到N0+N2=2*N-1 →N2=2*N-N0-1 …………②将②式代入①式，得到N0=N。

一、单选题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. 试写出如图所⽰的⼆叉树分别按先序、中序、后序遍历时得到的结点序列。

第6章树和二叉树6.1知识点: 树和二叉树的基本概念一、填空题1. n 22. 一个数据元素分支结点的度叶子或终端结点非终端结点或分支结点树的度3. n-14.45. 每个结点至多只有两颗子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒6. 满二叉树7. 完全二叉树8.31 329.9 10.500 499 1 011. 5 12.20 13.5 14.31 15.n-2n0+1二、选择题1.C2.A3.B4.A5.D6.D7. ABC＝1，1，3三、简答题1．度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。

即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。

四、算法设计题1.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); //不管孩子是否为空,都入队列}}//whilereturn 1;}//IsFull_Bitree分析:该问题可以通过层序遍历的方法来解决.不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针.6.2知识点：遍历二叉树和线索二叉树一、填空题1.n+12. L R N F E G H D C B3. 二叉链表、三叉链表、双亲链表、线索链表4. 线索线索二叉树二叉树的线索化5. 左孩子该结点的前驱结点右孩子该结点的后继结点二、选择题1.D2.C3.A三、判断题1.√2. ×3. √4. √5. √6. √四、简答题1.DLR：A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD：J F K G D B H L M I E C A2.这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为：A B C C E E B A D F F D G G3.若已知一棵二叉树的后序序列是FEGHDCB，中序序列是FEBGCHD，则它的先序序列必是BEFCGDH 。

第6章树和二叉树习题一、选择题1、如果T2是由树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（）。

A．先序 B．中序 C．后序 D．层次序2、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（）A．5 B．6 C．7 D．83、由3 个结点可以构造出多少种不同的二叉树？（）A．2 B．3 C．4 D．54、二叉树在线索后，仍不能有效求解的问题是（）。

A．前（先）序线索二叉树中求前（先）序后继 B．中序线索二叉树中求中序后继C．中序线索二叉树中求中序前驱 D．后序线索二叉树中求后序后继5、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。

A．9 B．11 C．15 D．不确定6、设F是一个森林，B是由F变换得的二叉树。

若F中有n个非终端结点，则B中右指针域为空的结点有（）个。

A． n-1 B．n C． n+1 D． n+27、设给定权值总数有n 个，其哈夫曼树的结点总数为( ) 。

A．不确定 B．2n C．2n+1 D．2n-18、（）的遍历仍需要栈的支持.A．前序线索树 B．中序线索树 C．后序线索树9、在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同B．完全相同 C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同10、一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG二、填空题1、已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______。

2、树在计算机内的表示方式有，，。

3、在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =______。

4、如果结点A有 3个兄弟，而且B是A的双亲，则B的度是______。

5、设一棵完全二叉树叶子结点数为k,最后一层结点数>2，则该二叉树的高度为______。

第６章树和二叉树习题答案1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。

答：树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。

树和二叉树的区别有三：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。

2．请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。

答：线性表属于约束最强的线性结构，在非空线性表中，只有一个“第一个”元素，也只有一个“最后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，每个元素有唯一后继。

树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，但只有一个双亲（根无双亲），从这个意义上说存在一（双亲）对多（子女）的关系。

广义表中的元素既可以是原子，也可以是子表，子表可以为它表共享。

从表中套表意义上说，广义表也是层次结构。

从逻辑上讲，树和广义表均属非线性结构。

但在以下意义上，又蜕变为线性结构。

如度为1的树，以及广义表中的元素都是原子时。

另外，广义表从元素之间的关系可看成前驱和后继，也符合线性表，但这时元素有原子，也有子表，即元素并不属于同一数据对象。

3．在二叉树的Ｌlink-Rlink存储表示中，引入“线索”的好处是什么？答：在二叉链表表示的二叉树中，引入线索的目的主要是便于查找结点的前驱和后继。

因为若知道各结点的后继，二叉树的遍历就变成非常简单。

二叉链表结构查结点的左右子女非常方便，但其前驱和后继是在遍历中形成的。

为了将非线性结构二叉树的结点排成线性序列，利用结点的空链域，左链为空时用作前驱指针，右链为空时作为后继指针。

第六章树和二叉树一、选择题4. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（）A．5 B．6 C．7 D．85. 在下述结论中，正确的是（）①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③ B．②③④ C．②④ D．①④8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个A．4 B．5 C．6 D．711．具有10个叶结点的二叉树中有（）个度为2的结点，A．8 B．9 C．10 D．ll12．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A． 250 B． 500 C．254 D．505 E．以上答案都不对13. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )A．不确定 B．2n C．2n+1 D．2n-114. 有n个叶子的哈夫曼树的结点总数为（）。

A．不确定 B．2n C．2n+1 D．2n-115．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（）。

A．n-1 B．⎣n/m⎦-1 C．⎡(n-1)/(m-1)⎤D．⎡n/(m-1)⎤-1E．⎡(n+1)/(m+1)⎤-116. 有关二叉树下列说法正确的是（）A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为217．二叉树的第I层上最多含有结点数为（）A．2I B． 2I-1-1 C． 2I-1 D．2I -118. 一个具有1025个结点的二叉树的高h为（）A．11 B．10 C．11至1025之间 D．10至1024之间19．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+122．深度为h的满m叉树的第k层有（）个结点。

习题六树和二叉树一、单项选择题1．以下说法错误的是 ( )A．树形结构的特点是一个结点可以有多个直接前趋B．线性结构中的一个结点至多只有一个直接后继C．树形结构可以表达(组织)更复杂的数据D．树(及一切树形结构)是一种"分支层次"结构E．任何只含一个结点的集合是一棵树2．下列说法中正确的是 ( )A．任何一棵二叉树中至少有一个结点的度为2B．任何一棵二叉树中每个结点的度都为2C．任何一棵二叉树中的度肯定等于2D．任何一棵二叉树中的度可以小于23．讨论树、森林和二叉树的关系，目的是为了（）A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储C．将树、森林转换成二叉树D．体现一种技巧，没有什么实际意义4．树最适合用来表示 ( )A．有序数据元素 B．无序数据元素C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。

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

A．M1 B．M1+M2 C．M3 D．M2+M37．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A． 250 B． 500 C．254 D．505 E．以上答案都不对8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )A．不确定 B．2n C．2n+1 D．2n-19．二叉树的第I层上最多含有结点数为（）A．2I B． 2I-1-1 C． 2I-1 D．2I -110．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+111. 利用二叉链表存储树，则根结点的右指针是（）。

A．指向最左孩子 B．指向最右孩子 C．空 D．非空12．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。