二叉树的遍历算法

1、二叉树的前序、后序的递归、非递归遍历算法学生姓名：贺天立 指导老师：湛新霞摘 要 本课程设计主要解决树的前序、后序的递归、非递归遍历算法，层次序 的非递归遍历算法的实现。在课程设计中，系统开发平台为 Windows 2000，程 序设计设计语言采用Visual C+，程序运行平台为Windows 98/2000/XP。用除 递归算法前序，后续，中序遍历树外还通过非递归的算法遍历树。程序通过调试 运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实 际问题。关键词程序设计；C+ ；树的遍历；非递归遍历引 言本课程设计主要解决树的前序、后序的递归、非递归遍历算法，层次序的非递 归

2、遍历算法的实现。课程设计的任务构造一棵树并输入数据，编写三个函数，非别是树的前序递归遍历算法、树的 后序递归遍历算法、树的非递归中序遍历算法（这里的非递归以中序为例）。在 主程序中调用这三个函数进行树的遍历，观察用不同的遍历方法输出的数据的顺 序和验证递归与非递归输出的数据是否一样。课程设计的性质由要求分析知，本设计主要要求解决树的前序、后序的递归、非递归遍历算 法，层次序的非递归遍历算法的实现。所以设计一个良好的前序、后序的递归、 非递归遍历算法非常重要。课程设计的目的在程序设计中，可以用两种方法解决问题：一是传统的结构化程序设计方法，二是更先进的面向对象程序设计方法1。利用数据结构课程的相

3、关知识完成一个具有一定难度的综合设计题目， 利用C语言进行程序设计。巩固和加深对线性表、栈、队列、字符串、树、图、 查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括 问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分 析解决综合性实际问题的基本能力。树的遍历分为前序、中序和后序，可以用递归算法实现树的三种遍历。除了 递归外还可以构造栈，利用出栈和入栈来实现树的前序遍历、中序遍历和后序遍 历。需求分析（1）根据给定二叉树的先序遍历结果，构造出该二叉树； 按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。（2）给出该二叉树的递归前序和后序遍历结

4、果还有非递归中序遍历结果。二叉树非递归遍历是用显示栈来存储二叉树的结点指针。前序遍历时,按二叉树前序 遍历的顺序访问结点并将结点的指针入栈,直到栈顶指针指向的结点的左指针域为空时取出 栈顶指针并删除栈顶指针,访问刚取出的指针指向的结点的右指针指向的结点并将其指针入 栈,如此反复执行且在有标志的情况下实现前序非递归算法。前序遍历二叉树的递归遍历为 若二叉树为空，则算法结束，否则（1）访问根结点，（2）前序遍历左子树，（3）前序遍历 右子树。后序遍历得递归为若二叉树非空，则依次执行如下操作：（1）遍历左子树；（2）遍历 右子树；（3）访问根结点。概要设计3.1 数据存储结构二叉树的存储结构type

5、def char DataType;struct BitreeNodeDataTypedata;BitreeNode*lchild;BitreeNode*rchild;3.2 基本操作T=CreateBitree();/创建树Preorder(T) ;/输出树的前序遍历Postorder(T);/输出树的后序遍历Inorder2(T)；/输出树的非递归中序遍历以下为流程图：详细设计4.1 数据类型定义二叉树的定义：二叉树的存储结构typedef char DataType;struct BitreeNodeDataType data;/二叉树的数据BitreeNode*lchild;/指向左孩

6、子的指针BitreeNode*rchild;/指向右孩子的指针;4.2 系统主要子程序详细设计主程序模块设计及用户工作区模块设计： void main()struct BitreeNode*T=0;/定义T为指向BitreeNode类型的指针T=CreateBitree();/ 用前序输入法创建二叉树prin tf( n 前序遍历n);Preorder(T) ;/用前序递归输入法输出二叉树prin tf( n 后序遍历n);Postorder(T); /用后序递归输入法输出二叉树 prin tf( n中序遍历(非递归)n);Inorder2(T);/用中序非递归输入法输出二叉树coutdata

7、=ch;T-lchild=CreateBitree();T-rchild=CreateBitree();return T;先序递归遍历二叉树：void Preorder(struct BitreeNode *p) if (p!=NULL)printf(%c,p-data);Preorder( p-lchild );Preorder(p-rchild );后序递归遍历二叉树void Postorder(struct BitreeNode *p) if (p!=NULL)Postorder( p-lchild ); Postorder(p-rchild ) ; printf(%c,p-data);

8、中序非递归遍历二叉树void Inorder2(BitreeNode *T)/ 中序遍历二叉树的非递归算法BitreeNode *p;BitreeNode * stack100;/定义了一个栈的对象sint top=0;stacktop+=T; /根结点的指针进栈while (top0)p= stacktop-1;while (p)stacktop+= p-lchild/往左下走到底p= stacktop-1;p= stack-top;/ 空指针退栈if (top0 )p=stack-top; coutdata; stacktop+= p-rchild;/访问结点后向右下一步 释放存储空间：v

9、oid DeleteTree(struct BitreeNode *p) if (p!=NULL)DeleteTree( p-lchild ); DeleteTree(p-rchild ) ; free(p);调试分析系统运行主界面如图 5.1 所示：caw乩已（亡请输入一颗二叉树在主菜单下，用户输入数据，按回车键。屏幕显示如下图所示S3血 CAWi nd Dws5ystem32cmd .exeS3晴输入颗二叉树孔皿F删9丼丼网序遍历abedefg 辰序遍历 edbfgea 用序遍历（非递归 cbdafeg请按任意键继续 总结“ 数据结构 ” 是计算机类各专业的核心课程，也是其他诸多类专业的重

10、 要选修课。我通过学习这门课，可以为理解、应用和开发程序提供技术和方法支 持，为后续课程的学习提供重要思想和方法基础。同时对于我的逻辑思维培养和 程序设计思想体系的建立有着重要的影响。在调试过程中，碰到诸多问题，比如定义表长过小，处理记录数量错误时 程序的异常，记录冲突次数等等。处理这些问题异常麻烦，有时连续错误，摸不 清头绪，在不断调试，询问老师,和同学探讨之后，终于解决，运行成功。参考文献李文军，李师贤，周晓聪.C+作为计算机专业程序设计入门语言的实践与探讨.计算机科学，1999, 26 （4）： 8083唐浩强 C程序设计（第三版）清华大学出版社，2005严蔚敏，吴伟民数据结构（C语言版

11、）清华大学出版社，1997F. Brokken and K. Kubat.C+ Annotations. Version 4.4.0m， ICCE，University of Groningen， Netherlands, 1990. 250280附录：#includeiostream using namespace std; typedef char DataType; struct BitreeNodeDataTypedata;BitreeNode*lchild;BitreeNode*rchild;void Preorder(struct BitreeNode *p) / 先序遍历二叉树i

12、f (p!=NULL) printf(%c,p-data); Preorder( p-lchild ); Preorder(p-rchild );void Postorder(struct BitreeNode *p) / 后序遍历二叉树if (p!=NULL)Postorder( p-lchild ); Postorder(p-rchild ) ; printf(%c,p-data);/ a=&b;/PostorderBitreeNode *CreateBitree() /按先序次序输入二叉树 char ch;scanf(%c,&ch);BitreeNode* T=NULL;if(ch!=#

13、)T= (struct BitreeNode*)(malloc(sizeof(struct BitreeNode); T-data=ch;T-lchild=CreateBitree();T-rchild=CreateBitree();return T;void DeleteTree(struct BitreeNode *p)/ 释放存储空间if (p!=NULL)DeleteTree( p-lchild );DeleteTree(p-rchild ) ; free(p);/Postordervoid Inorder2(BitreeNode *T)/ 中序遍历二叉树的非递归算法BitreeNode *p;BitreeNode * stack100;/定义了一个栈的对象sint top=0; stacktop+=T;/根结点的指针进栈while (top0)p= stacktop-1;while (p)stacktop+= p-lchild ;/往左下走到底p= stacktop-1;p= stack-top;/ 空指针退栈if (top0 )p=stack-top; coutdata; stacktop+= p-rchild;/访问结点后向右下一步/if/wh