数据结构二叉树的遍历

1、精选优质文档-倾情为你奉上数据结构实验报告班级：学号：姓名：计算机科学与技术学院 题目：二叉树的遍历一、设计内容 从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历。然后将遍历结果输出。先序、中序、后序遍历要求采用递归和非递归实现。ABCDGEF对于如右图所示的二叉树，其扩展的先序遍历序列为：A B D . G . . C E . . F . .（其中小圆点表示空子树）当输入扩展的先序遍历序列：A B D . G . . C E . . F . . 输出应该为：层次遍历：A B C D E F G 先序遍历：A B D G C E F中序遍历：D G B

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

3、Tree bt)7.实现中序遍历二叉树的非递归算法，NRInOrder (BiTree bt)8.实现后序遍历二叉树的非递归算法，NRPostOrder (BiTree bt)9.实现层次遍历二叉树的递归算法，LevelOrder (BiTree bt)10.调用各个函数输出遍历结果四、源程序代码#include "iostream.h"#include "stdio.h"#include "malloc.h"typedef struct Node/*声明二叉树二叉链表节点的结构！*/ char data; struct Node *

4、lchild; struct Node *rchild;BiTNode,*BiTree;typedef struct /*定义结构体（将栈中元素的数据类型定义为指针和标志flag合并的结构体类型）*/BiTree link;int flag;stacktype;/*函数声明*/void Visite(char a);void CreateBiTree(BiTree *bt);void PreOrder(BiTree bt);void InOrder(BiTree bt);void PostOrder(BiTree bt);void NRPreOrder (BiTree bt);void NRI

5、nOrder (BiTree bt);void NRPostOrder (BiTree bt);void LevelOrder (BiTree bt);/*定义函数（访问节点的数据域）*/void Visite(char a) cout<<a<<" "/*层次遍历二叉树*/void LevelOrder (BiTree bt)BiTree queue50;int front,rear;if (bt=NULL)return;front=-1;rear=0;queuerear=bt;while (front !=rear)front +;Visite (

6、queuefront->data);if (queuefront->lchild!=NULL)rear+;queuerear=queuefront->lchild;if (queuefront->rchild!=NULL)rear+;queuerear=queuefront->rchild;/*先序遍历建立二叉树*/void CreateBiTree(BiTree *bt)char ch;ch=getchar();if (ch='.') *bt=NULL;else *bt=(BiTree) malloc(sizeof(BiTNode); (*bt)

7、->data=ch; CreateBiTree(&(*bt)->lchild); CreateBiTree(&(*bt)->rchild);/*递归先序遍历二叉树bt*/void PreOrder(BiTree bt) if(bt=NULL) return;cout<<bt->data<<" "PreOrder (bt->lchild);PreOrder (bt->rchild);/*递归中序遍历二叉树bt*/void InOrder(BiTree bt)if(bt=NULL) return;InO

8、rder (bt->lchild);cout<<bt->data<<" "InOrder (bt->rchild);/*递归后序遍历二叉树bt*/void PostOrder(BiTree bt)if(bt=NULL) return;PostOrder (bt->lchild);PostOrder (bt->rchild);cout<<bt->data<<" "/*非递归先序遍历二叉树bt*/ void NRPreOrder (BiTree bt)BiTree stack

9、20,p;int top;if (bt=NULL)return;top=0;p=bt;while(!(p=NULL&&top=0)while (p!=NULL)Visite (p->data);if (top <20-1)stacktop=p;top+;elsecout<<"溢出！"return;p=p->lchild;if (top<=0)return;elsetop-;p=stacktop;p=p->rchild; /*非递归中序遍历二叉树bt*/void NRInOrder (BiTree bt)BiTree

10、stack20,p;int top;if (bt=NULL)return;top=0;p=bt;while(!(p=NULL&&top=0)while (p!=NULL)if (top <20-1)stacktop=p;top+;elsecout<<"溢出！"return;p=p->lchild;if (top<=0)return;elsetop-;p=stacktop;Visite (p->data);p=p->rchild;/*非递归后序遍历二叉树bt*/void NRPostOrder (BiTree bt)s

11、tacktype stack50;BiTree p;int top,sign;if (bt=NULL)return;top=-1;p=bt;while (!(p=NULL&&top=-1)if (p!=NULL)top+;stacktop.link=p;stacktop.flag=1;p=p->lchild;elsep=stacktop.link;sign=stacktop.flag;top-;if (sign=1)top+;stacktop.link=p;stacktop.flag=2;p=p->rchild;else Visite (p->data);p=

12、NULL;/*主函数*/void main()cout<<"请输入序列："<<endl;BiTree bt;CreateBiTree(&bt);cout<<"n层次遍历:"LevelOrder (bt);cout<<"nn先序、中序、后序遍历的递归实现:"cout<<"n先序遍历:"PreOrder(bt);cout<<"n中序遍历:"InOrder(bt);cout<<"n后序遍历:"PostOrder(bt);cout<<"nn先序、中序、后序遍历的非递归实现:"cout<<"n先序遍历:"NRPreOrder (bt);cout<<"n中序遍历:"NRInOrder (bt);cout<<"n后序遍历:"NRPostOrder (bt);cout<<"nn&qu