一、问题描述
二叉树是一种常见的特殊的树型结构，在计算机领域有着极为广泛的应用。在二叉树的一些应用中，常常要求在树中查找具有某些特征的结点或者对树中全部结点逐一进行某种处理，这就提出了遍历二叉树。根据遍历的方向的不同，有前序遍历、中序遍历、后序遍历以及层序遍历。在本次课程设计中，要求学生通过编写程序完成对二叉树的一些操作，比如可以构造二叉树、打印二叉树、遍历二叉树以及对左右子树进行交换等等。
二、基本要求
要求：。构造一颗20个节点的完全二叉树或者20个节点以上的满二叉树。 实现如下步骤：
（1）实现二叉树的构造过程，并打印出二叉树
（2）对该二叉树分别用层序、前序、中序和后序四种不同的方法进行遍历； （3）将该二叉树的所有左右子树进行交换，得到新的二叉树，并打印出该二叉树； （4）对新获得的二叉树分别用层序、前序、中序和后序四种不同的方法进行遍历。
三、数据结构的设计
由数据结构中二叉树的定义可知，二叉树的结点由一个数据元素和分别指
向其左、右子树的两个分支构成，所以在本程序二叉树的构造是采用二叉链表的链式存储结构，链表中的结点应包含三个域：数据域和左、右孩子的指针域。这种存储结构可以方便二叉树的建立以及遍历。 1、结点的数据结构
struct node {
char data;
struct node *lchild,*rchild;
}
2、基本操作
void Create(BiTNode **p)
初始条件：按照结点的结构体构造二叉树；
操作结果：构造一棵二叉树。
void PreOrderTraverse(BiTree T) 初始条件：二叉树T存在；
操作结果： 按照前序遍历方法遍历二叉树。
void InOrderTraverse(BiTree T) 初始条件：二叉树T存在；
操作结果：按照中序遍历方法遍历二叉树。
void PostOrderTraverse(BiTree T) 初始条件：二叉树T存在；
操作结果：按照后序遍历方法遍历二叉树。 void LevelOrderTraverse(BiTree T) 初始条件：二叉树T存在；
操作结果：按照层序遍历方法遍历二叉树。 void SwapChild(BiTNode **p)
初始条件：二叉树存在且交换的结点有子树； 操作结果：将二叉树左右结点交换。 void Paint(BiTree T)
初始条件：二叉树T存在；
操作结果：将二叉树的结点打印出来。
四、软件模块结构图
构造二叉树 主函数 打印二叉树 前序遍历 层序遍历 遍历函数 菜单函数 左右子树交换
中序遍历 五、 程序设计思想 1、程序设计基本思想
(1)本实验要求编写一个程序实现对二叉树的各种基本操作，并以此为
目的设计一个程序，完成如下功能：
1、输入二叉树的先序序列字符，建立二叉链表。注意：输入时，必须
加入虚结点以示空指针的位置；假设虚结点输入时用空格字符表示。 2、打印二叉树。
3、按先序、中序、后序和层序三种不同方法遍历二叉树。 4、交换二叉树的所有左右子树。
5、打印二叉树，并且分别按照先序、中序、后序和层序三种不同方法
遍历二叉树。
6、在设计一个简单的菜单，分别调试上述算法。 7、编写主程序完成各功能的调用和实现。
(2)测试数据：
1、按照先序序列依次输入字符。
2、打印二叉树并且按先序、中序和后序遍历二叉树并输出遍历结果。 3、输出交换二叉树的左右子树并且打印二叉树并且按先序、中序和后
序遍历二叉树并输出遍历结果。
后序遍历 2、程序设计基本思想
本程序含有7个函数；
①主函数main( )
②前序遍历二叉树PreOrderTraverse(T,PrintChar) ③中序遍历二叉树Inorder(T) ④后续遍历二叉树Postorder(T)
⑤层序遍历二叉树LevelOrderTraverse(T) ⑥打印二叉树Paint（T）
⑦交换二叉树所有左右子树SwapChild(T)
六、程序流程图
1、创建函数
开始
输入结点 Ｙ Ｎ 输入为* 新结点
二叉树
构成
结束
空结点
void Create(BiTNode **p) {
char e;
e=getchar(); if(e=='*') (*p)=NULL; else {
if(!((*p)=(BiTree)malloc(sizeof(BiTNode)))) {
printf(\分配失败\\n\ exit(0); }
(*p)->data=e;
Create(&((*p)->lchild)); Create(&((*p)->rchild)); } } 2、前序遍历函数
开始 结点BTNode 是否为空 Ｙ
Ｎ
输出根节点 前序遍历左子树 前序遍历右子树 遍历完成 结束