数据结构二叉树的遍历培训讲学.doc

《数据结构二叉树的遍历培训讲学.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构二叉树的遍历精品文档数据结构实验报告班级：学号：姓名：计算机科学与技术学院题目：二叉树的遍历收集于网络，如有侵权请联系管理员删除精品文档一、设计内容从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历。然后将遍历结果输出。先序、中序、后序遍历要求采用递归和非递归实现。ABCDGEF对于如右图所示的二叉树，其扩展的先序遍历序列为：ABD.G..CE..F..（其中小圆点表示空子树）当输入扩展的先序遍历序列：ABD.G..CE..F..输出应该为：层次遍历：ABCDEFG先序遍历：ABDGCEF中序遍历：DGBAECF后续遍历：GDBEFCA二、

2、设计目的1.达到熟练掌握C++语言的基本知识和技能；2.能够利用所学的基本知识和技能，解决简单的面向对象程序设计问题。三、系统分析与设计（确定程序功能模块）1.定义二叉链表存储结构2.以先序遍历建立二叉链表，CreateBiTree(BiTree*bt)3.实现先序遍历二叉树的递归算法，PreOrder(BiTreebt)4实现中序遍历二叉树的递归算法，InOrder(BiTreebt)5.实现后序遍历二叉树的递归算法，PostOrder(BiTreebt)6.实现先序遍历二叉树的非递归算法，NRPreOrder(BiTreebt)7.实现中序遍历二叉树的非递归算法，NRInOrder

3、(BiTreebt)8.实现后序遍历二叉树的非递归算法，NRPostOrder(BiTreebt)9.实现层次遍历二叉树的递归算法，LevelOrder(BiTreebt)收集于网络，如有侵权请联系管理员删除精品文档10.调用各个函数输出遍历结果四、源程序代码#include"iostream.h"#include"stdio.h"#include"malloc.h"typedefstructNode{/*声明二叉树二叉链表节点的结构！*/chardata;structNode*lchild;structNode*rchild;}BiTNode,*BiTree;typedefstruc

4、t{/*定义结构体（将栈中元素的数据类型定义为指针和标志flag合并的结构体类型）*/BiTreelink;intflag;}stacktype;//*************函数声明**************//voidVisite(chara);voidCreateBiTree(BiTree*bt);voidPreOrder(BiTreebt);voidInOrder(BiTreebt);voidPostOrder(BiTreebt);voidNRPreOrder(BiTreebt);voidNRInOrder(BiTreebt);voidNRPostOrder(BiTreebt

5、);voidLevelOrder(BiTreebt);//***********定义函数（访问节点的数据域）**********//voidVisite(chara){cout<

6、front]->data);if(queue[front]->lchild!=NULL){rear++;queue[rear]=queue[front]->lchild;}if(queue[front]->rchild!=NULL){rear++;queue[rear]=queue[front]->rchild;}}}//**********先序遍历建立二叉树***********//voidCreateBiTree(BiTree*bt){charch;ch=getchar();if(ch=='.')*bt=NULL;else收集于网络，如有侵权请联系管理员删除精品文档{*bt=(Bi

7、Tree)malloc(sizeof(BiTNode));(*bt)->data=ch;CreateBiTree(&((*bt)->lchild));CreateBiTree(&((*bt)->rchild));}}//**********递归先序遍历二叉树bt***********//voidPreOrder(BiTreebt){if(bt==NULL)return;cout<data<<"";PreOrder(bt->lchild