二叉树的遍历.doc

《二叉树的遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、荆楚理工学院《数据结构》课程设计学院:计算机工程学院班级:计算机科学与技术（1）班学生姓名:…学号:20094040101..设计地点（单位）荆楚理工学院设计题目：二叉树遍历完成日期：2010年12月20日指导教师评语:成绩(五级记分制):教师签名:9一．目的更好的了解二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现流程及操作步骤。加深理论知识，提高实践能力。二．问题描述二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，建树的实现。三．概要设计1.创建二叉树2.二叉树的递归遍历算

2、法（前、中、后）3.二叉树的层次遍历算法4.二叉树的非递归遍历算法（前、中、后）5.退出以选择面板开始，显得更为清晰。其中3，4，5，6，8为添加内容，有助于更好的了解二叉树。四．详细设计1.创建二叉树(1)定义二叉树结点值的类型为字符型。(2)结点个数不超过10个。(3)按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树。2.二叉树的递归遍历算法（前、中、后）DLR(1)访问根结点。(2)先序遍历根结点的左子数。(3)先序遍历根结点的右子数。LDR(1)先序遍历根结点的左子数。(2)访问根结点。(3)先序遍历根结点的右子数。L

3、RD(1)先序遍历根结点的左子数。(2)先序遍历根结点的右子数。(3)访问根结点。3.二叉树的层次遍历算法(1)访问该元素所指结点。(2)若该元素所指结点的左右孩子结点非空，则该元素所指结点的左孩子指针和右孩子指针顺序入队。4.二叉树的非递归遍历算法（前、中、后）（1）非递归的先序遍历算法a.访问结点的数据域。b.指针指向p的左孩子结点。c.从栈中弹出栈顶元素。d.指针指向p的右孩子结点。（2）非递归的中序遍历算法a.指针指向p的左孩子结点。9b.从栈中弹出栈顶元素。c.访问结点的数据域。d.指针指向p的右孩子结点。（3）非递归的后序

4、遍历算法bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法，结点入栈时，配一个标志tag一同入栈(1：遍历左子树前的现场保护，2：遍历右子树前的现场保护)。首先将bt和tag(为1)入栈，遍历左子树；返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。5.退出五．测试数据与分析abcdefg9六．源代码#include"iostream.h"#include"stdlib.h"9#include"stdio.h"typedefcharElemType;//定义二叉树

5、结点值的类型为字符型constintMaxLength=10;//结点个数不超过10个typedefstructBTNode{ElemTypedata;structBTNode*lchild,*rchild;}BTNode,*BiTree;voidCreateBiTree(BiTree&T){//按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树//if(T)return;charch;ch=getchar();//不能用cin来输入，在cin中不能识别空格。if(ch=='')T=NULL;else{if(!(T=(BTNod

6、e*)malloc(sizeof(BTNode))))cout<<"mallocfail!";T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}}voidPreOrderTraverse(BiTreeT){//先序遍历if(T){cout<data<<'';PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}voidInOrderTraverse(BiTreeT){//中序遍历if(T){InO

7、rderTraverse(T->lchild);cout<data<<'';InOrderTraverse(T->rchild);}}voidPostOrderTraverse(BiTreeT){//后序遍历if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);cout<data<<'';9}}voidLevelOrderTraverse(BiTreeT){//层序遍历BiTreeQ[MaxLength];intfront=0,rear=0;Bi

8、Treep;if(T){//根结点入队Q[rear]=T;rear=(rear+1)%MaxLength;}while(front!=rear){p=Q[front];//队头元素出队front=(front+1)%Ma