数据结构课程设计二叉树的遍历算法.doc

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.12M 资料格式：doc 举报版权申诉

zcm123456789-2540927-4744302543355929831.doc.pdf-第1页.png

第1页 / 共15页

zcm123456789-2540927-4744302543355929831.doc.pdf-第2页.png

第2页 / 共15页

zcm123456789-2540927-4744302543355929831.doc.pdf-第3页.png

第3页 / 共15页

zcm123456789-2540927-4744302543355929831.doc.pdf-第4页.png

第4页 / 共15页

zcm123456789-2540927-4744302543355929831.doc.pdf-第5页.png

第5页 / 共15页

zcm123456789-2540927-4744302543355929831.doc.pdf-第6页.png

第6页 / 共15页

zcm123456789-2540927-4744302543355929831.doc.pdf-第7页.png

第7页 / 共15页

zcm123456789-2540927-4744302543355929831.doc.pdf-第8页.png

第8页 / 共15页

文本预览

二叉树的前序、后序的递归、非递归遍历算法第 1页二叉树的前序、后序的递归、非递归遍历算法学生姓名：贺天立指导老师：湛新霞摘要本课程设计主要解决树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现。在课程设计中，系统开发平台为 Windows 2000，程序设计设计语言采用 Visual C++，程序运行平台为 Windows 98/2000/XP。用除递归算法前序，后续，中序遍历树外还通过非递归的算法遍历树。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实际问题。关键词程序设计；C++；树的遍历；非递归遍历本课程设计主要解决树的前序、后序的递归、非递归遍历算法，层次序的非递 1 引言归遍历算法的实现。 1.1 课程设计的任务构造一棵树并输入数据，编写三个函数，非别是树的前序递归遍历算法、树的后序递归遍历算法、树的非递归中序遍历算法（这里的非递归以中序为例）。在主程序中调用这三个函数进行树的遍历，观察用不同的遍历方法输出的数据的顺序和验证递归与非递归输出的数据是否一样。 1.2 课程设计的性质由要求分析知，本设计主要要求解决树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现。所以设计一个良好的前序、后序的递归、非递归遍历算法非常重要。 1.3 课程设计的目的在程序设计中，可以用两种方法解决问题：一是传统的结构化程序设计方法，

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

二叉树的前序、后序的递归、非递归遍历算法第 3页 2 需求分析（1）根据给定二叉树的先序遍历结果，构造出该二叉树；按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。（2）给出该二叉树的递归前序和后序遍历结果还有非递归中序遍历结果。二叉树非递归遍历是用显示栈来存储二叉树的结点指针。前序遍历时,按二叉树前序遍历的顺序访问结点并将结点的指针入栈,直到栈顶指针指向的结点的左指针域为空时取出栈顶指针并删除栈顶指针,访问刚取出的指针指向的结点的右指针指向的结点并将其指针入栈,如此反复执行且在有标志的情况下实现前序非递归算法。前序遍历二叉树的递归遍历为若二叉树为空，则算法结束，否则（1）访问根结点，（2）前序遍历左子树，（3）前序遍历右子树。后序遍历得递归为若二叉树非空，则依次执行如下操作：(1)遍历左子树；(2)遍历右子树；(3)访问根结点。

二叉树的前序、后序的递归、非递归遍历算法第 4页 3 概要设计 3.1 数据存储结构二叉树的存储结构 typedef char DataType; struct BitreeNode{ DataType BitreeNode BitreeNode data; *lchild; *rchild; }; 3.2 基本操作 T=CreateBitree(); //创建树 Preorder(T) ; //输出树的前序遍历 Postorder(T); //输出树的后序遍历 Inorder2(T)； //输出树的非递归中序遍历

二叉树的前序、后序的递归、非递归遍历算法第 5页以下为流程图：开始用前序输入法构造一颗二叉树用前序递归算法输出二叉树 Y 用后序递归算法输出二叉树用中序非递归算法输出二叉树 Y 释放二叉树结束

二叉树的前序、后序的递归、非递归遍历算法第 6页 4 详细设计 4.1 数据类型定义二叉树的定义：二叉树的存储结构 typedef char DataType; struct BitreeNode{ DataType data; //二叉树的数据 BitreeNode //指向左孩子的指针 *lchild; BitreeNode *rchild; //指向右孩子的指针 }; 4.2 系统主要子程序详细设计主程序模块设计及用户工作区模块设计： void main() { struct BitreeNode // 定义T为指向BitreeNode类型的指针 T=CreateBitree(); *T=0; // 用前序输入法创建二叉树 printf("\n前序遍历\n"); Preorder(T) ; //用前序递归输入法输出二叉树 printf("\n后序遍历\n"); Postorder(T); //用后序递归输入法输出二叉树 printf("\n中序遍历（非递归)\n"); Inorder2(T);

二叉树的前序、后序的递归、非递归遍历算法第 7页 //用中序非递归输入法输出二叉树 cout<<"\n"; DeleteTree(T); //释放二叉树 } 以下是各子函数的定义： 1 创建二叉树 //按先序次序输入二叉树 BitreeNode *CreateBitree() { char ch; scanf("%c",&ch); BitreeNode* if(ch!='#') { T=NULL; 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 ); } }

二叉树的前序、后序的递归、非递归遍历算法第 8页 ③后序递归遍历二叉树 void Postorder(struct BitreeNode { *p) if (p!=NULL) { Postorder( p->lchild ); Postorder(p->rchild ) ; printf("%c",p->data); } } ④中序非递归遍历二叉树 void Inorder2(BitreeNode *T) // 中序遍历二叉树的非递归算法 { BitreeNode BitreeNode * stack[100]; *p; //定义了一个栈的对象S int 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 ) {

分享到：

赞收藏

资料库

数据结构课程设计二叉树的遍历算法.doc

相关推荐

开发技术

热门标签

最新资料