第5章 树与二叉树
1．选择题
CCACB BDABD CACA
2．填空题
（1）树的节点个数至少为1而二叉树的节点个数可以为0，树中节点最大度数没有限制而二叉树节点的最大度数为2，树的节点没有左右之分而二叉树的节点有左右之分
（2）树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题
（3）2k-1，2k-1，2k-2 +1
（4）2k-1，2[ log n ，2[ log n ] -1
（5）只有一个节点的树，空的二叉树
（6）5
（7）5
（8）物理
3．问答题
（1）度为2的树中至少有一个节点的度为2，而二叉树不必这样（例如，存在只含一个节点的二叉树）；度为2的树中一个节点的孩子节点没有左右之分，而二叉树中一个节点的孩子节点有左右之分，且左右不能交换。
|
图A-5 一棵树
|
①根节点是A。
②叶子节点是D、M、N、F、J、K、L。
③G的双亲是C。
④G的祖先是A、C。
⑤G的孩子是J、K。
⑥E的子孙是I、M、N。
⑦E的兄弟是D，F的兄弟是G、H。
⑧B的层次是2，N的层次是5。
⑨树的深度是5。
⑩以节点C为根的子树的深度是3。
（3）完全二叉树的特点是除了最高层上的节点不满外，其余层次均充满了节点，最高层上的节点集中在左部。已知完全二叉树的层次遍历序列为：ABCDEFGHIJKL，可以恢复这棵完全二叉树如图A-6所示。对应的先序遍历序列为：ABDHIEJKCFLG，中序遍历序列为：HDIBJEKALFCG，后序遍历序列为：HIDJKEBLFGCA。
（4）依题意，本题对应的哈夫曼树如图A-7所示。各字符对应的哈夫曼编码如下。
a：001 b：10 c：01 d：000 e：11
图A-6 一棵完全二叉树 图A-7 一棵哈夫曼树
（5）根的层次为1，此棵树共有10个层次，则：
①此棵二叉树共有1 023（210-1）个节点。
②第8层次最多有255（28-1）个节点。
③有128-1=127个度为2的节点。
4．上机操作题
（1）采用先序遍历的递归算法，边访问节点边复制节点。对应的算法如下：
void CopyBTree(BTNode *bt,BTNode *&newbt) /*由bt复制产生newbt
{
if (bt!=NULL)
{
newbt=(BTNode *)malloc(sizeof(BTNode)); /*复制根节点*/
newbt->data=bt->data;
CopyBTree(bt->lchild,newbt->lchild); /*递归复制左子树*/
CopyBTree(bt->rchild,newbt->rchild); /*递归复制右子树*/
}
else
newbt=NULL;
}
（2）采用先序遍历方法，用参数p返回最大节点的指针。若当前根节点*bt的值大于p所指节点的值，则p赋值为bt；在左子树中比较，再在右子树中比较。对应的算法如下：
void MaxNode(BTNode *bt,BTNode *&p)
{ /*调用本算法时p=bt*/
if(bt!=NULL)
{
if(bt->data>p->data)
p=bt;
MaxNode(bt->lchild,p);
MaxNode(bt->rchild,p);
}
}
（3）实现左、右孩子进行交换的算法如下：
void exchange (BTnode *t)
{
BTnode *p;
if(t)
{
exchange (t->lchild);
exchange (t->rchild);
if(t->lchild||t->rchild)
{
p=t->lchild;
t->lchild=t->rchild;
t->rchild=p;
}
}
}
（4）规定该算法在给定的二叉树bt中找到值为x的节点，返回该节点的指针，否则返回NULL。采用先序遍历方法，先判断根节点*bt的值是否为x，若是则返回bt，否则，在左子树中查找，若查找到了，算法结束，否则在右子树中查找，并返回其查找的结果。对应的算法如下：
BTNode *FindNode(BTNode *bt,ElemType x)
{
BTNode *p;
if(bt==NULL) /*空树返回NULL*/
return(NULL);
else if(bt->data==x) /*找到后返回根节点指针*/
return(bt);
else
{
p=FindNode(bt->lchild,x); /*在左子树中查找*/
if(p!=NULL) /*在左子树中找到并返回*/
return(p);
else /*否则，在右子树中查找*/
return(FindNode(bt->rchild,x));
}
}
（5）采用后序遍历的递归算法，先删除左子树，再删除右子树，最后删除根节点。对应的算法如下：
void DelTree(BTNode *&bt)
{
if(bt!=NULL)
{
DelTree(bt->lchild); /*删除左子树*/
DelTree(bt->rchild); /*删除右子树*/
free(bt); /*释放根节点*/
}
}