编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号。
A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 答案：C
解释：根据题意可知按照先左孩子、再右孩子、最后双亲结点的顺序遍历二叉树，即后序遍历二叉树。
（8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。
A．前序 B．中序 C．后序 D．按层次 答案：C
解释：后续遍历和层次遍历均可实现左右子树的交换，不过层次遍历的实现消耗比后续大，后序遍历方法最合适。
（9）在下列存储形式中，（ ）不是树的存储形式？
A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 答案：D
解释：树的存储结构有三种：双亲表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵树都能通过孩子兄弟表示法转换为二叉树进行存储。
（10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）。
A．所有的结点均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是任意一棵二叉树 答案：C
解释：因为先序遍历结果是“中左右”，后序遍历结果是“左右中”，当没有左子树时，就是“中右”和“右中”；当没有右子树时，就是“中左”和“左中”。则所有的结点均无左孩子或所有的结点均无右孩子均可，所以A、B不能选，又所有的结点均无左孩子与所有的结点均无右孩子时，均只有一个叶子结点，故选C。
（11）设哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。 A．99 C．101 答案：B
解释：在哈夫曼树中没有度为1的结点，只有度为0（叶子结点）和度为2的结点。设叶子结点的个数为n0，度为2的结点的个数为n2，由二叉树的性质n0=n2+1，则总结点数n= n0+n2=2*n0-1，得到n0=100。
（12）若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（ ）。 A．X的双亲 B．X的右子树中最左的结点 C．X的左子树中最右结点 D．X的左子树中最右叶结点 答案：C
（13）引入二叉线索树的目的是（ ）。
16
B．100 D．102
A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除
C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 答案：A
（14）设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。
A．n?1 答案：C
（15）n（n≥2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（ ）。 A．该树一定是一棵完全二叉树 B．树中一定没有度为1的结点
C．树中两个权值最小的结点一定是兄弟结点
D．树中任一非叶结点的权值一定不小于下一层任一结点的权值 答案：A
解释：哈夫曼树的构造过程是每次都选取权值最小的树作为左右子树构造一棵新的二叉树，所以树中一定没有度为1的结点、两个权值最小的结点一定是兄弟结点、任一非叶结点的权值一定不小于下一层任一结点的权值。
2．应用题
（1）试找出满足下列条件的二叉树
① 先序序列与后序序列相同 ②中序序列与后序序列相同 ③ 先序序列与中序序列相同 ④中序序列与层次遍历序列相同
答案：先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右
子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则有
① 或为空树，或为只有根结点的二叉树
② 或为空树，或为任一结点至多只有左子树的二叉树． ③ 或为空树，或为任一结点至多只有右子树的二叉树． ④ 或为空树，或为任一结点至多只有右子树的二叉树
（2）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C ①画出这棵二叉树。
②画出这棵二叉树的后序线索树。
③将这棵二叉树转换成对应的树（或森林）。 A A B BC D B．n C．n + 1 D．n + 2
CB
A
D
E
C
H EDnull17 EF G
① ②
3．算法设计题
以二叉链表作为二叉树的存储结构，编写以下算法： （1）统计二叉树的叶结点个数。
[题目分析]如果二叉树为空，返回0，如果二叉树不为空且左右子树为空，返回1，如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数。 [算法描述]
int LeafNodeCount(BiTree T) { }
（2）判别两棵树是否相等。
[题目分析]先判断当前节点是否相等(需要处理为空、是否都为空、是否相等)，如果当前节点不相等，直接返回两棵树不相等;如果当前节点相等，那么就递归的判断他们的左右孩子是否相等。 [算法描述]
int compareTree(TreeNode* tree1, TreeNode* tree2)
//用分治的方法做，比较当前根，然后比较左子树和右子树 {bool tree1IsNull = (tree1==NULL); bool tree2IsNull = (tree2==NULL); if(tree1IsNull != tree2IsNull) { return 1; }
if(tree1IsNull && tree2IsNull) {//如果两个都是NULL，则相等 return 0;
18
if(T==NULL)
return 0; //如果是空树，则叶子结点个数为0
return 1; //判断结点是否是叶子结点（左孩子右孩子都为空），若是则返回1 return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild); else if(T->lchild==NULL&&T->rchild==NULL) else
}//如果根节点不相等，直接返回不相等，否则的话，看看他们孩子相等不相等 if(tree1->c != tree2->c) { return 1; }
return (compareTree(tree1->left,tree2->left)&compareTree(tree1->right,tree2->right)) (compareTree(tree1->left,tree2->right)&compareTree(tree1->right,tree2->left)); }//算法结束
（3）交换二叉树每个结点的左孩子和右孩子。
[题目分析]如果某结点左右子树为空，返回，否则交换该结点左右孩子，然后递归交换左右子树。
[算法描述]
void ChangeLR(BiTree &T) { }
（5）计算二叉树最大的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。
[题目分析] 求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。
[算法描述]
int Width(BiTree bt)//求二叉树bt的最大宽度 {if (bt==null) return (0); //空二叉树宽度为0 else
{BiTree Q[];//Q是队列，元素为二叉树结点指针，容量足够大 front=1;rear=1;last=1;
19
BiTree temp;
if(T->lchild==NULL&&T->rchild==NULL) else {
temp = T->lchild; T->lchild = T->rchild; return;
T->rchild = temp;
}//交换左右孩子
ChangeLR(T->lchild); //递归交换左子树 ChangeLR(T->rchild); //递归交换右子树
//front队头指针,rear队尾指针,last同层最右结点在队列中的位置 temp=0; maxw=0; //temp记局部宽度, maxw记最大宽度 Q[rear]=bt; //根结点入队列 while(front<=last)
{p=Q[front++]; temp++; //同层元素数加1
if (p->lchild!=null) Q[++rear]=p->lchild; //左子女入队 if (p->rchild!=null) Q[++rear]=p->rchild; //右子女入队 if (front>last) //一层结束，
{last=rear;
if(temp>maxw) maxw=temp;
//last指向下层最右元素, 更新当前最大宽度
temp=0;
}//if }//while return (maxw); }//结束width
若某个结点左子树空右子树非空或者右子树空左子树非空，则该结点为度为1的结点
20
数据结构（C语言版）第2版习题答案—严蔚敏（简化版）
