二叉树实验报告.doc

实验题目：实验九——二叉树实验 算法设计（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 1325 1 3 2 5 4 1 1 2 3 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 交换前： 交换后： 166 16 6 11 7 18 3 13 19 17 11 7 16 6 13 3 19 18 17 概要设计： 1、为了实现上述功能：①构造一个空的二叉树；②应用先序遍历输入，建立二叉树；③中序遍历二叉树；④调用左右子树交换函数；⑤中序遍历交换过后的二叉树。 2、本程序包括4个函数： ① 主函数main（） ② 先序遍历二叉树建立函数creat_bt（） ③ 中序遍历二叉树函数inorder（） ④ 左右子树交换函数 exchange（） 各函数间关系如下： main（） 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) { 判断是否为空{ 递归左子树； 输出； 递归右子树；} } 源代码： #includestdio.h #includemalloc.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(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) { inorder(bt-lchild); printf(%d ,bt-data); inorder(bt-rchild); } } void main() { bitree root; printf(先序遍历建立二叉树，输入元素(0表示空）：\n); root=creat_bt(); printf(交换前的中序序列