第6章 树和二叉树
6.1知识点: 树和二叉树的基本概念
一、 填空题
1. 高度为h，度为m的树中至少有___________个结点，至多有______________个结点。
2. 树的结点是由        及若干指向其子树的      组成；结点拥有的子树数称为      ；度为0的结点称为          ；度不为0的结点成为          ；树中结点的最大度数称为      ；树的最大层次称为_____________。
3. 对于一棵具有n个结点的树，该树中所有结点的度数之和为___________。
4. 如果结点A有3个兄弟结点，而且B是A的双亲，则B的度是___________。
5. 二叉树是另一种树形结构，它的特点是                                                    。
6. 一颗度数为k且有2k-1个结点的二叉树称为          。
7. 深度为k，且有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称之为            。
8. 一棵深度为6的满二叉树有      个分支结点和      个叶子。
9. 一棵具有257个结点的完全二叉树，它的深度为      。
10. 设一棵完全二叉树具有1000个结点，则此完全二叉树有      个叶子结点，有      个度为2的结点，有      个结点只有非空左子树，有      个结点只有非空右子树。
11. 由3个结点可以构成__________种形态的的二叉树，可以构成      种形态的树。
12. 将含有82个结点的完全二叉树从根结点开始顺序编号，根结点为第1号，其他结点自上向下，同一层自左向右连续编号。则第40号结点的双亲结点的编号为      。
13. 一棵高度为5的完全二叉树中，最多包含有____________个结点。
14. 一棵具有n个结点的二叉树，若它有n0个叶子结点，则该二叉树上度为1的结点n1=____________。
15. 在高度为h（h>=0）的二叉树中至多可以有__________个结点，至少可以有___________个结点。
16. n个结点的二叉树最大高度是____________,最小高度是_______________。
二、 选择题
1. (    ）不含任何结点的空树（      ）。
    A.是一棵树  B.是一棵二叉树  C.是一棵树也是一棵二叉树  D.既不是树也不是二叉树
2. （    ）一棵度为4的树中度为1、2、3、4的结点个数为4、3、2、1，则该树的结点总数为（      ）。
    A.21        B.26        C.27        D.24
3. (    )具有10个叶子结点的二叉树中有      个度为2的结点。
    A.8        B.9        C.10      D.11
4. (      )在一棵高度为h（假定根结点的层号为1）的完全二叉树中，所含结点个数不小于（  ）。
    A．        B．        C．            D．
5. (      )如下的4棵二叉树中，（    ）不是完全二叉树。
    A．                      B.            C.                D.
6. (    )设树T 的度为4，其中度为1，2，3 ,4 的结点个数分别为4，2，1，1 则T 中的叶子数为（    ）。
    A．5      B．6        C．7      D．8
7. (    )哈夫曼编码树的带权路径长度从供选择的答案中，选出应填入下面叙述      内的最确切的解答，把相应编号写在答卷的对应栏内。
        树是结点的有限集合，它A 根结点，记为T。其余的结点分成为m（m≥0）个  B 
  的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点
  (1≤i≤m）。一个结点的子结点个数为该结点的  C    。
  供选择的答案
  A：  ①有0个或1个    ②有0个或多个    ③有且只有1个    ④有1个或1个以上
  B:  ①互不相交        ② 允许相交      ③ 允许叶结点相交  ④ 允许树枝结点相交
  C： ①权              ② 维数          ③ 次数（或度）      ④ 序
8. （      ）在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（    ）。
    A．2          B．1        C．0            D．-1
三、简答题
1．一棵度为2的树与一棵二叉树有何区别？
6.2知识点：遍历二叉树和线索二叉树
一、填空题
1. 二叉树有四种遍历方法：________、__________、___________、___________。
2. 若已知一棵二叉树的先序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是                    。
3. 二叉树的链式存储结构有：            、          、            、          四种。
4. 指向前驱或后继结点的指针称为      ，加上线索的二叉链表表示的二叉树叫          ，
5. 对二叉树按某种遍历次序使其变为线索二叉树的过程叫            。
6. 在线索二叉树的结点中增加两个标志域LTag和RTag,若LTag=0,则lchild 域指向      ；若 LTag=1, 则lchild域指向                ；若RTag =0,则rchild域指向        ；若RTag=1, 则rchild域
指向                。
二、选择题
1. （      ）某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（    ）。
    A.空树或只有一个结点  B.完全二叉树  C.二叉排序树  D.高度等于其结点数
2. （      ）二叉树是非线性数据结构，所以（    ）。
    A.它不能用顺序存储结构存储            B.它不能用链式存储结构存储
C.顺序存储结构和链式存储结构都能存储  D.顺序存储结构和链式存储结构都不能使用
3. （      ）线索二叉树是一种(      )结构
A.逻辑    B. 存储      C.线性     
4.  在n个结点的线索二叉树中，线索的数目为(    )。
    A.n-1    B. n      C.n+1    D.2n
三、判断题
1. （    ）在先序、中序和后序序列中，叶子结点出现的相对次序是相同的。
2. （    ）由一棵二叉树的先序序列和中序序列可以唯一确定这棵二叉树。
3. （    ）在一棵二叉树中，假定每个结点只有左孩子，没有右孩子，对它分别进行中序遍历和后序遍历，则具有相同的遍历结果。
4. （    ）对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。
5. （    ）在一棵具有n个结点的线索化二叉树中，每个结点的指针域可能指向孩子结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点。
6. （    ）若有一个叶子结点是二叉树中某个子树的先序遍历结果序列的最后一个结点，则它一定是该子树中序遍历结果序列的最后一个结点。
7. （    ）由一棵二叉树的先序序列和后序序列可以唯一确定这棵二叉树。
四、 简答题
1.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
2.设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：
（1）对下列二叉树B，执行下列算法traversal(root)，试指出其输出结果；
（2）假定二叉树B共有n个结点，试分析算法traversal(root)的时间复杂度。