完成二叉树中一切节点阁下子树的交换[精华]

完成二叉树中一切节点阁下子树的交换[精华] 题目名称: 实现二叉树中所有节点左右子树的交换 学 院: 信息科学与工程学院 专业班级: 计算机科学与技术 1003 班 姓 名: 叶 成 功 学 号: 12081414 指导教师: 陈国良教授 李立三教授 日 期: 2012年7月3日 目录 一、问题描述........................................................................................ 4 二、基本要求........................................................................................ 4 三、数据结构的设计............................................................................. 5 1、结点的数据结构........................................................................... 5 2、基本操作...................................................................................... 5 四、软件模块结构图............................................................................. 6 五、程序设计思想 ................................................................................ 6 1、程序设计基本思想 ....................................................................... 6 2、程序设计基本思想 ....................................................................... 7 六、程序流程图 .................................................................................... 7 1、创建函数...................................................................................... 7 2、前序遍历函数 .............................................................................. 8 3、中序遍历函数 .............................................................................. 9 4、后序遍历函数 .............................................................................10 5、层序遍历函数 .............................................................................12 6、左右子树交换函数 ......................................................................13 7、二叉树打印函数..........................................................................14 8、遍历调用函数 .............................................................................15 9、菜单函数.....................................................................................16 10、主函数.......................................................................................17 七、源程序代码 ...................................................................................19 八、调试.......................................................................................25 九、数据测试.......................................................................................27 1、主菜单界面 .................................................................................28 2、建立一棵有二十个结点的完全二叉树.........................................28 3、打印二叉树 .................................................................................28 4、遍历二叉树 .................................................................................29 5、二叉树左右子树交换 ..................................................................29 6、交换后打印二叉树 ......................................................................29 7、交换后二叉树的遍历 ..................................................................30 8、退出程序.....................................................................................30 十、用户使用手册 ...............................................................................30 十一、心得体会 ...................................................................................30 一、问题描述 二叉树是一种常见的特殊的树型结构，在计算机领域有着极为广泛的应用。在二叉树的一些应用中，常常要求在树中查找具有某些特征的结点或者对树中全部结点逐一进行某种处理，这就提出了遍历二叉树。根据遍历的方向的不同，有前序遍历、中序遍历、后序遍历以及层序遍历。在本次课程设计中，要求学生通过编写程序完成对二叉树的一些操作，比如可以构造二叉树、打印二叉树、遍历二叉树以及对左右子树进行交换等等。 二、基本要求 要求:。构造一颗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 Y P为空, N 访问节点P,并将P入队 P=P->LChild Y 队为空, N 出队—>P, 结束 P=P->RChild 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、左右子树交换函数 开始 结点 BTNode N 有无子 树 Y 交换子树 交换完成 结束 //交换左右子树(递归算法) void SwapChild(BiTNode **p) { BiTNode *temp; if((*p)) { //交换左右子树指针 temp=(*p)->lchild; (*p)->lchild=(*p)->rchild; >rchild=temp; (*p)- 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='<'; else if(T->rchild) c='/'; else if(T->lchild) c='\\'; else c=' '; printf("%c\n",c); Paint(T->lchild,n+1); } } 8、遍历调用函数 开始 输入 1 2 3 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、主函数 开始 输入 choice 1 2 3 4 0 交 建 打 遍 换 退 立 印 历 左 二 二 二 右 叉 叉 叉 结 树 树 树 点 出 结束 /***************************主函数****************************/ //根据用户的输入，调用相应的子函数 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); } 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("无效输入!\n\n"); } } } /****************************************************************/ 七、源程序代码 /********************头文件、宏定义和存储结构********************/ //用到的头文件 #include #include //队列最大结点数目 #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='<'; else if(T->rchild) c='/'; else if(T->lchild) c='\\'; else c=' '; 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); } 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("无效输入!\n\n"); } } } /****************************************************************/ 八、调试分析 运行程序，例如:输入如下图所示的有20个结点的完全二叉树。 R S T 时间复杂度分析: 很显然，先序.中序.后序递归算法的复杂度是相同的，递归算法非常的简单。例如先序先访问跟节点，然后访问左节点，再访问右节点。仔细看一下递归程序，就会发现，其实每次都是子树的左子树(lchild)，直到左子树为空，然后开始从递归的最深处返回，然后开始恢复递归现场，访问右子树。其实过程很简单:一直往左走 root->lchild->lchild->lchild...->null，由于是先序遍历，因此一遇到节点，便需要立即访问;由于一直走到最左边后，需要逐步返回到父节点访问右节点，时间方面每个节点调用一次函数，访问一次，是O(n).没有空间开销，所以是0. 中序.后序递归算法同先序一样。时间复杂度是O(n),空间复杂度是0.同理可知中序与后序也是一样的。 非递归层序遍历有不一样。层序遍历中每次将节点压入队，然后弹出，再让左子树入队，再让右子树入队，在遍历过程中，左右子树依次入队出队。时间复杂度O(n)，空间复杂度为0。 问题一:前序遍历、中序遍历以及后序遍历为递归算法很简单就没什么可说的了，而层次遍历就需要用到队列处理稍微复杂一点。创建二叉树时，要求二叉树

内容

财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容

可以是各种形式，刚开始编创建算法的时候调试总是出错，后来经过参考数据结构相关资料才发现有一个地方少写一行申请空间的代码。 问题二:非递归算法在编程时都是不很顺利，其中层序遍历有点难，需要掌握队列的知识，但是经过我不懈努力，最终成功的解决了这个问题。 问题三:要注意输入必要的头文件，比如调用malloc需要stdlib.h的头文件，否者编译出错，有时不知道头文件可以查询

书

关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf

本。 问题四:在这次课程设计中其实主要问题就是编程完成后会有很多小错误。所以需要耐心调试 算法的改进设想: 我没有想到更好的算法，我想到的最好的算法编出的C语言程序代码只有100多行，但是可以非常成功的解决了问题。我认为我的算法应该算是最简洁的算法了。 九、数据测试 数据测试主要是由截图来说明，编译成功后，按照前序遍历的方法输入子树，空子树用*表示，在本程序中输入的是一个有二十个结点的二叉树，输入ABDHP**Q**IR**S**EJT***K**CFL**M**GN**O**, 则构成一棵拥有二十个结点的完全二叉树，如图: R S T 输入二叉树后，分别调用打印函数、前序遍历函数、中序遍历函数、后序遍历函数以及层次遍历函数，在功能实现后。调换二叉树所有的左右子树，再分别调用打印函数、前序遍历函数、中序遍历函 数、后序遍历函数以及层次遍历函数。所有功能都实现后，退出程序。 程序运行中的截图如下所示。 1、主菜单界面 2、建立一棵有二十个结点的完全二叉树 3、打印二叉树 4、遍历二叉树 5、二叉树左右子树交换 6、交换后打印二叉树 7、交换后二叉树的遍历 8、退出程序 十、用户使用手册 十一、心得体会 为期两周的课程设计结束了，在这次的课程设计中我们将抽象的数据结构理论知识与大一所学的C语言相结合，完成了这次课程设计。在完成这个课程设计的过程中，从问题分析、程序设计以及程序调试每个环节都必须要做到完美，因为这几环都是环环相扣的，只有在前一环做好的情况下才能完好的做第二步 课程设计是我们专业课程知识综合应用的实践训练，着是我们迈向社会，从事职业工作前一个必不少的过程(”千里之行始于足下”，通过这次课程设计，我深深体会到这句千古名言的真正含义(我今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳健地在社会大潮中奔跑打下坚实的基础( 通过这次程序设计，我在许多方面都有所提高。通过这次课程设计，综合运用本专业所学课程:数据结构与C语言程序的理论知识，同时也将相关的理论知识都有了全面的复习，独立思考的能力也有了提高。 在这次设计过程中，体现出自己单独设计程序的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补。 在此感谢我们的所有的课程设计的指导老师.，老师严谨细致、一丝不苟的作风一直是我工作、学习中的榜样;老师循循善诱的教导和不拘一格的思路给予我无尽的启迪;这次课程设计中遇到了各种各样的困难，有些不能自己解决的都得到老师您的细心指导。而您开朗的个性和宽容的态度，也帮助我能够很顺利的完成了这次课程设计。 同时感谢对我帮助过的同学们，谢谢你们对我的帮助和支持，让我感受到同 学的友谊。