上 机 作 业 3
1.输入带空二叉树(信息)的先序遍历序列，生成一棵二叉树；
若结点为字符类型,用空格表示空二叉树；若结点为整数类型,用0(零)表示空二叉树；
2.作前序遍历，分别用递归算法、非递归算法实现；
3.作中序遍历，分别用递归算法、非递归算法实现；
4.作后序遍历，用递归算法实现；
5.求度分别为0、1、2的结点的数目,分别用递归算法、非递归算法实现；
**6.按层次遍历二叉树(提示：使用一个队列实现）；
**7.求二叉树的高度(深度)；
**8.判断是否为满二叉树，输出"Yes!"/"No!"；
**9.交换每个结点的左右子树；
**10.对交换左右子树后的二叉树作中序遍历。
说明和要求
1.选做带“**”的题；
2.每一种操作用C函数或C++函数实现,二叉树的根指针为C(或C++)函数的形式参数；
3.第12周交第1,2,5题的程序清单(打印或手抄),关键位置加注释。
4.参考程序结构：
#include"stdlib.h" /* 或"malloc.h",存储分配头文件 */
#include"stdio.h" /* 标准I/O头文件 */
#define NULL 0 /* 定义空指针NULL */
#define LENG sizeof(struct Bnode) /* 结点所占的字节数 */
typedef char ElemType; /* 抽象元素类型为整型 */
typedef struct Bnode /* Bnode为结点(结构)类型 */
{ ElemType data； /* data为抽象元素类型 */
struct Bnode *lchild,*rchild； /* 为指针类型 */
}Bnode；
creat_tree(Bnode **root) /*root是指向指针的指针*/
{ /*生成二叉树*/
ElemType ch；
scanf("%c",&ch)； /*输入结点,字符型*/
if (ch==’ ’)(*root)=NULL； /*生成空二叉树*/
else /*生成非空二叉树*/
{ (*root)=(Bnode *)malloc(LENG)；
(*root)->data=ch； /*生成根结点 */
creat_tree(&(*root)->lchild) ； /*递归生成左子树*/
creat_tree(&(*root)->rchild) ； /*递归生成右子树*/
}
return；
}
void preorder(Bnode *root)
{ /*前序遍历二叉树*/
if ( … )
…………
}
……………
……………
void main(void) /*主函数*/
{ Bnode *root；
creat_tree(&root)；
preorder(root)；
…………………
}