11.一棵有n个结点的满二叉树有__(1) 0 _个度为1的结点、有__(2) (n-1)/2_个分支 （非 终端）结点和__(3) (n+1)/2 _个叶子，该满二叉树的深度为_(4) ?log2n? +1__。
k-1k
12.深度为k（设根的层数为1）的完全二叉树至少有 (1) 2 个结点，至多有 (2) 2-1 个结点，k和结点数n之间的关系是 (3) k= ? log2n ? ＋1 。 13．在完全二叉树中，编号为i和j的两个结点处于同一层的条件是_?log2i?=?log2j? _____。 14.对于一个具有n个结点的二叉树，当它为一棵_(1) 完全二叉树_二叉树时具有最小高度，当它为一棵_(2) 单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或只有右子女。_时，具有最大高度。
15.假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是_ n _____。 16.具有256个结点的完全二叉树的深度为___9 ___。
17.一棵完全二叉树有999个结点，它的深度是 10 。 18.一个有2001个结点的完全二叉树的高度为_ 11 __。
19.二叉树有不同的链式存储结构，其中最常用的是 (1)二叉链表 与 三叉链表 。 20.二叉树的先序序列和中序序列相同的条件是_任一结点均无左孩子_____。
21.在一棵二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是__双亲的右子树中最左下的叶子结点____。
22.每一棵树都能唯一的转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是_(1) FEGHDCB __。设上述二叉树是由某棵树（或森林）转换而成，则第一棵树的先根次序序列是_(2)_ BEF
23.二叉树结点的中序序列为ABCDEFG,后序序列为BDCAFGE,则该二叉树结点的前序序列为_(1) EACBDGF __,则该二叉树对应的树林包括_(2) 2__棵树。 24.已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，则该二叉树的根为_(1) a __，左子树中结点有_(2) dbe __， 右子树中结点有_(3) hfcg __。
25.现有按中序遍历二叉树的结果为abc，问有_(1) 5 __种不同的二叉树可以得到这一遍历结果，这些二叉树分别是_(2)_ 略 _（画出树型）。 26.中缀式a+b*3+4*（c-d）对应的前缀式为__(1) ++a*b3*4-cd _，若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为_(2) 18__。
27.线索二叉树的左线索指向其 (1) 前驱 ,右线索指向其 (2) 后继 .
28.一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为：_2_____。
29.树在计算机内的表示方式有_(1) 双亲表示法_，_(2) 孩子表示法__，_(3) 孩子兄弟表示法
30.利用树的孩子兄弟表示法存储，可以将一棵树转换为__二叉树 ____。
31.设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有__(1) n1-1_个结点，右子树中有_(2) n2+n3 __个结点。
32.先根次序遍历树林正好等同于按_(1) 先序__遍历对应的二叉树，后根次序遍历树林正好等同于按__(2) 中序_遍历对应的二叉树。
33.先根次序遍历森林正好等同于按____先序__遍历对应的二叉树；中根次序遍历森林正好等同于__中序____遍历对应的二叉树。
34.哈夫曼树是__带权路径长度最小的二叉树，又称最优二叉树____。
35.设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有 2n0-1 个结点。
36.哈夫曼树是带权路径长度 最短 的树,通常权值较大的结点离根 较近 . 37.若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是__69 ____。 38.有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构
造一棵哈夫曼树，则其加权路径长度WPL为_(1) 80__，字符c的编码是_(2) 001（不唯一）__。
39.下面是求二叉树高度的类C写的递归算法试补充完整。二叉树的两指针域为lchild与rchild, 算法中p为二叉树的根，lh和rh分别为以p为根的二叉树的左子树和右子树的高，hi为以p为根的二叉树的高，hi最后返回。
height(p)
{if ((1) p ___)
{if(p->lchild==null) lh=(2)_ 0______; else lh=(3)_ height(p->lchild)______;
if(p->rchild==null) rh=(4)_ 0______; else rh=(5)_
height(p->rchild)______;
if (lh>rh) hi=(6) lh+1__；else hi=(7)_ rh+1______; }
else hi=(8) 0_______; return hi; }//
40.二叉树用二叉链表存储，以下程序为求二叉树深度的递归算法，请填空完善之。
int depth(bitree bt) /*bt为根结点的指针*/ {int hl,hr;
if (bt==NULL) return((1) 0 ___);
hl=depth(bt->lchild); hr=depth(bt->rchild); if((2) hl>hr ___) (3)_ hr=hl ____； return(hr+1); }
三、判断题
1.二叉树是一般树的特殊情形。×
2.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法( X ) 3.二叉树中每个结点至多有两个子结点,而对一般树则无此限制.因此,二叉树是树的特殊情形. ×
4.树形结构中元素之间存在一个对多个的关系。√ 5.二叉树是度为2的有序树。×
6.如果二叉树中某结点的度为1，则说该结点只有一棵子树( √ )
k
7.深度为K的二叉树中结点总数≤2-1。√
8.完全二叉树中，若一个结点没有左孩子，则它必是树叶。√ 9.对于有N个结点的二叉树，其高度为log2n。×
k-2
10.深度为k具有n个结点的完全二叉树，其编号最小的结点序号为 ?2?+1。× 11.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。× 12.完全二叉树的存储结构通常采用顺序存储结构。√ 13.二叉树只能用二叉链表表示。
14.用链表存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。× 15.二叉树的遍历结果不是唯一的. √
只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。 16.二叉树的遍历只是为了在应用中找到一种线性次序。√
17.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面，这种说法( √ )
18.非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子√ 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。 19.由一棵二叉树的前序序列和后序序列可以唯一确定它。× 20.在中序线索二叉树中，每一非空的线索均指向其祖先结点。√ 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。
21.线索二叉树的优点是便于是在中序下查找前驱结点和后继结点。√ 22.二叉树中序线索化后，不存在空指针域。× 非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。
23.给定一棵树，可以找到唯一的一棵二叉树与之对应。√ 24.必须把一般树转换成二叉树后才能进行存储。× 25.将一棵树转成二叉树，根结点没有左子树；× 26.采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。√
27.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。×
28.一棵树中的叶子数一定等于与其对应的二叉树的叶子数。×
29.在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法（ X）。 30.在二叉树中插入结点，则它不再是二叉树了。× 31.哈夫曼树的结点个数不能是偶数。√
32.一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。×
33.当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。×
四．解答应用题
1. 一棵二叉树中的结点的度或为0或为2，则二叉树的枝数为2(n0-1)，其中n0是度为0的结点的个数。
证明：设二叉树度为0和2的结点数及总的结点数分别为n0，n2 和n， 则n=n0+n2 ? (1)
再设二叉树的分支数为B, 除根结点外，每个结点都有一个分支所指， 则 n=B+1? ? ?(2)
度为零的结点是叶子，没有分支，而度为2的结点有两个分支，因此（2）式可写为
n=2*n2+1 ?????(3)
由（1）、（3）得n2=n0-1,代入（1），并由（1）和（2）得B=2*(n0-1)。 证毕。
2．任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有（m-1）个度为2，其余度为1。
证明：设度为1和2 的结点数是n1和n2，则二叉树结点数n为n=m+n1+n2???? (1)
由于二叉树根结点没有分枝所指，度为1和2的结点各有1个和2个分枝，度为0 的结点没有分枝，故二叉树的结点数n与分枝数B有如下关系 n=B+1=n1+2*n2+1?????????.(2)
由（1）和（2），得n2=m-1。即n个结点的二叉树，若叶子结点数是m，则非叶子结点中有（m-1）个度为2，其余度为1。
3．一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。
先序序列是“根左右” 后序序列是“左右根”，可见对任意结点，若至多只有左子女或至多只有右子
女，均可使前序序列与后序序列相反，图示如下：
4．画出同时满足下列两条件的两棵不同的二叉树。
(1)按先根序遍历二叉树顺序为ABCDE。 (2)高度为5其对应的树（森林）的高度最大为4。
5．已知二叉树的先序、中序和后序遍历序列分别如下(但其中一些模糊不清)
先序： ABC__EF__ __ 中序： BDE__AG__ H 后序： _DC__GH__ __ 要求：
（1）补充模糊的地方，并重新写出先序、中序和后序遍历序列 （2）画出该二叉树
（3）画出该二叉树的中序线索树 （4）画出该二叉树对应的森林
A B C D E
E D A B C （5）画出森林中第一棵树的孩子兄弟表示法
答案：
（1）先序：ABCDEFGH; 中序BDECAGFH; EDCBGHFA
（2）二叉树: （4）森林： A F B C G H A C D F H B G E D E 五、算法设计
1．二叉树用二叉链表存储，编写算法求二叉树度为1的结点 （1）给出二叉链表的类型定义
（2）用类C语言写出递归算法 类型定义：
typedef struct BiTNode { TElemType data;
struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; int num(BiTree T) { if(!T)return 0;
else{
nl=num(T->lchild); nr=num(T->rchild);
if(T->lchild&&!T->rchild||! T->lchild&&T->rchild)return nl+nr+1;else return nl+nr; } }
2．编写算法以中序编立的顺序给出每个结点以及该结点的层次（二叉树用二叉链表存储，类型定义如（1）） void inorder (BiTree T,int l) { if (T) {
inorder(T->lchild,l+1);
printf(“%c,%d” ,T->data,l);
inorder(T->rchild,l+1); } }