实验题目：实验九——二叉树实验 算法设计（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 交换前： 交换后： 1 1 2 3 3 2 5 4 4 5 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 交换前： 交换后： 3 3 6 7 7 6 16 11 11 16 13 18 18 13 19 19 17 17

概要设计：

1、为了实现上述功能：①构造一个空的二叉树；②应用先序遍历输入，建立二叉树；③中序遍历二叉树；④调用左右子树交换函数；⑤中序遍历交换过后的二叉树。

2、本程序包括4个函数： ① 主函数main（）

② 先序遍历二叉树建立函数creat_bt（） ③ 中序遍历二叉树函数inorder（） ④ 左右子树交换函数 exchange（）

各函数间关系如下：

creat_bt（）

inorder（） main（）

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) {

判断是否为空{ 递归左子树； 输出；

递归右子树；} }

源代码：

#include #include

typedef struct binode //定义二叉树 {

int data; //数据域

struct binode *lchild,*rchild; //左孩子、右孩子 }binode,*bitree;

bitree creat_bt() //按先序遍历建二叉树 {

bitree t; int x; scanf(\

if(x==0) t=NULL; //0表示空结点 else { t=(bitree)malloc(sizeof(binode));

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) {