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

《实现二叉树中所有节点左右子树的交换.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计实验报告题目名称：实现二叉树中所有节点左右子树的交换学院：信息科学与工程学院专业班级：计算机科学与技术1003班姓名：叶成功学号：12081414指导教师：陈国良教授李立三教授日期：2012年7月3日目录一、问题描述4二、基本要求4三、数据结构的设计41、结点的数据结构42、基本操作4四、软件模块结构图5五、程序设计思想61、程序设计基本思想62、程序设计基本思想6六、程序流程图71、创建函数72、前序遍历函数83、中序遍历函数94、后序遍历函数105、层序遍历函数116、左右子树交换函数137、二叉树打印函数148、遍历调用函数149、

2、菜单函数1610、主函数16七、源程序代码18八、调试分析25九、数据测试261、主菜单界面272、建立一棵有二十个结点的完全二叉树283、打印二叉树284、遍历二叉树285、二叉树左右子树交换286、交换后打印二叉树297、交换后二叉树的遍历298、退出程序29十、用户使用手册29十一、心得体会29一、问题描述二叉树是一种常见的特殊的树型结构，在计算机领域有着极为广泛的应用。在二叉树的一些应用中，常常要求在树中查找具有某些特征的结点或者对树中全部结点逐一进行某种处理，这就提出了遍历二叉树。根据遍历的方向的不同，有前序遍历、中序遍历、后序遍历以及层序遍历

3、。在本次课程设计中，要求学生通过编写程序完成对二叉树的一些操作，比如可以构造二叉树、打印二叉树、遍历二叉树以及对左右子树进行交换等等。二、基本要求要求：。构造一颗20个节点的完全二叉树或者20个节点以上的满二叉树。实现如下步骤：（1）实现二叉树的构造过程，并打印出二叉树（2）对该二叉树分别用层序、前序、中序和后序四种不同的方法进行遍历；（3）将该二叉树的所有左右子树进行交换，得到新的二叉树，并打印出该二叉树；（4）对新获得的二叉树分别用层序、前序、中序和后序四种不同的方法进行遍历。三、数据结构的设计由数据结构中二叉树的定义可知，二叉树的结点由一个数据元素

4、和分别指向其左、右子树的两个分支构成，所以在本程序二叉树的构造是采用二叉链表的链式存储结构，链表中的结点应包含三个域：数据域和左、右孩子的指针域。这种存储结构可以方便二叉树的建立以及遍历。1、结点的数据结构structnode{chardata;structnode*lchild,*rchild;}2、基本操作voidCreate(BiTNode**p)初始条件：按照结点的结构体构造二叉树；操作结果：构造一棵二叉树。voidPreOrderTraverse(BiTreeT)初始条件：二叉树T存在；操作结果：按照前序遍历方法遍历二叉树。voidInOrde

5、rTraverse(BiTreeT)初始条件：二叉树T存在；操作结果：按照中序遍历方法遍历二叉树。voidPostOrderTraverse(BiTreeT)初始条件：二叉树T存在；操作结果：按照后序遍历方法遍历二叉树。voidLevelOrderTraverse(BiTreeT)初始条件：二叉树T存在；操作结果：按照层序遍历方法遍历二叉树。voidSwapChild(BiTNode**p)初始条件：二叉树存在且交换的结点有子树；操作结果：将二叉树左右结点交换。voidPaint(BiTreeT)初始条件：二叉树T存在；操作结果：将二叉树的结点打印出来。

6、四、软件模块结构图左右子树交换主函数构造二叉树菜单函数打印二叉树遍历函数层序遍历前序遍历后序遍历中序遍历五、程序设计思想1、程序设计基本思想(1)本实验要求编写一个程序实现对二叉树的各种基本操作，并以此为目的设计一个程序，完成如下功能：1、输入二叉树的先序序列字符，建立二叉链表。注意：输入时，必须加入虚结点以示空指针的位置；假设虚结点输入时用空格字符表示。2、打印二叉树。3、按先序、中序、后序和层序三种不同方法遍历二叉树。4、交换二叉树的所有左右子树。5、打印二叉树，并且分别按照先序、中序、后序和层序三种不同方法遍历二叉树。6、在设计一个简单的菜单，分别

7、调试上述算法。7、编写主程序完成各功能的调用和实现。(2)测试数据：1、按照先序序列依次输入字符。2、打印二叉树并且按先序、中序和后序遍历二叉树并输出遍历结果。3、输出交换二叉树的左右子树并且打印二叉树并且按先序、中序和后序遍历二叉树并输出遍历结果。2、程序设计基本思想本程序含有7个函数；①主函数main()②前序遍历二叉树PreOrderTraverse(T,PrintChar)③中序遍历二叉树Inorder(T)④后续遍历二叉树Postorder(T)⑤层序遍历二叉树LevelOrderTraverse(T)⑥打印二叉树Paint（T）⑦交换二叉树所

8、有左右子树SwapChild(T)六、程序流程图1、创建函数开始输入结点输入为*