数据结构课程设计实验报告题目名称：实现二叉树中所有节点左右子树的交换学院：信息科学与工程学院专业班级：计算机科学与技术 1003 班姓名：叶成功学号： 12081414 指导教师：陈国良教授李立三教授日期： 2012年7月3日目录一、问题描述 (4)二、基本要求 (4)三、数据结构的设计 (4)1、结点的数据结构 (5)2、基本操作 (5)四、软件模块结构图 (5)五、程序设计思想 (6)1、程序设计基本思想 (6)2、程序设计基本思想 (7)六、程序流程图 (7)1、创建函数 (7)2、前序遍历函数 (8)3、中序遍历函数 (9)4、后序遍历函数 (10)5、层序遍历函数 (11)6、左右子树交换函数 (13)7、二叉树打印函数 (14)8、遍历调用函数 (15)9、菜单函数 (16)10、主函数 (17)七、源程序代码 (19)八、调试分析 (25)九、数据测试 (26)1、主菜单界面 (27)2、建立一棵有二十个结点的完全二叉树 (28)3、打印二叉树 (28)4、遍历二叉树 (28)5、二叉树左右子树交换 (28)6、交换后打印二叉树 (29)7、交换后二叉树的遍历 (29)8、退出程序 (29)十、用户使用手册 (29)十一、心得体会 (29)一、问题描述二叉树是一种常见的特殊的树型结构，在计算机领域有着极为广泛的应用。
在二叉树的一些应用中，常常要求在树中查找具有某些特征的结点或者对树中全部结点逐一进行某种处理，这就提出了遍历二叉树。
根据遍历的方向的不同，有前序遍历、中序遍历、后序遍历以及层序遍历。
在本次课程设计中，要求学生通过编写程序完成对二叉树的一些操作，比如可以构造二叉树、打印二叉树、遍历二叉树以及对左右子树进行交换等等。
二、基本要求要求：。
构造一颗20个节点的完全二叉树或者20个节点以上的满二叉树。
实现如下步骤：（1）实现二叉树的构造过程，并打印出二叉树（2）对该二叉树分别用层序、前序、中序和后序四种不同的方法进行遍历；（3）将该二叉树的所有左右子树进行交换，得到新的二叉树，并打印出该二叉树；（4）对新获得的二叉树分别用层序、前序、中序和后序四种不同的方法进行遍历。
三、数据结构的设计由数据结构中二叉树的定义可知，二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，所以在本程序二叉树的构造是采用二叉链表的链式存储结构，链表中的结点应包含三个域：数据域和左、右孩子的指针域。
这种存储结构可以方便二叉树的建立以及遍历。
1、结点的数据结构struct node{char data;struct node *lchild,*rchild;}2、基本操作void Create(BiTNode **p)初始条件：按照结点的结构体构造二叉树；操作结果：构造一棵二叉树。
void PreOrderTraverse(BiTree T)初始条件：二叉树T存在；操作结果：按照前序遍历方法遍历二叉树。
void InOrderTraverse(BiTree T)初始条件：二叉树T存在；操作结果：按照中序遍历方法遍历二叉树。
void PostOrderTraverse(BiTree T)初始条件：二叉树T存在；操作结果：按照后序遍历方法遍历二叉树。
void LevelOrderTraverse(BiTree T)初始条件：二叉树T存在；操作结果：按照层序遍历方法遍历二叉树。
void SwapChild(BiTNode **p)初始条件：二叉树存在且交换的结点有子树；操作结果：将二叉树左右结点交换。
void Paint(BiTree T)初始条件：二叉树T存在；操作结果：将二叉树的结点打印出来。
四、软件模块结构图1、程序设计基本思想(1)本实验要求编写一个程序实现对二叉树的各种基本操作，并以此为目的设计一个程序，完成如下功能：1、输入二叉树的先序序列字符，建立二叉链表。
注意：输入时，必须加入虚结点以示空指针的位置；假设虚结点输入时用空格字符表示。
2、打印二叉树。
3、按先序、中序、后序和层序三种不同方法遍历二叉树。
4、交换二叉树的所有左右子树。
5、打印二叉树，并且分别按照先序、中序、后序和层序三种不同方法遍历二叉树。
6、在设计一个简单的菜单，分别调试上述算法。
7、编写主程序完成各功能的调用和实现。
(2)测试数据：1、按照先序序列依次输入字符。
2、打印二叉树并且按先序、中序和后序遍历二叉树并输出遍历结果。
3、输出交换二叉树的左右子树并且打印二叉树并且按先序、中序和后序遍历二叉树并输出遍历结果。
2、程序设计基本思想本程序含有7个函数；①主函数main( )②前序遍历二叉树PreOrderTraverse(T,PrintChar)③中序遍历二叉树Inorder(T)④后续遍历二叉树Postorder(T)⑤层序遍历二叉树LevelOrderTraverse(T)⑥打印二叉树Paint（T）⑦交换二叉树所有左右子树SwapChild(T)六、程序流程图1、创建函数void Create(BiTNode **p){char e;e=getchar();if(e=='*')(*p)=NULL;else{if(!((*p)=(BiTree)malloc(sizeof(BiTNode)))) {printf("分配失败\n");exit(0);}(*p)->data=e;Create(&((*p)->lchild));Create(&((*p)->rchild));}}2、前序遍历函数void PreOrderTraverse(BiTree T){if(T){printf("%c ",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}3、中序遍历函数Ｎvoid InOrderTraverse(BiTree T){if(T){InOrderTraverse(T->lchild);printf("%c ",T->data);InOrderTraverse(T->rchild);}}4、后序遍历函数Ｎvoid PostOrderTraverse(BiTree T){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c ",T->data);}}5、层序遍历函数void LevelOrderTraverse(BiTree T){BiTree Q[MaxLength];int front=0,rear=0;BiTree p;//根结点入队if(T){Q[rear]=T;rear=(rear+1)%MaxLength;//插入结点为新的队尾元素}while(front!=rear){//队头元素出队p=Q[front];front=(front+1)%MaxLength;//删除头结点printf("%c ",p->data);//左孩子不为空，入队if(p->lchild){Q[rear]=p->lchild;rear=(rear+1)%MaxLength;//插入左孩子结点为新的队尾元素 }//右孩子不为空，入队if(p->rchild){Q[rear]=p->rchild;rear=(rear+1)%MaxLength;//插入右孩子结点为新的队尾元素 }}}6、左右子树交换函数//交换左右子树（递归算法）void SwapChild(BiTNode **p){BiTNode *temp;if((*p)){//交换左右子树指针temp=(*p)->lchild;(*p)->lchild=(*p)->rchild;(*p)->rchild=temp;SwapChild(&((*p)->lchild));SwapChild(&((*p)->rchild));}}7、二叉树打印函数//打印二叉树（采用凹入表横向打印）void Paint(BiTree T,int n){char c;if(T){Paint(T->rchild,n+1);printf("%*c",4*n,T->data);if(T->lchild&&T->rchild)c='<';elseif(T->rchild)c='/';elseif(T->lchild)c='\\';elsec=' ';printf("%c\n",c);Paint(T->lchild,n+1);}}8、遍历调用函数//遍历函数(调用层序，前序，中序，后序遍历函数) void OrderTraverse(BiTree T){printf("层序遍历: ");LevelOrderTraverse(T);printf("\n");printf("前序遍历: ");PreOrderTraverse(T);printf("\n");printf("中序遍历: ");InOrderTraverse(T);printf("\n");printf("后序遍历: ");PostOrderTraverse(T);printf("\n");}9、菜单函数//主菜单函数（显示系统功能，获取用户输入）void menu(int *choice){printf("-------------欢迎使用-------------\n");printf("1.建立二叉树(前序)\n");printf("2.打印二叉树\n");printf("3.遍历二叉树(层序,前序,中序,后序)\n");printf("4.交换左右子树\n");printf("0.退出\n");printf("----------------------------------\n");printf("你的选择: ");scanf("%d",choice);getchar(); //很重要，存储回车，避免对后面函数的影响}/**************************************************************/10、主函数/***************************主函数****************************/ //根据用户的输入，调用相应的子函数main(){BiTree T=NULL; //定义二叉树并默认为空int choice;while(1){menu(&choice); //显示主菜单switch(choice) //根据不同选择，实现相应操作{case 1: //创建二叉树{printf("输入各元素，空子树用'*'表示\n");Create(&T);printf("创建成功!\n\n");} break;case 2: //打印二叉树{if(T){printf("打印结果:\n");Paint(T,1);}elseprintf("二叉树为空!\n");printf("\n");} break;case 3: //遍历二叉树{if(T)OrderTraverse(T);elseprintf("二叉树为空!\n");printf("\n");} break;case 4: //交换左右子树{SwapChild(&T);printf("交换成功!\n");printf("\n");} break;case 0: exit(0); //退出default: printf("无效输入!\n\n");}}}/****************************************************************/七、源程序代码/********************头文件、宏定义和存储结构********************/ //用到的头文件#include<stdio.h>#include<stdlib.h>//队列最大结点数目#define MaxLength 100//定义二叉树的存储结构(二叉链表)typedef struct node{char data;struct node *lchild,*rchild;} BiTNode,*BiTree;/****************************************************************//*************************各功能函数的定义***********************/ /**************创建、遍历、交换、打印、主菜单函数****************/ //创建二叉树(前序)void Create(BiTNode **p){char e;e=getchar();if(e=='*')(*p)=NULL;else{if(!((*p)=(BiTree)malloc(sizeof(BiTNode)))){printf("分配失败\n");exit(0);}(*p)->data=e;Create(&((*p)->lchild));Create(&((*p)->rchild));}}//递归前序遍历void PreOrderTraverse(BiTree T){if(T){printf("%c ",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}//递归中序遍历void InOrderTraverse(BiTree T){if(T){InOrderTraverse(T->lchild);printf("%c ",T->data);InOrderTraverse(T->rchild);}}//递归后序遍历void PostOrderTraverse(BiTree T){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c ",T->data);}}//层序遍历（利用循环队列）void LevelOrderTraverse(BiTree T) {BiTree Q[MaxLength];int front=0,rear=0;BiTree p;//根结点入队if(T){Q[rear]=T;rear=(rear+1)%MaxLength;}while(front!=rear){//队头元素出队p=Q[front];front=(front+1)%MaxLength;printf("%c ",p->data);//左孩子不为空，入队if(p->lchild){Q[rear]=p->lchild;rear=(rear+1)%MaxLength;}//右孩子不为空，入队if(p->rchild){Q[rear]=p->rchild;rear=(rear+1)%MaxLength;}}}//交换左右子树（递归，类似于先序遍历）void SwapChild(BiTNode **p){BiTNode *temp;if((*p)){//交换左右子树指针temp=(*p)->lchild;(*p)->lchild=(*p)->rchild;(*p)->rchild=temp;SwapChild(&((*p)->lchild));SwapChild(&((*p)->rchild));}}//打印二叉树（采用凹入表横向打印）void Paint(BiTree T,int n){char c;if(T){Paint(T->rchild,n+1);printf("%*c",4*n,T->data);if(T->lchild&&T->rchild)c='<';elseif(T->rchild)c='/';elseif(T->lchild)c='\\';elsec=' ';printf("%c\n",c);Paint(T->lchild,n+1);}}//遍历函数(调用层序，前序，中序，后序遍历函数) void OrderTraverse(BiTree T){printf("层序遍历: ");LevelOrderTraverse(T);printf("\n");printf("前序遍历: ");PreOrderTraverse(T);printf("\n");printf("中序遍历: ");InOrderTraverse(T);printf("\n");printf("后序遍历: ");PostOrderTraverse(T);printf("\n");}//主菜单（显示系统功能，获取用户输入）void menu(int *choice){printf("-------------欢迎使用-------------\n");printf("1.建立二叉树(前序)\n");printf("2.打印二叉树\n");printf("3.遍历二叉树(层序,前序,中序,后序)\n");printf("4.交换左右子树\n");printf("0.退出\n");printf("----------------------------------\n");printf("你的选择: ");scanf("%d",choice);getchar(); //很重要，存储回车，避免对后面函数的影响}/****************************************************************//***************************主函数*******************************/ //根据用户的输入，调用相应的子函数main(){BiTree T=NULL; //定义二叉树并默认为空int choice;while(1){menu(&choice); //显示主菜单switch(choice) //根据不同选择，实现相应操作{case 1: //创建二叉树{printf("输入各元素，空子树用'*'表示\n");Create(&T);printf("创建成功!\n\n");} break;case 2: //打印二叉树{if(T){printf("打印结果:\n");Paint(T,1);}elseprintf("二叉树为空!\n");printf("\n");} break;case 3: //遍历二叉树{if(T)OrderTraverse(T);elseprintf("二叉树为空!\n");printf("\n");} break;case 4: //交换左右子树{SwapChild(&T);printf("交换成功!\n");printf("\n");} break;case 0: exit(0); //退出default: printf("无效输入!\n\n");}}}/****************************************************************/八、调试分析运行程序，例如：输入如下图所示的有20个结点的完全二叉树。