《2022年数据结构课程方案二叉树遍历》由会员分享，可在线阅读，更多相关《2022年数据结构课程方案二叉树遍历（8页珍藏版）》请在金锄头文库上搜索。
1、个人资料整理仅限学习使用数据结构课程设计报告题目：二叉树的遍历日期：2009-12-22 年级：班级：姓名：学号：一实习目的更好的了解二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现流程及操作步骤。加深理论知识，提高实践能力。二问题描述二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，建树的实现。三概要设计1.创建二叉树2.二叉树的递归遍历算法前、中、后）3.二叉树的层次遍历算法4.二叉树的非递归遍历算法定义二叉树结点值的类型为字符型。(2结点个数不超过10 个。(3按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树。2.二叉树的递
2、归遍历算法访问根结点。(2先序遍历根结点的左子数。(3先序遍历根结点的右子数。LDR (1先序遍历根结点的左子数。(2访问根结点。(3先序遍历根结点的右子数。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 8 页个人资料整理仅限学习使用LRD (1先序遍历根结点的左子数。(2先序遍历根结点的右子数。(3访问根结点。3.二叉树的层次遍历算法(1访问该元素所指结点。(2若该元素所指结点的左右孩子结点非空，则该元素所指结点的左孩子指针和右孩子指针顺序入队。4.二叉树的非递归遍历算法前、中、后）1）非递归的先序遍历算法a.访问结点的数据域。b.
3、指针指向p 的左孩子结点。c.从栈中弹出栈顶元素。d.指针指向p 的右孩子结点。2）非递归的中序遍历算法a.指针指向p 的左孩子结点。b.从栈中弹出栈顶元素。c.访问结点的数据域。d.指针指向p 的右孩子结点。首先将 bt 和 tag(为 1入栈，遍历左子树；返回后，修改栈顶tag为 2，遍历右子树；最后访问根结点。5.退出五测试数据与分析a b c d e f g 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 8 页个人资料整理仅限学习使用精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第
4、3 页，共 8 页个人资料整理仅限学习使用六源代码#include iostream.h #include stdlib.h #include stdio.h typedef 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
5、 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/中序遍历 i
6、f(T 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 8 页个人资料整理仅限学习使用 InOrderTraverse(T-lchild 。 coutdatarchild 。 void PostOrderTraverse(BiTree T/ 后序遍历 if(T PostOrderTraverse(T-lchild 。 PostOrderTraverse(T-rchild 。 coutdata/层序遍历 BiTree QMaxLength 。 int front=0,rear=0 。 BiTree p 。 if(T / 根结点入队 Qre
7、ar=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。 i
8、f (bt!=NULL top=0。p=bt。 while(p!=NULL|top0 while(p!=NULL 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 8 页个人资料整理仅限学习使用 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
9、=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。精选学习资料 - - - - - - - - -
10、 名师归纳总结 - - - - - - -第 6 页，共 8 页个人资料整理仅限学习使用 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 。 /PostOrderUnrec
11、void main( BiTree T 。 T=NULL 。 int select。 /cout: 。 while(1 coutnn 请选择要执行的操作:n。 cout1. 创建二叉树 n。 cout2. 二叉树的递归遍历算法前、中、后） n。 cout3. 二叉树的层次遍历算法n。cout4. 二叉树的非递归遍历算法前、中、后）n。coutselect。 switch(select case 0:return。 case 1: cout: 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 8 页个人资料整理仅限学习使用 break。 case 2: if(!T cout 未建立树，请先建树！。 else cout。 cout 。 cout。 break。 case 3: cout 。 break。 case 4: if(!T cout 未建立树，请先建树！。 else cout 。 cout 。 cout 。 break。 default: cout 请确认选择项:n。 /end switch /end while 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 8 页
