下载文档原格式
数据结构二叉树遍历实验报告一、实验目的本次实验的主要目的是深入理解和掌握二叉树的三种遍历方式：前序遍历、中序遍历和后序遍历，并通过实际编程实现来加深对这些遍历算法的理解和应用能力。
二、实验环境本次实验使用的编程语言为 Python，开发工具为 PyCharm。
三、实验原理1、二叉树的定义二叉树是一种每个节点最多有两个子节点的树结构，分别称为左子节点和右子节点。
2、前序遍历前序遍历首先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。
3、中序遍历中序遍历首先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
4、后序遍历后序遍历首先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。
四、实验步骤1、定义二叉树节点类｀｀｀pythonclass TreeNode:def ＿_init__(self, value)：selfvalue ＝ valueselfleft ＝ Noneselfright ＝ None｀｀｀2、实现前序遍历函数｀｀｀pythondef pre_order_traversal(root)：if root is not None:print(rootvalue, end=＂＂）pre_order_traversal(rootleft)pre_order_traversal(rootright)｀｀｀3、实现中序遍历函数｀｀｀pythondef in_order_traversal(root)：if root is not None:in_order_traversal(rootleft) print(rootvalue, end=＂＂）in_order_traversal(rootright)｀｀｀4、实现后序遍历函数｀｀｀pythondef post_order_traversal(root)：if root is not None:post_order_traversal(rootleft) post_order_traversal(rootright) print(rootvalue, end=＂＂）｀｀｀5、构建二叉树并进行遍历｀｀｀python构建二叉树root ＝ TreeNode(1) rootleft ＝ TreeNode(2) rootright ＝ TreeNode(3) rootleftleft ＝ TreeNode(4) rootleftright ＝ TreeNode(5)前序遍历print(＂前序遍历:＂）pre_order_traversal(root) print(）中序遍历print(＂中序遍历:＂）in_order_traversal(root) print(）后序遍历print(＂后序遍历:＂）post_order_traversal(root)print(）｀｀｀五、实验结果1、前序遍历结果：1 2 4 5 32、中序遍历结果：4 2 5 1 33、后序遍历结果：4 5 2 3 1六、结果分析1、前序遍历在前序遍历中，首先访问根节点，然后再访问左子树和右子树。
数据结构二叉树遍历实验报告数据结构二叉树遍历实验报告一、引言本文档旨在详细介绍二叉树遍历的实验过程和结果。
二叉树是一种在计算机科学领域常用的数据结构，通过遍历二叉树可以获取树中的所有节点数据。
本实验将分别介绍前序遍历、中序遍历和后序遍历这三种常见的遍历方法。
二、实验目的本实验的目的是通过实际操作，加深对二叉树遍历方法的理解，并验证这些遍历方法的正确性和效率。
三、实验环境本实验使用的环境如下：●操作系统: Windows 10●开发工具: Visual Studio Code●编程语言: C++四、实验步骤1.创建二叉树数据结构1.1 定义二叉树节点的结构，包含数据和左右子节点指针。
1.2 创建一个二叉树类，包含插入节点、删除节点、查找节点等方法。
1.3 使用已有的数据集构建二叉树，确保树的结构合理。
2.前序遍历前序遍历是先访问根节点，然后递归地遍历左子树和右子树。
2.1 以递归方式实现前序遍历。
2.2 以迭代方式实现前序遍历。
3.中序遍历中序遍历是先遍历左子树，然后访问根节点，最后遍历右子树。
3.1 以递归方式实现中序遍历。
3.2 以迭代方式实现中序遍历。
4.后序遍历后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。
4.1 以递归方式实现后序遍历。
4.2 以迭代方式实现后序遍历。
五、实验结果1.前序遍历结果：[节点1数据] [节点2数据] [节点4数据] [节点5数据] [节点3数据]2.中序遍历结果：[节点4数据] [节点2数据] [节点5数据] [节点1数据] [节点3数据]3.后序遍历结果：[节点4数据] [节点5数据] [节点2数据] [节点3数据] [节点1数据]六、实验分析通过实验结果可以看出，不同的遍历顺序得到的节点顺序也不同。
前序遍历先访问根节点，中序遍历先遍历左子树，后序遍历先遍历右子树。
根据需要，可以选择合适的遍历方法来处理二叉树的节点数据。
七、结论本实验验证了前序遍历、中序遍历和后序遍历的正确性，并且对比了它们的不同。
吉林工程技术师范学院《数据结构》课程设计报告书设计题目：二叉树遍历专业：软件班级：XXX学生姓名：XXX学号：XXX指导教师：XXX2012年12月信息工程学院目录摘要 (I)第一章问题定义 (1)第二章设计思路 (2)第三章数据结构定义 (3)第四章系统功能模块设计 (4)第五章运行与调试 (6)总结 (10)附录 (I)1程序清单 (I)2参考资料 (X)摘要本课设主要实现对二叉树进行的三种次序遍历，输出三种遍历次序的遍历序列。
先序遍历对二叉树进行根左右次序遍历，中序遍历对二叉树进行左根右次序遍历，后续遍历对二叉树进行左右根遍历次序。
采用二叉链表实现各种遍历操作。
关键字：二叉树二叉链表遍历第一章问题定义1.1 课题：建立二叉树，层序、先序、中序、后序遍历（用递归或非递归的方法）以及中序线索化。
1.2意义：通过以前的学习以及查看相关资料，按照题目要求编写程序，进一步加强对编程的训练，使得自己掌握一些将书本知识转化为实际应用当中去，在整个程序中，主要应用的是链表，但也运用了栈。
通过两种方法解决现有问题。
1.3要求：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数；实现二叉树的中序线索化。
第二章设计思路2.1中序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：(1)遍历左子树；(2)访问根结点；(3)遍历右子树。
2.1．先序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：(1) 访问根结点；(2) 遍历左子树；(3) 遍历右子树。
2.2后序遍历得递归算法定义：若二叉树非空，则依次执行如下操作：(1)遍历左子树；(2)遍历右子树；(3)访问根结点。
第三章数据结构定义二叉树定义：二叉树是另一种树形结构，（1）每个节点最多有两颗子树。
(2)子树有左右之分创建二叉树链表的结点存储结构及数据的输入函数。
数据结构课程设计报告
题目：二叉树的遍历
班级：信息与计算科学
姓名：施苏杰
学号:0911080128
1、实验目的
1）学会建立二叉树以及二叉树的遍历。
2）了解递归在函数的运用。
2、实验内容
建立一棵二叉树，并按照先序中序以及后序遍历并输出二叉树。
3、算法分析
1）数据存储结构
struct BiNode{
char data;
BiNode *lchild;
BiNode *rchild;
};
2）整体框架
（1）在输入函数中，以先序遍历输入字符，如果输入的字符不是$，即不为空，则开辟新空间，存入字符，然后输入左子树，不为空继续输入，直到为空，开始输
右子树，以此递归输入。
（2）在先序遍历输出二叉树时，先输出根结点，左子树不为空，则继续输出，若为空则开始输出右子树，以此递归输出，中序遍历，后续遍历同理。
4、数据测试
例：若一棵二叉树为
则输入abd$$eg$$$c$f$$ 1）输入abd$$eg$$$c$f$$
2）输入ab$$c$$
3）输入abc$$$$
5、总结
我觉得在二叉树遍历这个程序中，主要是运用的是递归这个思想，无论是在输入，还是遍历输出一棵二叉树时，都得通过递归来实现，使得程序能够按照一定的规律循环下去。
其次是指针的运用，在结点上以及节点与节点之间的操作。
这个程序相对于一元多项式的相加较为简单，功能也较弱，希望通过以后的学习能够继续完善。
《数据结构》课程设计报告题目：二叉树的遍历日期：2009-12-22年级：班级：姓名：学号：一．实习目的更好的了解二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现流程及操作步骤。
加深理论知识，提高实践能力。
二．问题描述二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，建树的实现。
三．概要设计1.创建二叉树2.二叉树的递归遍历算法<前、中、后）3.二叉树的层次遍历算法4.二叉树的非递归遍历算法<前、中、后）5.退出以选择面板开始，显得更为清晰。
其中3，4，5，6，8为添加内容，有助于更好的了解二叉树。
四．详细设计1.创建二叉树(1>定义二叉树结点值的类型为字符型。
(2>结点个数不超过10个。
(3>按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树。
2.二叉树的递归遍历算法<前、中、后）DLR(1>访问根结点。
(2>先序遍历根结点的左子数。
(3>先序遍历根结点的右子数。
LDR(1>先序遍历根结点的左子数。
(2>访问根结点。
(3>先序遍历根结点的右子数。
LRD(1>先序遍历根结点的左子数。
(2>先序遍历根结点的右子数。
(3>访问根结点。
3.二叉树的层次遍历算法(1>访问该元素所指结点。
(2>若该元素所指结点的左右孩子结点非空，则该元素所指结点的左孩子指针和右孩子指针顺序入队。
4.二叉树的非递归遍历算法<前、中、后）<1）非递归的先序遍历算法a.访问结点的数据域。
b.指针指向p的左孩子结点。
c.从栈中弹出栈顶元素。
d.指针指向p的右孩子结点。
<2）非递归的中序遍历算法a.指针指向p的左孩子结点。
b.从栈中弹出栈顶元素。
c.访问结点的数据域。
d.指针指向p的右孩子结点。
<3）非递归的后序遍历算法bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。
课程设计报告——数据结构题目：二叉排序树姓名：学号：专业：班级：指导老师：年月日目录一、课程设计简介 (3)二、原理分析及流程 (3)2.1、原理分析 (3)2.2、流程图 (4)1、main()函数 (4)2、创建 (4)3、插入 (5)4、查找 (6)5、中序遍历输出 (7)三、算法描述 (8)3.1、存储结构 (8)3.2、插入算法 (8)3.3、查找算法 (9)3.4、删除算法 (10)四、小结与体会 (12)五、程序执行过程 (13)5.1、创建二叉排序树并中序输出 (13)5.2、插入并中序输出 (13)5.3、查找 (14)六、程序清单 (14)一、课程设计简介1.1、题目：二叉排序树相关操作1、创建二叉排序树；2、插入给定值；3、查找给定值；4、删除给定值的结点。
1.2、报告要求：1、封面;2、题目与流程图或模块图;3、程序清单和运行结果;4、小结(收获和体会);5、装订成册。
1.3、目的：课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。
提高学生适应实际，实践编程的能力。
二、原理分析及流程2.1、原理分析：根据题目要求，要实现这些功能，就必须创建一个菜单。
这个菜单设置在main（）函数里面，然后使用while()...switch()语句进行循环调用相关函数，以达到实现相关功能的目的。
2.2、流程图：1、main（）函数：23、插入：4、查找：5、中序遍历输出：三、算法描述3.1、存储结构定义一个链表式的二叉排序树，用链表的方式构造结点，存储二叉排序树中的结点、结点类型和指针类型如下：#include <stdio.h>#define null 0typedef int keytype;typedef struct node{keytype key;struct node *lchild,*rchild;}bstnode,*bstree;3.2、插入算法在二叉排序树中插入一个新节点，首先要查找该节点在二叉排序树中是否已经存在。
二叉树遍历数据结构课程设计以下是为大家整理的二叉树遍历数据结构课程设计的相关范文，本文关键词为二叉,遍历,数据结构,课程,设计,吉林,工程技术,师范学院,，您可以从右上方搜索框检索更多相关文章，如果您觉得有用，请继续关注我们并推荐给您的好友，您可以在综合文库中查看更多范文。
吉林工程技术师范学院《数据结构》课程设计报告书设计题目：二叉树遍历专业：软件班级：xxx学生姓名：xxx学号：xxx指导教师：xxx20XX年12月信息工程学院目录摘要................................................................................I第一章问题定义.........................................................1第二章设计思路.........................................................2第三章数据结构定义.................................................3第四章系统功能模块设计.........................................4第五章运行与调试.....................................................6总结..........................................................................10附录............................................................................I1程序清单...............................................................I2参考资料.. (x)摘要本课设主要实现对二叉树进行的三种次序遍历，输出三种遍历次序的遍历序列。
数据结构二叉树遍历实验报告正文：1.实验目的本实验旨在实现二叉树的四种遍历方式：前序遍历、中序遍历、后序遍历和层次遍历，并对其进行验证和性能评估。
2.实验原理2.1 二叉树的定义二叉树是一种特殊的树状结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。
2.2 二叉树的遍历方式2.2.1 前序遍历前序遍历的顺序是先访问根节点，然后递归地遍历左子树和右子树。
2.2.2 中序遍历中序遍历的顺序是先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。
2.2.3 后序遍历后序遍历的顺序是先递归地遍历左子树和右子树，最后访问根节点。
2.2.4 层次遍历层次遍历按照二叉树的层次从上到下、从左到右的顺序遍历节点。
3.实验内容3.1 实现二叉树的数据结构首先，我们需要定义二叉树的数据结构。
二叉树节点应包含键值和左右子节点的指针。
3.2 实现二叉树的各种遍历方式接下来，我们实现四种遍历方式：前序遍历、中序遍历、后序遍历和层次遍历。
针对每种遍历方式，编写相应的算法实现逻辑。
3.3 实验验证和性能评估使用已实现的算法，对一棵二叉树进行各种遍历方式操作，并将结果输出。
验证输出结果与预期结果是否一致。
同时，记录每种遍历方式的算法时间复杂度和空间复杂度，并进行性能评估。
4.实验结果与分析对于给定的二叉树，分别进行了前序遍历、中序遍历、后序遍历和层次遍历操作，并得到了相应的输出结果。
结果与预期相符。
通过对算法的时间复杂度和空间复杂度的计算和分析，可以看出各种遍历方式的效率和资源消耗情况。
5.结论本实验成功实现了二叉树的四种遍历方式，并验证了其正确性。
同时，对这些遍历方式的性能进行了评估，为后续使用二叉树进行数据操作提供了参考。
附件：无法律名词及注释：- N/A。
##大学数据结构课程设计报告题目：二叉树和树的遍历院（系）：计算机工程学院学生姓名:班级：学号:起迄日期: 2011-6-21至2011-6-25指导教师:2010—2011年度第 2 学期一、需求分析1.问题描述：进行二叉树和树的各种遍历，包括递归和非递归。
2.基本功能二叉树前序递归遍历、二叉树中序递归遍历、二叉树后序递归遍历、二叉树前序非递归遍历、二叉树中序非递归遍历、二叉树后序非递归遍历、二叉树层次非递归遍历树先根递归遍历、树后根递归遍历、树先根非递归遍历、树后根非递归遍历、树层次非递归遍历，可循环执行直到按退出键。
3.输入输出字符串形式二、概要设计1.设计思路：在递归遍历二叉树时，主要看遍历的根的先后，可根据遍历根，遍历左子树和遍历右子树的顺序不同来实现二叉树的先序，中序，后序递归遍历，二叉树的先序和中序非递归则用到了栈，一般都是先根进栈然后左孩子进栈，二叉树的后序遍历则用到了队列，并用tag 数组值0、1来标记二叉树结点的左右，树的先根非递归和后序非递归则参考了二叉树的先序和中序非递归遍历，也用到了栈，它的层次遍历则用到了队列。
2.数据结构设计：//二叉树的结点结构typedef struct bitnode{char data;struct bitnode *lchild,*rchild;}bitnode,* bitree;//二叉树的栈的结构typedef struct{bitree *base;bitree *top;int stacksize;}sqstack;为二叉树的先序和中序非递归提供栈，保存已经访问过的结点信息。
//二叉树后序非递归的栈的结构typedef struct node1{bitree data[30]; //默认30个元素，这里需要一个辅助堆栈！！！int top;}stack;top能够保存结点是左还是右孩子，该栈为后序遍历提供保存结点信息。
//二叉树的队列结点结构typedef struct qnode{bitree data;struct qnode *next;}qnode,*queueptr;//二叉树的队列结构typedef struct{queueptr front;queueptr rear;}linkqueue;该队列能为二叉树层序遍历提供先进先出的数据访问条件//树的结点结构typedef struct csnode{char data;struct csnode *firstchild,*nextsibling;}csnode,*cstree;//树的栈的结构typedef struct{cstree *base;cstree *top;int stacksize;}sqstack1;为树的前根和后根非递归遍历提供保存已经访问过的数据信息//树的队列结点结构typedef struct qnode1{cstree data;struct qnode1 *next;}qnode1,*queueptr1;//树的队列结构typedef struct{queueptr1 front;queueptr1 rear;}linkqueue1;为树的层次遍历提供条件3.软件结构设计：cout<<"1:进行二叉树的操作2:进行树的操作3:退出"<<endl;这是初始界面。
数据结构二叉树遍历实验报告数据结构二叉树遍历实验报告1. 实验目的本实验旨在通过实现二叉树的前序、中序和后序遍历算法，加深对二叉树遍历的理解，并验证算法的正确性。
2. 实验原理2.1 二叉树二叉树是一种特殊的树状数据结构，它的每个节点最多只能有两个子节点。
二叉树可以为空树，也可以是由根节点、左子树和右子树组成的非空树。
2.2 遍历算法二叉树的遍历算法包括前序遍历、中序遍历和后序遍历。
- 前序遍历：先访问根节点，然后依次递归访问左子树和右子树。
- 中序遍历：先递归访问左子树，然后访问根节点，最后递归访问右子树。
- 后序遍历：先递归访问左子树，然后递归访问右子树，最后访问根节点。
3. 实验过程3.1 数据结构设计首先，我们需要设计表示二叉树的数据结构。
在本次实验中，二叉树的每个节点包含三个成员变量：值、左子节点和右子节点。
我们可以使用面向对象编程语言提供的类来实现。
具体实现如下：```pythonclass TreeNode:def __init__(self, val=0, left=None, right=None): self.val = valself.left = leftself.right = right```3.2 前序遍历算法前序遍历算法的实现主要包括以下步骤：1. 若二叉树为空，则返回空列表。
2. 创建一个栈，用于存储遍历过程中的节点。
3. 将根节点入栈。
4. 循环执行以下步骤，直到栈为空：- 弹出栈顶节点，并将其值添加到结果列表中。
- 若当前节点存在右子节点，则将右子节点压入栈。
- 若当前节点存在左子节点，则将左子节点压入栈。
具体实现如下：```pythondef preorderTraversal(root):if not root:return []stack = []result = []stack.append(root)while stack:node = stack.pop()result.append(node.val)if node.right:stack.append(node.right)if node.left:stack.append(node.left)return result```3.3 中序遍历算法中序遍历算法的实现主要包括以下步骤：1. 若二叉树为空，则返回空列表。
数据结构课程设计说明书题目: 遍历二叉树院系：专业班级：学号：学生姓名：同组人：指导教师：年月日目录一、需求分析 (2)1.主功能模块 (2)2.创建树模块 (2)3.遍历树模块 (2)二、概要设计 (3)1.功能设计 (3)（1）创建二叉树 (3)（2）先序递归遍历 (3)（3）中序递归遍历 (3)（4）后序递归遍历 (3)（5）先序非递归遍历 (3)（6）中序非递归遍历 (4)（7）后序非递归遍历 (4)（8）层序非递归遍历 (4)2.算法流程图 (4)三、详细设计 (12)1.界面设计 (12)2.详细代码分析 (14)（1）主模块 (14)（2）创建树模块 (15)（3）遍历树模块 (16)（4）源程序清单 (16)3.调试分析 (35)（1）调试结果 (35)（2）算法分析 (36)四、心得体会 (37)五、参考文献 (38)一、需求分析在现实世界层次化的数据模型中，数据与数据之间的关系纷繁复杂。
其中很多关系无法使用简单的线性结构表示清楚，比如祖先与后代的关系、整体与部分的关系等。
于是人们借鉴自然界中树的形象创造了一种强大的非线性结构——树。
树形结构的具体形式有很多种，其中最常用的就是二叉树。
而二叉树的多层次遍历遍历则是二叉树的重要内容。
本程序用Microsoft Visual C++ 6.0编写，可以实现对二叉树的多种方式的创建、采用递归和非递归等两种方式先序、中序、后序进行遍历。
1.主功能模块通过合理的界面设计，根据提示信息，使用者可以方便快捷地运行本程序来完成创建、遍历二叉树等操作。
界面美观，人性化，程序智能，安全性高。
2.创建树模块当进入程序运行界面后，根据提示输入需要建立的二叉树，共有三种方法来创建二叉树,即：1：广义表构造法、2：先序和中序构造法、3：中序和后序构造法。
建立完二叉树后自动进入下一个功能模块。
3.遍历树模块实现对该二叉树的先序递归遍历、先序非递归遍历、中序递归遍历、中序非递归遍历、后序递归遍历、后序非递归遍历、层序非递归遍历等方式的遍历操作，并输出各遍历序列。
当对该二叉树进行层序非递归遍历时，直接输出该树的逻辑结构图，以便更直观地显示其层次关系。
二、概要设计1.功能设计（1）创建二叉树利用二叉树模板类，创建二叉树时产生类模板，调用类的构造函数来创建，修改二叉树的结构时，可以调用赋值语句直接把广义表转换成二叉树。
相关类或函数如下：class BinaryTree;BinaryTree();BinaryTree<T>& operator=(const string& str);（2）先序递归遍历若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。
相关函数如下：void PreOrderTraverse(const BinaryTreeNode<T>* p) const;（3）中序递归遍历若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。
相关函数如下：void InOrderTraverse(const BinaryTreeNode<T>* p) const;（4）后序递归遍历若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。
相关函数如下：void PostOrderTraverse(const BinaryTreeNode<T>* p) const;（5）先序非递归遍历若二叉树为空，则空操作；否则引入栈模拟递归工作栈，初始时栈为空。
相关函数如下：void PreOrderTraverse() const;（6）中序非递归遍历若二叉树为空，则空操作；否则引入栈模拟递归工作栈，初始时栈为空。
相关函数如下：void InOrderTraverse() const;（7）后序非递归遍历若二叉树为空，则空操作；否则引入栈和标记模拟递归工作栈，初始时栈为空。
相关函数如下：void PostOrderTraverse() const;（8）层序非递归遍历按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。
相关函数如下：void LevelOrderTraverse() const;2.算法流程图图2-1 创建而二叉树图2-2 前序递归遍历图2-3 中序递归遍历图2-4 后序递归遍历图2-5 先序非递归遍历图2-6 中序非递归遍历图2-7 后序非递归遍历图2-8 层序非递归遍历三、详细设计1.界面设计图3-1 系统运行主界面图3-2 创建二叉树界面图3-3 某二叉树层序遍历界面2.详细代码分析（1）主模块本模块定义了系统运行主界面的相关内容和相关操作函数，源代码如下：int main(){system("color A9"); //设置屏幕背景和字体颜色cout<<endl<<endl<<endl<<endl<<endl;cout<<string(35,'*')<<"遍历二叉树"<<string(35,'*')<<endl;cout<<string(31,' ')<<"1：创建二叉树"<<endl;cout<<string(31,' ')<<"2：先序遍历(递归)"<<endl;cout<<string(31,' ')<<"3：先序遍历(非递归)"<<endl;cout<<string(31,' ')<<"4：中序遍历(递归)"<<endl;cout<<string(31,' ')<<"5：中序遍历(非递归)"<<endl;cout<<string(31,' ')<<"6：后序遍历(递归)"<<endl;cout<<string(31,' ')<<"7：后序遍历(非递归)"<<endl;cout<<string(31,' ')<<"8：层序遍历(非递归)"<<endl;cout<<string(31,' ')<<"9：重新显示所有菜单"<<endl;cout<<string(31,' ')<<"0：关闭窗口";if(second>=0){cout<<"(剩"<<setw(2)<<second<<"秒)";}cout<<endl<<endl<<string(80,'*'); while(!isdigit(ch)) //合法性判断{center("您的输入有误，请重新输入：",0);ch=getch();cout<<ch<<endl;}BinaryTree<char> t; //构造空二叉树while(1) //菜单操作无限循环{bool mark=1; //设置重新显示所有菜单时的输出标记switch(ch){...}}}本模块包括两个类——二叉树结点类、二叉树类，源代码如下：class BinaryTreeNode{private:T data; //存储该结点的数据BinaryTreeNode<T> *parent; //存储该结点的父指针BinaryTreeNode<T> *left; //存储该结点的左孩子指针BinaryTreeNode<T> *right; //存储该结点的右孩子指针public:BinaryTreeNode();BinaryTreeNode(const T& t);T GetData() const;bool IsLeftChild() const;bool IsRightChild() const;BinaryTreeNode<T>* GetParent() const;BinaryTreeNode<T>* GetLeftChild() const;BinaryTreeNode<T>* GetRightChild() const;BinaryTreeNode<T>* GetLeftBrother() const;BinaryTreeNode<T>* GetRightBrother() const;void Assign(const T& t);void SetParent(BinaryTreeNode<T>* q);void SetLeftChild(BinaryTreeNode<T>* q);void SetRightChild(BinaryTreeNode<T>* q);~BinaryTreeNode();};class BinaryTree{private:BinaryTreeNode<T>* root; //二叉树根节点public:BinaryTree(); //二叉树构造函数声明bool IsEmpty() const; //二叉树判空函数声明BinaryTreeNode<T>* GetRoot() const; //取得根节点函数声明BinaryTree<T>& operator=(const string& str); //二叉树赋值函数声明~BinaryTree(); //二叉树析构函数声明private:void NodeCounter(const BinaryTreeNode<T>* p,int& sum) const; //统计二叉树结点个数函数声明void Destroy(BinaryTreeNode<T>* p); //二叉树级联释放结点内存函数声明int Depth(const BinaryTreeNode<T>* p) const; //计算二叉树深度函数声明};本模块包括了各种遍历二叉树的函数，源代码如下：void LevelOrderTraverse() const; //二叉树的层序遍历(非递归)成员函数声明void PreOrderTraverse() const; //二叉树的先序遍历(非递归)成员函数声明void PreOrderTraverse(const BinaryTreeNode<T>* p) const; //二叉树的先序遍历(递归)成员函数声明void InOrderTraverse() const; //二叉树的中序遍历(非递归)成员函数声明void InOrderTraverse(const BinaryTreeNode<T>* p) const; //二叉树的中序遍历(递归)成员函数声明void PostOrderTraverse() const; //二叉树的后序遍历(非递归)成员函数声明void PostOrderTraverse(const BinaryTreeNode<T>* p) const; //二叉树的后序遍历(非递归)成员函数声明（4）源程序清单BinaryTreeNode.h#include<cassert>#include<string>#include<stack>template<class T>class BinaryTreeNode{private:T data; //存储该结点的数据BinaryTreeNode<T> *parent; //存储该结点的父指针BinaryTreeNode<T> *left; //存储该结点的左孩子指针BinaryTreeNode<T> *right; //存储该结点的右孩子指针public:BinaryTreeNode();BinaryTreeNode(const T& t);T GetData() const;bool IsLeftChild() const;bool IsRightChild() const;BinaryTreeNode<T>* GetParent() const;BinaryTreeNode<T>* GetLeftChild() const;BinaryTreeNode<T>* GetRightChild() const;BinaryTreeNode<T>* GetLeftBrother() const;BinaryTreeNode<T>* GetRightBrother() const;void Assign(const T& t);void SetParent(BinaryTreeNode<T>* q);void SetLeftChild(BinaryTreeNode<T>* q);void SetRightChild(BinaryTreeNode<T>* q);~BinaryTreeNode();};template<class T>BinaryTreeNode<T>::BinaryTreeNode():data(0),parent(NULL),left(NULL),right(NULL){} template<class T>BinaryTreeNode<T>::BinaryTreeNode(constT&t):data(t),parent(NULL),left(NULL),right(NULL){}template<class T>bool BinaryTreeNode<T>::IsLeftChild() const{return (this==this->parent->GetLeftChild());}template<class T>bool BinaryTreeNode<T>::IsRightChild() const{return (this==this->parent->GetRightChild());}template<class T>T BinaryTreeNode<T>::GetData() const{return data;}template<class T>BinaryTreeNode<T>* BinaryTreeNode<T>::GetParent() const{return parent;}template<class T>BinaryTreeNode<T>* BinaryTreeNode<T>::GetLeftChild() const{return left;}template<class T>BinaryTreeNode<T>* BinaryTreeNode<T>::GetRightChild() const{return right;}template<class T>BinaryTreeNode<T>* BinaryTreeNode<T>::GetLeftBrother() const{assert(IsRightChild());return this->parent->GetLeftChild();}template<class T>BinaryTreeNode<T>* BinaryTreeNode<T>::GetRightBrother() const {assert(IsLeftChild());return this->parent->GetRightChild();}template<class T>void BinaryTreeNode<T>::Assign(const T& t){data=t;}template<class T>void BinaryTreeNode<T>::SetParent(BinaryTreeNode<T>* q){parent=q;}template<class T>void BinaryTreeNode<T>::SetLeftChild(BinaryTreeNode<T>* q) {left=q;}template<class T>void BinaryTreeNode<T>::SetRightChild(BinaryTreeNode<T>* q) {right=q;}template<class T>BinaryTreeNode<T>::~BinaryTreeNode(){}BinaryTree.h#include<iostream>#include<cmath>#include<vector>#include<stack>#include<queue>#include"BinaryTreeNode.h" //二叉树结点模板类头文件using namespace std;const int MAX=1024;template<class T>class BinaryTree{private:BinaryTreeNode<T>* root; //二叉树根节点public:BinaryTree(); //二叉树构造函数声明bool IsEmpty() const; //二叉树判空函数声明BinaryTreeNode<T>* GetRoot() const; //取得根节点函数声明BinaryTree<T>& operator=(const string& str); //二叉树赋值函数声明void LevelOrderTraverse() const; //二叉树的层序遍历(非递归)成员函数声明void PreOrderTraverse() const; //二叉树的先序遍历(非递归)成员函数声明void PreOrderTraverse(const BinaryTreeNode<T>* p) const; //二叉树的先序遍历(递归)成员函数声明void InOrderTraverse() const; //二叉树的中序遍历(非递归)成员函数声明void InOrderTraverse(const BinaryTreeNode<T>* p) const; //二叉树的中序遍历(递归)成员函数声明void PostOrderTraverse() const; //二叉树的后序遍历(非递归)成员函数声明void PostOrderTraverse(const BinaryTreeNode<T>* p) const; //二叉树的后序遍历(非递归)成员函数声明~BinaryTree(); //二叉树析构函数声明private:void NodeCounter(const BinaryTreeNode<T>* p,int& sum) const; //统计二叉树结点个数函数声明void Destroy(BinaryTreeNode<T>* p); //二叉树级联释放结点内存函数声明int Depth(const BinaryTreeNode<T>* p) const; //计算二叉树深度函数声明};template<class T>BinaryTree<T>::BinaryTree():root(NULL){} //二叉树构造函数定义template<class T>BinaryTree<T>& BinaryTree<T>::operator=(const string& str) //二叉树赋值函数定义{Destroy(root);root=NULL;BinaryTreeNode<T> *index[MAX];BinaryTreeNode<T> *p=NULL;int top=-1,sum=0,number=0;int mark=1;for(int i=0;i<str.size();i++){char ch=str[i];switch(ch){case '(':{index[++top]=p;mark=1;break;}case ')':{mark=1;top--;break;}case ',':{mark++;break;}default:{p=new BinaryTreeNode<T>(ch);sum++;if(root==NULL){root=p;}else{if(mark==1){index[top]->SetLeftChild(p);}else if(mark==2){index[top]->SetRightChild(p);}}}}}NodeCounter(root,number);if(sum>number){Destroy(root);root=NULL;}return *this;}template<class T>bool BinaryTree<T>::IsEmpty() const //二叉树判空函数定义{return (root==NULL);}template<class T>BinaryTreeNode<T>* BinaryTree<T>::GetRoot() const //取得根节点函数定义{return root;}template<class T>void BinaryTree<T>::LevelOrderTraverse() const //二叉树的层序遍历(非递归)成员函数定义{if(root==NULL){cout<<string(15,' ')<<"二叉树为空，请先创建二叉树！"<<endl;return;}int sum=Depth(root);queue<BinaryTreeNode<T> *> list;list.push(root);BinaryTreeNode<T> *p=new BinaryTreeNode<T>(' ');int number=1;while(number<=pow(2,sum)-1){BinaryTreeNode<T>* temp=list.front();list.pop();int i=floor(log10(number)/log10(2))+1;int j=number+1-pow(2,i-1);if(number==pow(2,i-1)){cout<<string((81-pow(2,sum))/2+pow(2,sum-i)-1,' ');}else{cout<<string(pow(2,sum-i+1)-1,' ');}cout<<temp->GetData();if(floor(log10(number+1)/log10(2))==log10(number+1)/log10(2)){cout<<endl;}number++;if(temp->GetLeftChild()!=NULL){list.push(temp->GetLeftChild());}elselist.push(p);}if(temp->GetRightChild()!=NULL){list.push(temp->GetRightChild());}else{list.push(p);}}delete p;}template<class T>void BinaryTree<T>::PreOrderTraverse(const BinaryTreeNode<T>* p) const //二叉树的先序遍历(递归)成员函数定义{if(root==NULL){cout<<"二叉树为空，请先创建二叉树！";return;}if(p==NULL){return;}cout<<p->GetData();PreOrderTraverse(p->GetLeftChild());PreOrderTraverse(p->GetRightChild());}template<class T>void BinaryTree<T>::PreOrderTraverse() const //二叉树的先序遍历(非递归)成员函数定义{if(root==NULL){cout<<"二叉树为空，请先创建二叉树！";return;}stack<BinaryTreeNode<T> *> list;BinaryTreeNode<T> *p=root;while(!list.empty() || p!=NULL){while(p!=NULL)list.push(p);cout<<p->GetData();p=p->GetLeftChild();}p=list.top();list.pop();p=p->GetRightChild();}}template<class T>void BinaryTree<T>::InOrderTraverse(const BinaryTreeNode<T>* p) const //二叉树的中序遍历(递归)成员函数定义{if(root==NULL){cout<<"二叉树为空，请先创建二叉树！";return;}if(p==NULL){return;}InOrderTraverse(p->GetLeftChild());cout<<p->GetData();InOrderTraverse(p->GetRightChild());}template<class T>void BinaryTree<T>::InOrderTraverse() const //二叉树的中序遍历(非递归)成员函数定义{if(root==NULL){cout<<"二叉树为空，请先创建二叉树！";return;}stack<BinaryTreeNode<T> *> list;BinaryTreeNode<T> *p=root;while(!list.empty() || p!=NULL){while(p!=NULL){list.push(p);p=p->GetLeftChild();}p=list.top();list.pop();cout<<p->GetData();p=p->GetRightChild();}}template<class T>void BinaryTree<T>::PostOrderTraverse(const BinaryTreeNode<T>* p) const //二叉树的后序遍历(递归)成员函数定义{if(root==NULL){cout<<"二叉树为空，请先创建二叉树！";return;}if(p==NULL){return;}PostOrderTraverse(p->GetLeftChild());PostOrderTraverse(p->GetRightChild());cout<<p->GetData();}template<class T>void BinaryTree<T>::PostOrderTraverse() const //二叉树的后序遍历(非递归)成员函数定义{if(root==NULL){cout<<"二叉树为空，请先创建二叉树！";return;}stack<BinaryTreeNode<T> *> list;BinaryTreeNode<T> *p=root;BinaryTreeNode<T> *q;bool flag;while(!list.empty() || p!=NULL){while(p!=NULL){list.push(p);p=p->GetLeftChild();}q=NULL;flag=1;while(flag && !list.empty()){p=list.top();if(p->GetRightChild()==q){cout<<p->GetData();list.pop();q=p;if(list.empty()){p=NULL;}}else{p=p->GetRightChild();flag=0;}}}}template<class T>BinaryTree<T>::~BinaryTree() //二叉树析构函数定义{Destroy(root);}template<class T>void BinaryTree<T>::Destroy(BinaryTreeNode<T>* p) //二叉树级联释放结点内存函数定义{if(p!=NULL){Destroy(p->GetLeftChild());Destroy(p->GetRightChild());delete p;p=NULL;}}template<class T>void BinaryTree<T>::NodeCounter(const BinaryTreeNode<T>* p,int& sum) const //统计二叉树结点个数函数定义{if(p==NULL){return;}sum++;NodeCounter(p->GetLeftChild(),sum);NodeCounter(p->GetRightChild(),sum);}template<class T>int BinaryTree<T>::Depth(const BinaryTreeNode<T>* p) const //计算二叉树深度函数声明{if(p==NULL){return 0;}int h1=Depth(p->GetLeftChild());int h2=Depth(p->GetRightChild());return h1>h2 ? h1+1 : h2+1;}遍历二叉树.cpp#include<iostream>#include<iomanip>#include<string>#include<ctime>#include<conio.h>#include"BinaryTree.h" //二叉树模板类头文件using namespace std;char limittime(int i); //限时输入函数声明void menu(int second=30); //菜单输出函数声明void center(string str,bool e=1); //居中输出函数声明bool Convert1(string s1,string s2,string& str); //先序和中序转换成广义表函数声明bool Convert2(string s1,string s2,string& str); //中序和后序转换成广义表函数声明int main(){system("color A9"); //设置屏幕背景和字体颜色char ch=limittime(15); //调用限时函数while(!isdigit(ch)) //合法性判断{center("您的输入有误，请重新输入：",0);ch=getch();cout<<ch<<endl;}BinaryTree<char> t; //构造空二叉树while(1) //菜单操作无限循环{bool mark=1; //设置重新显示所有菜单时的输出标记switch(ch){case '1':{if(t.GetRoot()!=NULL) //进行是否要覆盖原二叉树判断{center("您要重新创建二叉树吗？");center("(请按回车键继续创建，其他键返回上一级。
