实验题目：实验九——二叉树实验
算法设计（3）
问题分析：
1、题目要求：编写算法交换二叉树中所有结点的左右子树
2、设计思路：首先定义一个二叉树的数据类型，使用先序遍历建立该二叉树，遍历二叉树，设计左右子树交换的函数，再次遍历交换之后的二叉树，与先前二叉树进行比较。

遍历算法与交换算法使用递归设计更加简洁。

3、测试数据：
A、输入：1 2 4 0 0 5 0 0 3 0 0
交换前中序遍历：4 2 5 1 3
交换后中序遍历：3 1 5 2 4
交换前：交换后：
B、输入：3 7 11 0 0 18 17 0 0 19 0 0 6 13 0 0 16 0 0
交换前中序遍历：11 7 17 18 19 3 13 6 16
交换后中序遍历：16 6 13 3 19 18 17 7 11
概要设计：
1、为了实现上述功能：①构造一个空的二叉树；②应用先序遍历输入，建立二叉树；③中序遍历二叉树；④调用左右子树交换函数；⑤中序遍历交换过后的二叉树。

2、本程序包括4个函数：
①主函数main（）
②先序遍历二叉树建立函数creat_bt（）
③中序遍历二叉树函数inorder（）
④左右子树交换函数 exchange（）
各函数间关系如下：
详细设计：
1、结点类型
typedef struct binode //定义二叉树
{
int data; //数据域
struct binode *lchild,*rchild; //左孩子、右孩子
}binode,*bitree;
2、各函数操作
① 先序遍历建二叉树函数
bitree creat_bt()
{
输入结点数据；
判断是否为0{
若是，为空；
不是，递归；}
返回二叉树；
}
② 左右子树交换函数
void exchange(bitree t)
{
判断结点是否为空{
否，交换左右子树；
递归；}
}
③ 中序遍历函数
void inorder(bitree bt)
{
判断是否为空{
递归左子树；
输出；
递归右子树；}
}
main （） creat_bt （） inorder （） exchange （）
源代码：
#include<stdio.h>
#include<malloc.h>
typedef struct binode //定义二叉树
{
int data; //数据域
struct binode *lchild,*rchild; //左孩子、右孩子
}binode,*bitree;
bitree creat_bt() //按先序遍历建二叉树
{
bitree t;
int x;
scanf("%d",&x);
if(x==0) t=NULL; //0表示空结点
else
{
t=(bitree)malloc(sizeof(b inode));
t->data=x;
t->lchild=creat_bt(); //递归
t->rchild=creat_bt();
}
return t;
}
void exchange(bitree t) //左、右子树交换
{
bitree p;
if(t!=NULL) //不是空树
{
p=t->lchild;
t->lchild=t->rchild; t->rchild=p; //左右交换
exchange(t->lchild); //递归
exchange(t->rchild);
}
}
void inorder(bitree bt) //递归的中序遍历
{
if(bt)
{
inorder(bt->lchild);
printf("%d ",bt->data);
inorder(bt->rchild);
}
}
void main()
{
bitree root; printf("先序遍历建立二叉树，输入元素(0表示空）：\n"); root=creat_bt();
printf("交换前的中序序列是：");
inorder(root);
exchange(root);
printf("\n交换后的中序序列是：");
inorder(root);
printf("\n");
}
测试结果:
调试分析：
1、函数多以递归设计，虽然大大减轻了代码上的复杂度，是思路更加明了，但也更加容易出错，尤其要注意递归函数出口的设计，否则程序难以执行。

如：
①
If（t!=NULL）即为递归函数出口，当结点为空时，递归函数结束；
②
If（bt）为函数出口，当bt为真时，执行递归；否则，递归结束。

2、注意遍历函数中遍历的次序，
递归时先遍历左子树，后遍历右子树，这是先序遍历。

使用说明：
1、打开左右子树交换.exe
2、按先序遍历输入二叉树的各元素
3、回车确认，比较结果。