二叉树实验报告

1、实验题目：实验九二叉树实验算法设计（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 41234513254交换前：交换后：B、输入：3 7 11 0 0 18 17 0 0 19 0 0 6 13 0 0 16 0 0交换前中序遍历：11 7 17 18

2、 19 3 13 6 16 交换后中序遍历：16 6 13 3 19 18 17 7 11交换前：交换后：376111618131719367161113181917概要设计：1、为了实现上述功能：构造一个空的二叉树；应用先序遍历输入，建立二叉树；中序遍历二叉树；调用左右子树交换函数；中序遍历交换过后的二叉树。2、本程序包括 4 个函数： 主函数 main（） 先序遍历二叉树建立函数 creat_bt（） 中序遍历二叉树函数 inorder（） 左右子树交换函数 exchange（）1各函数间关系如下：creat_bt（）main（）inorder（）exchange（）详细设计： 1、结点类

3、型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<stdio.h>

4、 #include<malloc.h>typedef struct binode/定义二叉树int data;/数据域struct binode *lchild,*rchild;/左孩子、右孩子binode,*bitree;bitree creat_bt()/按先序遍历建二叉树bitree t;scanf("%d",&x);if(x=0)t=NULL;/0 表示空结点elseinode);t->data=x;t->lchild=creat_bt();/递归t->rchild=creat_bt();int x;t=(bitree)mall

5、oc(sizeof(breturn t;void exchange(bitree t)/左、右子树交换bitree p;if(t!=NULL)/不是空树t->rchild=p;/左右交换exchange(t->lchild);/递归exchange(t->rchild);p=t->lchild;t->lchild=t->rchild;void inorder(bitree bt)/递归的中序遍历if(bt)inorder(bt->lchild); printf("%d ",bt->data); inorder(bt->r

6、child);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 为真时，执