内容发布更新时间 : 2024/9/16 11:41:39星期一 下面是文章的全部内容请认真阅读。
实验题目：实验九——二叉树实验 算法设计（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
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) {