二叉树的遍历算法
- 格式：doc
- 大小：120.00 KB
- 文档页数：15
二叉树的前序、后序的递归、非递归遍历算法学生姓名：贺天立指导老师：湛新霞摘要本课程设计主要解决树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现。
在课程设计中，系统开发平台为Windows 2000，程序设计设计语言采用Visual C++，程序运行平台为Windows 98/2000/XP。
用除递归算法前序，后续，中序遍历树外还通过非递归的算法遍历树。
程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实际问题。
关键词程序设计；C++；树的遍历；非递归遍历1 引言本课程设计主要解决树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现。
1.1课程设计的任务构造一棵树并输入数据，编写三个函数，非别是树的前序递归遍历算法、树的后序递归遍历算法、树的非递归中序遍历算法（这里的非递归以中序为例）。
在主程序中调用这三个函数进行树的遍历，观察用不同的遍历方法输出的数据的顺序和验证递归与非递归输出的数据是否一样。
1.2课程设计的性质由要求分析知，本设计主要要求解决树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现。
所以设计一个良好的前序、后序的递归、非递归遍历算法非常重要。
1.3课程设计的目的在程序设计中，可以用两种方法解决问题：一是传统的结构化程序设计方法，二是更先进的面向对象程序设计方法[1]。
利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用C语言进行程序设计。
巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。
树的遍历分为前序、中序和后序，可以用递归算法实现树的三种遍历。
除了递归外还可以构造栈，利用出栈和入栈来实现树的前序遍历、中序遍历和后序遍历。
2需求分析（1）根据给定二叉树的先序遍历结果，构造出该二叉树；按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。
（2）给出该二叉树的递归前序和后序遍历结果还有非递归中序遍历结果。
二叉树非递归遍历是用显示栈来存储二叉树的结点指针。
前序遍历时,按二叉树前序遍历的顺序访问结点并将结点的指针入栈,直到栈顶指针指向的结点的左指针域为空时取出栈顶指针并删除栈顶指针,访问刚取出的指针指向的结点的右指针指向的结点并将其指针入栈,如此反复执行且在有标志的情况下实现前序非递归算法。
前序遍历二叉树的递归遍历为若二叉树为空，则算法结束，否则（1）访问根结点，（2）前序遍历左子树，（3）前序遍历右子树。
后序遍历得递归为若二叉树非空，则依次执行如下操作：(1)遍历左子树；(2)遍历右子树；(3)访问根结点。
3 概要设计3.1数据存储结构二叉树的存储结构typedef char DataType;struct BitreeNode{DataType data;BitreeNode *lchild;BitreeNode *rchild;};3.2基本操作T=CreateBitree();//创建树Preorder(T) ;//输出树的前序遍历Postorder(T);//输出树的后序遍历Inorder2(T)；//输出树的非递归中序遍历以下为流程图：4 详细设计4.1数据类型定义二叉树的定义：二叉树的存储结构typedef char DataType;struct BitreeNode{DataType data;//二叉树的数据BitreeNode *lchild;//指向左孩子的指针BitreeNode *rchild;//指向右孩子的指针};4.2系统主要子程序详细设计主程序模块设计及用户工作区模块设计：void main(){struct BitreeNode *T=0;// 定义T为指向BitreeNode类型的指针T=CreateBitree();// 用前序输入法创建二叉树printf("\n前序遍历\n");Preorder(T) ;//用前序递归输入法输出二叉树printf("\n后序遍历\n");Postorder(T);//用后序递归输入法输出二叉树printf("\n中序遍历（非递归)\n");Inorder2(T);//用中序非递归输入法输出二叉树cout<<"\n";DeleteTree(T);//释放二叉树}以下是各子函数的定义：① 创建二叉树//按先序次序输入二叉树BitreeNode *CreateBitree(){ char ch;scanf("%c",&ch);BitreeNode* T=NULL;if(ch!='#'){T= (struct BitreeNode*)(malloc(sizeof(struct BitreeNode)));T->data=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);}}④中序非递归遍历二叉树void Inorder2(BitreeNode *T)// 中序遍历二叉树的非递归算法{BitreeNode *p;BitreeNode * stack[100]; //定义了一个栈的对象Sint top=0;stack[top++]=T; //根结点的指针进栈while (top>0){p= stack[top-1];while (p){stack[top++]= p->lchild ;//往左下走到底p= stack[top-1];}p= stack[--top];// 空指针退栈if (top>0 ){p=stack[--top];cout<<p->data;stack[top++]= p->rchild;//访问结点后向右下一步}}}⑤释放存储空间：void DeleteTree(struct BitreeNode *p){if (p!=NULL){DeleteTree( p->lchild );DeleteTree(p->rchild ) ;free(p);}}5 调试分析系统运行主界面如图5.1所示：在主菜单下，用户输入数据，按回车键。
屏幕显示如下图所示6 总结1. “ 数据结构” 是计算机类各专业的核心课程，也是其他诸多类专业的重要选修课。
我通过学习这门课，可以为理解、应用和开发程序提供技术和方法支持，为后续课程的学习提供重要思想和方法基础。
同时对于我的逻辑思维培养和程序设计思想体系的建立有着重要的影响。
2.在调试过程中，碰到诸多问题，比如定义表长过小，处理记录数量错误时程序的异常，记录冲突次数等等。
处理这些问题异常麻烦，有时连续错误，摸不清头绪，在不断调试，询问老师,和同学探讨之后，终于解决，运行成功。
参考文献[1] 李文军，李师贤，周晓聪. C++作为计算机专业程序设计入门语言的实践与探讨. 计算机科学，1999，26（4）：80～83[2] 唐浩强 . C程序设计（第三版）.清华大学出版社，2005[3]严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社，1997[4] F.Brokken and K.Kubat. C++ Annotations. Version 4.4.0m，ICCE，University of Groningen，Netherlands，1990. 250～280附录：#include"iostream"using namespace std;typedef char DataType;struct BitreeNode{DataType data;BitreeNode *lchild;BitreeNode *rchild;};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);// a=&b;}}//PostorderBitreeNode *CreateBitree()//按先序次序输入二叉树{ char ch;scanf("%c",&ch);BitreeNode* T=NULL;if(ch!='#'){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 * stack[100];//定义了一个栈的对象Sint top=0;stack[top++]=T;//根结点的指针进栈while (top>0){p= stack[top-1];while (p){stack[top++]= p->lchild ;//往左下走到底p= stack[top-1];}p= stack[--top]; // 空指针退栈if (top>0 ){p=stack[--top];cout<<p->data;stack[top++]= p->rchild; //访问结点后向右下一步}//if}//while}void main(){ //Bitree MyBitree;struct BitreeNode *T=0;// T=MyBitree.T;cout<<"请输入一颗二叉树";T=CreateBitree();printf("\n前序遍历\n");Preorder(T) ;printf("\n后序遍历\n");Postorder(T);printf("\n中序遍历（非递归)\n");Inorder2(T);cout<<"\n";DeleteTree(T);}。
