二叉树的遍历

荆楚理工学院 数据结构课程设计 学院:计算机工程学院 班 级: 计算机科学与技术（1）班 学生姓名: 学 号: . 设计地点（单位） 荆楚理工学院 设计题目： 二叉树遍历 完成日期： 2010年 12 月 20 日 指导教师评语: 成绩(五级记分制): 教师签名: 一目的更好的了解二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现流程及操作步骤。加深理论知识，提高实践能力。二问题描述二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，建树的实现。三概要设计1.创建二叉树2.二叉树的递归遍历算法（前、中、后）3.二叉树的层次遍历算法4.二叉树的非递归遍历算法（前、中、后）5.退出以选择面板开始，显得更为清晰。其中3，4，5，6，8为添加内容，有助于更好的了解二叉树。四详细设计1.创建二叉树(1)定义二叉树结点值的类型为字符型。(2)结点个数不超过10个。(3)按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树。2.二叉树的递归遍历算法（前、中、后）DLR(1)访问根结点。(2)先序遍历根结点的左子数。(3)先序遍历根结点的右子数。LDR(1)先序遍历根结点的左子数。(2)访问根结点。(3)先序遍历根结点的右子数。LRD(1)先序遍历根结点的左子数。(2)先序遍历根结点的右子数。(3)访问根结点。3.二叉树的层次遍历算法(1)访问该元素所指结点。(2)若该元素所指结点的左右孩子结点非空，则该元素所指结点的左孩子指针和右孩子指针顺序入队。4.二叉树的非递归遍历算法（前、中、后）（1）非递归的先序遍历算法a.访问结点的数据域。b.指针指向p的左孩子结点。c.从栈中弹出栈顶元素。d.指针指向p的右孩子结点。（2）非递归的中序遍历算法a.指针指向p的左孩子结点。b.从栈中弹出栈顶元素。c.访问结点的数据域。d.指针指向p的右孩子结点。（3）非递归的后序遍历算法bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法，结点入栈时，配一个标志tag一同入栈(1：遍历左子树前的现场保护，2：遍历右子树前的现场保护)。首先将bt和tag(为1)入栈，遍历左子树；返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。5.退出五测试数据与分析abcdefg六源代码#include iostream.h#include stdlib.h#include stdio.htypedef char ElemType;/定义二叉树结点值的类型为字符型const int MaxLength=10;/结点个数不超过10个typedef struct BTNode ElemType data; struct BTNode *lchild,*rchild;BTNode,* BiTree;void CreateBiTree(BiTree &T)/按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树/ if(T) return; char ch; ch=getchar(); /不能用cin来输入，在cin中不能识别空格。 if(ch= ) T=NULL; else if(!(T=(BTNode *)malloc(sizeof(BTNode) coutdata=ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); void PreOrderTraverse(BiTree T)/先序遍历 if(T) coutdatalchild); PreOrderTraverse(T-rchild); void InOrderTraverse(BiTree T)/中序遍历 if(T) InOrderTraverse(T-lchild); coutdatarchild); void PostOrderTraverse(BiTree T)/后序遍历 if(T) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); coutdata ; void LevelOrderTraverse(BiTree T)/层序遍历 BiTree QMaxLength; int front=0,rear=0; BiTree p; if(T) /根结点入队 Qrear=T; rear=(rear+1)%MaxLength; while(front!=rear) p=Qfront; /队头元素出队 front=(front+1)%MaxLength; coutdatalchild) /左孩子不为空，入队 Qrear=p-lchild; rear=(rear+1)%MaxLength; if(p-rchild) /右孩子不为空，入队 Qrear=p-rchild; rear=(rear+1)%MaxLength; /非递归的先序遍历算法void NRPreOrder(BiTree bt) BiTree stackMaxLength,p; int top; if (bt!=NULL) top=0;p=bt; while(p!=NULL|top0) while(p!=NULL) coutdata; stacktop=p; top+; p=p-lchild; if (top0) top-; p=stacktop; p=p-rchild; /非递归的中序遍历算法void NRInOrder(BiTree bt) BiTree stackMaxLength,p; int top; if (bt!=NULL) top=0;p=bt; while(p!=NULL|top0) while(p!=NULL) stacktop=p; top+; p=p-lchild; if (top0) top-; p=stacktop;coutdata; p=p-rchild; /非递归的后序遍历算法typedef struct BiTree ptr; int tag;stacknode;void NRPostOrder(BiTree bt) stacknode sMaxLength,x; BiTree p=bt; int top; if(bt!=NULL) top=0;p=bt; do while (p!=NULL) /遍历左子树 stop.ptr = p; stop.tag = 1; /标记为左子树 top+; p=p-lchild; while (top0 & stop-1.tag=2) x = s-top; p = x.ptr; coutdata; /tag为R，表示右子树访问完毕，故访问根结点 if (top0) stop-1.tag =2; /遍历右子树 p=stop-1.ptr-rchild; while (top0);/PostOrderUnrecvoid main() BiTree T; T=NULL; int select; /cout请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):endl;/ CreateBiTree(T); while(1) coutnn请选择要执行的操作:n; cout1.创建二叉树n; cout2.二叉树的递归遍历算法（前、中、后）n; cout3.二叉树的层次遍历算法n;cout4.二叉树的非递归遍历算法（前、中、后）n; coutselect; switch(select) case 0:return; case 1: cout请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):endl; CreateBiTree(T); break; case 2: if(!T) cout未建立树，请先建树！; else coutn先序遍历:n; PreOrderTraverse(T); coutn中序遍历:n; InOrderTraverse(T); coutn后序遍历:n; PostOrderTraverse(T); break; case 3: coutn层序遍历:n; LevelOrderTraverse(T); br