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

1、实现二叉树中所有节点左右子树的交换数据结构课程设计实验报告JtNGGANGSHANUNIVERSITY题目名称：实现二叉树中所有节点左右子树的交换学院：信息科学与工程学院专业班级：计算机科学与技术1003班姓名：叶成功学号：12081414指导教师：陈国良教授李立三教授日期：2021年7月3日目录问题描述5二、根本要求6三、数据结构的设计71、结点的数据结构72、根本操作7四、软件模块结构图8五、程序设计思想81、程序设计根本思想82、程序设计根本思想9六、程序流程图91、创立函数92、前序遍历函数113、中序遍历函数124、后序遍历函数135、层序遍历函数156、左右子树交换函数167、二叉

2、树打印函数188、遍历调用函数189、菜单函数2110、主函数21七、源程序代码24八、调t分析36九、数据测试381、主菜单界面392、建立一棵有二十个结点的完全二叉树393、打印二叉树394、遍历二叉树405、二叉树左右子树交换406、交换后打印二叉树407、交换后二叉树的遍历408、退出程序41十、用户使用手册41十一、心得体会41一、问题描述在计算机领域有着极为广泛的应用.在二叉树的一些应用中,常常要求在树中查找具有某些特征的结点或者对树中全部结点逐一进行某种处理,这就提出了遍历二叉树.根据遍历的方向的不同,有前序遍历、中序遍历、后序遍历以及层序遍历.在本次课程设计中,要求学生通过编写

3、程序完成对二叉树的一些操作,比方可以构造二叉树、打印二叉树、遍历二叉树以及对左右子树进行交换等等.二、根本要求要求：.构造一颗20个节点的完全二叉树或者20个节点以上的满二叉树.实现如下步骤：(1)实现二叉树的构造过程,并打印出二叉树(2)对该二叉树分别用层序、前序、中序和后序四种不同的方法进行遍历；(3)将该二叉树的所有左右子树进行交换,得到新的二叉树,并打印出该二叉树；(4)对新获得的二叉树分别用层序、前序、中序和后序四种不同的方法进行遍历O三、数据结构的设计由数据结构中二叉树的定义可知,二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成,所以在本程序二叉树的构造是采用二叉链表

4、的链式存储结构,链表中的结点应包含三个域：数据域和左、右孩子的指针域.这种存储结构可以方便二叉树的建立以及遍历.1、结点的数据结构structnode(chardata;structnode*lchild,*rchild;)2、根本操作voidCreate(BiTNode*p)初始条件：根据结点的结构体构造二叉树；操作结果：构造一棵二叉树.voidPreOrderTraverse(BiTreeT)初始条件：二叉树T存在；操作结果：根据前序遍历方法遍历二叉树.voidInOrderTraverse(BiTreeT)初始条件：二叉树T存在；操作结果：根据中序遍历方法遍历二叉树.voidPostOr

5、derTraverse(BiTreeT)初始条件：二叉树T存在；操作结果：根据后序遍历方法遍历二叉树.voidLevelOrderTraverse(BiTreeT)初始条件：二叉树T存在；操作结果：根据层序遍历方法遍历二叉树.voidSwapChild(BiTNode*p)初始条件：二叉树存在且交换的结点有子树；操作结果：将二叉树左右结点交换.voidPaint(BiTreeT)初始条件：二叉树T存在；操作结果：将二叉树的结点打印出来四、软件模块结构图1、程序设计根本思想(1)本实验要求编写一个程序实现对二叉树的各种根本操作,并以此为目的设计一个程序,完成如下功能：1 、输入二叉树的先序序列字

6、符,建立二叉链表.注意：输入时,必须参加虚结点以示空指针的位置；假设虚结点输入时用空格字符表示.2 、打印二叉树.3 、按先序、中序、后序和层序三种不同方法遍历二叉树.4 、交换二叉树的所有左右子树.5 、打印二叉树,并且分别根据先序、中序、后序和层序三种不同方法遍历二叉树.6 、在设计一个简单的菜单,分别调试上述算法.7 、编写主程序完成各功能的调用和实现.(2)测试数据：1、根据先序序列依次输入字符.2 、打印二叉树并且按先序、中序和后序遍历二叉树并输出遍历结果.3 、输出交换二叉树的左右子树并且打印二叉树并且按先序、中序和后序遍历二叉树并输出遍历结果.2、程序设计根本思想本程序含有7个函

7、数；主函数main()前序遍历二叉树PreOrderTraverse(T,PrintChar)中序遍历二叉树Inorder(T)后续遍历二叉树Postorder(T)层序遍历二叉树LevelOrderTraverse(T)打印二叉树Paint(T)交换二叉树所有左右子树SwapChild(T)六、程序流程图1、创立函数voidCreate(BiTNode*p)(chare;e=getchar();if(e='*')(*p)=NULL;else(if(!(*p)=(BiTree)malloc(sizeof(BiTNode)(printf("分配失败n");ex

8、it(0);(*p)->data=e;Create(&(*p)->lchild);Create(&(*p)->rchild);2、前序遍历函数输出根节点前序遍历专了前序遍力布于遍历完成voidPreOrderTraverse(BiTreeT)(if(T)(printf("%c",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);3、中序遍历函数中序遍历4子输出根节;点中序遍历,丁子遍历.完成公结voidInOrderTraverse(BiTre

9、eT)(if(T)(InOrderTraverse(T->lchild);printf("%c",T->data);InOrderTraverse(T->rchild);4、后序遍历函数后序遍历年子后序遍历有子输出结思二遍历完曲结voidPostOrderTraverse(BiTreeT)(if(T)(PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c",T->data);)5、层序遍历'函数voidLevelOrderTra

10、verse(BiTreeT)(BiTreeQMaxLength;intfront=0,rear=0;BiTreep;/根结点入队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;/插入左孩子结点为新的队尾元素)/右孩子

11、不为空,入队if(p->rchild)(Qrear=p->rchild;rear=(rear+1)%MaxLength;/插入右孩子结点为新的队尾元素)6、左右子树交换函数/交换左右子树(递归算法)voidSwapChild(BiTNode*p)(BiTNode*temp;if(*p)(/交换左右子树指针temp=(*p)->lchild;(*p)->lchild=(*p)->rchild;(*p)->rchild=temp;SwapChild(&(*p)->lchild);SwapChild(&(*p)->rchild);7、二

12、叉树打印函数/打印二叉树(采用凹入表横向打印)voidPaint(BiTreeT,intn)(charc;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("%cn",c);Paint(T->lchild,n+1)

13、;8、遍历调用函数输/1、心刖序遍遍历函数(调用层序,前序,中序,后序遍历函数)voidOrderTraverse(BiTreeT)(printf("层序遍历:");LevelOrderTraverse(T);printf("n");printf("前序遍历:");PreOrderTraverse(T);printf("n");printf("中序遍历:");InOrderTraverse(T);printf("n");printf("后序遍历:");Po

14、stOrderTraverse(T);printf("n");9、菜单函数/主菜单函数显示系统功能,获取用户输入voidmenuint*choiceprintf"欢送使用n"printf"1.建立二叉树前序n"printf"2.打印二叉树n"printf"3.遍历二叉树层序,前序,中序,后序n"printf"4.交换左右子树n"printf"0.退出n"printf"n"printf"你的选择："scanf"

15、;%d",choice;getchar;/很重要,存储回车,防止对后面函数的影响产*10、主函数产*主函数*/根据用户的输入,调用相应的子函数main()(BiTreeT=NULL;/定义二叉树并默认为空intchoice;while(1)(menu(&choice);/显示主菜单switch(choice)/根据不同选择,实现相应操作(case 1: /创立二叉树(printf("输入各元素,空子树用'*'表示n");Create(&T);printf("创立成功!nn");break;case 2: /打印二

16、叉树(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;case0:

17、exit(0);/退出default:printf("无效输入!nn");/*七、源程序代码/*结构*/用到的头文件#include<stdio.h>头文件、宏定义和存储#include<stdlib.h>队列最大结点数目#defineMaxLength100定义二叉树的存储结构二叉链表typedefstructnodechardata;structnode*lchild,*rchild;BiTNode,*BiTree;/*各功能函数的定/*义*/菜单函数*/*创立、遍历、交换、打印、H创立二叉树(前序)voidCreate(BiTNode*p)(c

18、hare;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);递归前序遍历voidPreOrderTraverse(BiTreeT)(if(T)(printf("%c",T->data);PreOrderTraverse(T->lchi

19、ld);PreOrderTraverse(T->rchild);)递归中序遍历voidInOrderTraverse(BiTreeT)(if(T)(InOrderTraverse(T->lchild);printf("%c",T->data);InOrderTraverse(T->rchild);)递归后序遍历voidPostOrderTraverse(BiTreeT)(if(T)(PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c"

20、,T->data);)层序遍历(利用循环队列)voidLevelOrderTraverse(BiTreeT)(BiTreeQMaxLength;intfront=0,rear=0;BiTreep;/根结点入队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)%MaxLen

21、gth;右孩子不为空,入队if(p->rchild)(Qrear=p->rchild;rear=(rear+1)%MaxLength;)交换左右子树(递归,类似于先序遍历)voidSwapChild(BiTNode*p)(BiTNode*temp;if(*p)(交换左右子树指针temp=(*p)->lchild;(*p)->lchild=(*p)->rchild;(*p)->rchild=temp;SwapChild(&(*p)->lchild);SwapChild(&(*p)->rchild);)打印二叉树(采用凹入表横向打印)

22、voidPaint(BiTreeT,intn)(charc;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("%cn",c);Paint(T->lchild,n+1);)遍历函数(调用层序,前序,中序,后序遍历函数)voidOrd

23、erTraverse(BiTreeT)printf("层序遍历:");LevelOrderTraverse(T);printf("n");printf("前序遍历:");PreOrderTraverse(T);printf("n");printf("中序遍历:");InOrderTraverse(T);printf"后序遍历:"PostOrderTraverseT;printf"n"主菜单显示系统功能,获取用户输入voidmenuint*choicepri

24、ntf"欢送使用n"printf"1.建立二叉树前序n"printf"2.打印二叉树n"printf"3.遍历二叉树层序,前序,中序,后序n"printf"4.交换左右子树n"printf"0.退出n"printf"n"printf"你的选择:"scanf"%d",choice;getchar;很重要存储回车防止对后面函数的影响/*/*/根据用户的输入,调用相应的子函数main()(BiTreeT=NULL;空定义二

25、叉树并默认为intchoice;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");br

26、eak;case 3: 遍历二叉树(if(T)OrderTraverse(T);elseprintf("二叉树为空!n");printf("n");break;case 4: 交换左右子树(SwapChild(&T);printf("交换成功！n");printf("n");break;case0:exit(0);/退出default:printf("无效输入!nn");)/*/八、调试分析运行程序,例如：输入如下列图所示的有20个结点的完全二叉树时间复杂度分析:很显然,先序.中序.后序

27、递归算法的复杂度是相同的,递归算法非常的简单.例如先序先访问跟节点,然后访问左节点,再访问右节点.仔细看一下递归程序,就会发现,其实每次都是子树的左子树(Ichild),直到左子树为空,然后开始从递归的最深处返回,然后开始恢复递归现场,访问右子树.其实过程很简单：一直往左走root->lchild->lchild->lchild.->null,由于是先序遍历,因此一遇到节点,便需要立即访问；由于一直走到最左边后,需要逐步返回到父节点访问右节点,时间方面每个节点调用一次函数,访问一次,是O(n).没有空间开销,所以是0.中序.后序递归算法同先序一样.时间复杂度是O(n),

28、空间复杂度是0.同理可知中序与后序也是一样的.非递归层序遍历有不一样.层序遍历中每次将节点压入队,然后弹出,再让左子树入队,再让右子树入队,在遍历过程中,左右子树依次入队出队.时间复杂度O(n),空间复杂度为00问题一：前序遍历、中序遍历以及后序遍历为递归算法很简单就没什么可说的了,而层次遍历就需要用到队列处理稍微复杂一点.创立二叉树时,要求二叉树内容可以是各种形式,刚开始编创立算法的时候调试总是出错,后来经过参考数据结构相关资料才发现有一个地方少写一行申请空间的代码.问题二：非递归算法在编程时都是不很顺利,其中层序遍历有点难,需要掌握队列的知识,但是经过我不懈努力,最终成功的解决了这个问题.

29、问题三：要注意输入必要的头文件,比方调用malloc需要stdlib.h的头文件,否者编译出错,有时不知道头文件可以查询书本.问题四：在这次课程设计中其实主要问题就是编程完成后会有很多小错误.所以需要耐心调试算法的改良设想：我没有想到更好的算法,我想到的最好的算法编出的C语言程序代码只有100多行,但是可以非常成功的解决了问题.我认为我的算法应该算是最简洁的算法了.九、数据测试数据测试主要是由截图来说明,编译成功后,根据前序遍历的方法输入子树,空子树用*表示,在本程序中输入的是一个有二十个结点的二叉树,输入ABDHP*Q*IR*S*EJT*K*CFL*M*GN*O*,那么构成一棵拥有二十个结点的完全二叉树,如图：输入二叉树后,分别调用打印函数、前序遍历函数、中序遍历函数、后序遍历函数以及层次遍历函数,在功能实现后.调换二叉树所有的左右子树,再分别调用打印函数