实现二叉树中所有节点左右子树的交换.doc

数据结构课程设计实验报告题目名称： 实现二叉树中所有节点左右子树的交换 学 院： 信息科学与工程学院 专业班级： 计算机科学与技术 1003 班 姓 名： 叶 成 功 学 号： 12081414 指导教师： 陈国良教授 李立三教授 日 期： 2012年7月3日 目录一、问题描述4二、基本要求4三、数据结构的设计41、结点的数据结构42、基本操作4四、软件模块结构图5五、程序设计思想61、程序设计基本思想62、程序设计基本思想6六、程序流程图71、创建函数72、前序遍历函数83、中序遍历函数94、后序遍历函数105、层序遍历函数116、左右子树交换函数137、二叉树打印函数148、遍历调用函数149、菜单函数1610、主函数16七、源程序代码18八、调试分析25九、数据测试261、主菜单界面272、建立一棵有二十个结点的完全二叉树283、打印二叉树284、遍历二叉树285、二叉树左右子树交换286、交换后打印二叉树297、交换后二叉树的遍历298、退出程序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、前序遍历函数开始结点BTNode是否为空输出根节点前序遍历左子树前序遍历右子树遍历完成结束void PreOrderTraverse(BiTree T) if(T) printf(%c ,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); 3、中序遍历函数开始结点BTNode是否为空中序遍历左子树输出根节点中序遍历右子树遍历完成结束void InOrderTraverse(BiTree T) if(T) InOrderTraverse(T-lchild); printf(%c ,T-data); InOrderTraverse(T-rchild); 4、后序遍历函数开始结点BTNode是否为空后序遍历左子树后序遍历右子树输出结点遍历完成结束void PostOrderTraverse(BiTree T) if(T) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(%c ,T-data); 5、层序遍历函数P=root访问节点P,并将P入队P=P-LChildP为空？N队为空？出队P,P=P-RChild结束YNYvoid LevelOrderTraverse(BiTree T) BiTree QMaxLength; int front=0,rear=0; BiTree p; /根结点入队 if(T) Qrear=T; rear=(rear+1)%MaxLength;/插入结点为新的队尾元素 while(front!=rear) /队头元素出队 p=Qfront; front=(front+1)%MaxLength;/删除头结点 printf(%c ,p-data); /左孩子不为空，入队 if(p-lchild) Qrear=p-lchild;rear=(rear+1)%MaxLength;/插入左孩子结点为新的队尾元素 /右孩子不为空，入队 if(p-rchild) Qrear=p-rchild;rear=(rear+1)%MaxLength;/插入右孩子结点为新的队尾元素 6、左右子树交换函数开始结点BTNode有无子树NY交换子树交换完成结束/交换左右子树（递归算法）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=rchild) c=/; else if(T-lchild)c=;elsec= ; printf(%cn,c); Paint(T-lchild,n+1); 8、遍历调用函数开始输入3后序遍历2中序遍历1前序遍历4 层序遍历结束/遍历函数(调用层序，前序，中序，后序遍历函数)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、主函数开始输入choice0退出3遍历二叉树2打印二叉树1建立二叉树4 交换左右结点结束/*主函数*/根据用户的输入，调用相应的子函数main() BiTree T=NULL; /定义二叉树并默认为空 int choice; while(1) menu(&choice); /显示主菜单 switch(choice) /根据不同选择，实现相应操作 case 1: /创建二叉树 printf(输入各元素，空子树用*表示n); Create(&T); printf(创建成功!nn); break; case 2: /打印二叉树 if(T) printf(打印结果:n); Paint(T,1); else printf(二叉树为空!n); printf(n); break; case 3: /遍历二叉树 if(T) OrderTraverse(T); else printf(二叉树为空!n); printf(n); break; case 4: /交换左右子树 SwapChild(&T); printf(交换成功!n); printf(n); break; case 0: exit(0); /退出 default: printf(无效输入!nn); /*/七、源程序代码/*头文件、宏定义和存储结构*/用到的头文件#include#include/队列最大结点数目#define MaxLength 100 /定义二叉树的存储结构(二叉链表)typedef struct nodechar data;struct node *lchild,*rchild; BiTNode,*BiTree;/*/*各功能函数的定义*/*创建、遍历、交换、打印、主菜单函数*/创建二叉树(前序)void Create(BiTNode *p)char e;e=getchar();if(e=*)(*p)=NULL;elseif(!(*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 QMaxLength;int front=0,rear=0;BiTree p;/根结点入队if(T)Qrear=T;rear=(rear+1)%MaxLength;while(front!=rear)/队头元素出队p=Qfront;front=(front+1)%MaxLength;printf(%c ,p-data);/左孩子不为空，入队if(p-lchild)Qrear=p-lchild;rear=(rear+1)%MaxLength;/右孩子不为空，入队if(p-rchild)Qrear=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=rchild)c=/;elseif(T-lchild)c=;elsec= ;printf(%cn,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(创建成功!nn); 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(无效输入!nn);/*/八、调试分析运行程序，例如：输入如下图所示的有20个结点的完全二叉树。TSR时间复杂度分析：很显然，先序.中序.后序递归算法的复杂度是相同的，递归算法非常的简单。例如先序先访问跟节点，然后访问左节点，再访问右节点。仔细看一下递归程序，就会发现，其实每次都是子树的左子树(lchild)，直到左子树为空，然后开始从递归的最深处返回，然后开始恢复递归现场，访问右子树。其实过程很简单：一直往左走 root-lchild-lchild-lchild.-null，由于是先序遍历，因此一遇到节点，便需要立即访问；由于一直走到最左边后，需要逐步返回到父节点访问右节点，时间方面每个节点调用一次函数，访问一次，是O(n).没有空间开销，所以是0. 中序.后序递归算法同先序一样。时间复杂度是O(n),空间复杂度是0.同理可知中序与后序也是一样的。非递归层序遍历有不一样。层序遍历中每次将节点压入队，然后弹出，再让左子树入队，再让右子树入队，在遍历过程中，左右子树依次入队出队。时间复杂度O(n)，空间复杂度为0。问题一：前序遍历、中序遍历以及后序遍历为递归算法很简单就没什么可说的了，而层次遍历就需要用到队列处理稍微复杂一点。创建二叉树时，要求二叉树内容可以是各种形式，刚开始编创建算法的时候调试总是出错，后来经过参考数据结构相关资料才发现有一个地方少写一行申请空间的代码。问题二：非递归算法在编程时都是不很顺利，其中层序遍历有点难，需要掌握队列的知识，但是经过我不懈努力，最终成功的解决了这个问题。问题三：要注意输入必要的头文件，比如调用malloc需要stdlib.h的头文件，否者编译出错，有时不知道头文件可以查询书本。问题四：在这次课程设计中其实主要问题就是编程完成后会有很多小错误。所以需要耐心调试算法的改进设想：我没有想到更好的算法，我想到的最好的算法编出的C语言程序代码只有100多行，但是可以非常成功的解决了问题。我认为我的算法应该算是最简洁的算法了。九、数据测试数据测试主要是由截图来说明，编译成功后，按照前序遍历的方法输入子树，空子树用*表示，在本程序中输入的是一个有二十个结点的二叉树，输入ABDHP*Q*IR*S*EJT*K*CF