第六章作业
参见《数据结构题集》第6章部分P38。

1、一棵度为2的树与一棵二叉树有何区别？（题集6.2）
二叉树是颗有序树，但度为2的树则未必有序。

2、假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。

请画
出该树（题集6.29）。

3、假设二叉树如下，请分别写出先序、中序和后序遍历结果，并画出该二叉树
对应的森林。

答：
先序遍历：A B D G C E F H 中序遍历：D G B A E C H F 后序遍历：G D B E H F C A
A
B C
D E F
G H
4、画出与下列已知序列对应的树T。

（题集6.23）
树的先根次序访问的序列为：GFKDAIEBCHJ；
树的后根次序访问的序列为：DIAEKFCJHBG。

5、请编写一个递归算法，将二叉树中所有结点的左、右子树相互交换。

（题集
6.43）
6、6.43 解：
// 按先序交换二叉树的左右子树
Status ExchangeBiTree(BiTree& T)
{
BiTree p;
if(T){
p=T->lchild;
T->lchild=T->rchild;
T->rchild=p;
ExchangeBiTree(T->lchild);
ExchangeBiTree(T->rchild);
}
return OK;
}
7、对于那些所有非叶子结点均有非空左右子树的二叉树，试问：有n个叶子结
点的树中共有多少个结点？
2n-1
8、森林与二叉树的转换。

（题集6.21）
树二叉树
根根
第一个孩子左孩子
右兄弟右孩子
8、选做：请设计按层次顺序（同一层自左向右）遍历二叉树的算法。

（题集6.47）
typedef BiTree QElemType;
#include "c:\Yin\include\Queue.h"
Status LevelOrderTraverse(BiTree& T,Status (*Visit)(TElemType e))
{
QElemType p;
Queue q;
InitQueue(q);
if(T) EnQueue(q,T);
while(!QueueEmpty(q)){
DeQueue(q,p);
Visit(p->data);
if(p->lchild) EnQueue(q,p->lchild);
if(p->rchild) EnQueue(q,p->rchild);
}
return OK;
}
（注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。

可复制、编制，期待你的好评与关注）。