数据结构树的遍历算法课程设计实验报告

1、交通大学信息科学与工程学院综合性设计性实验报告班级：物联网1501班学号： 怿欣1实验项目名称：树的遍历算法实验项印性质：综合性实验所属课程：算法与数据结构实验室（中心）：语音楼801信息实验室指导教师：盛明兰实验完成时间：2017年11 月23 日教师评阅意见：签名：年 月曰实验成绩：一、问题描述本实验要求对二叉树进行对每一个结点进行访问。树的遍历是树的一种重要的运算。 所谓遍历是指对树中所有结点的信息的访 问，即依次对树中每个结点访问一次且仅访问一次。 二叉树的3种最重要的遍历 方式分别称为前序遍历、中序遍历和后序遍历。以这3种方式遍历一棵树时，若 按访问结点的先后次序将结点排列起来，就可

2、分别得到树中所有结点的前序列表， 中序列表和后序列表。相应的结点次序分别称为结点的前序、中序和后序。二、基本要求建立一棵二叉树，编写程序，对二叉树进行前、中、后序和层次进行遍历， 给出算法，并打印结果，本程序用VC6.0编写，实现建立一棵二叉树的功能输入 二叉树数据1. 输入形式和输入值的围：输入数据格式不限，具体定义为为char字符格式输入，并以嵌套表示法输入， 以#'字符结尾。2. 输出的形式：输出二叉树的前序、中序、后序以及层次遍历结果。3. 程序所能达到的功能：a）输入二叉树的先序序列构造相应的二叉树;b）前序递归遍历二叉树，输出得到的节点序列;c）中序递归遍历二叉树，输出得到

3、的节点序列；d）后序递归遍历二叉树，输出得到的节点序列；e）前序非递归遍历二叉树，输出得到的节点序列;f）中序非递归遍历二叉树，输出得到的节点序列;g）后序非递归遍历二叉树，输出得到的节点序列h）层次遍历二叉树，输出得到的节点序列三、测试数据本实验采用本人学号1进行数据测试具体二叉树结构如下：方法在建立时以createbtree(bt,"6(3(5(3(,0),0(,0),1(7(,1(1),0)#")建立。IZH C:Users Adrninistrator Deskt-op _Uebug binar|rtree 嵌套表示法 6（3（5（3（r0）,0（J0）,l（7（J

4、 L） 递归：前序遍历；635300017110 中*遍历：305300671110 后序遍历匕035003117016 非递归r前序：635300017110 中序：305300671110 后序：03S003117016 层次；631507030101Press any key to continue四、算法思想1) 建立二叉树结构建立二叉树时要明确建立的树的结构，本实验以嵌套表示法进行建树，二叉 树用链表存储来实现，因此要先定义一个二叉树链表存储结构。因此要先定义一 个结构体。此结构体的每个结点都是由数据域data、左指针域Lchild、右指针域Rchild两个指针域分别指向该结点的左、

5、右孩子,若某结点没有左孩子或者右 孩子时,对应的指域就为空。最后,还需要一个链表的头指针指向根结点。 第一步 的时候一定要先定义一个结束标志符号，例如空格键、#等。当它遇到该标志时， 就指向为空。建立左右子树时,仍然是调用createbtree ()函数,依此递归进行下去,直到遇到结束标志时停止操作。2) 输入二叉树元素输入二叉树时，是按上面所确定的遍历规则输入的。最后,用一个返回值来表示所需要的。3) 先序遍历二叉树当二叉树为非空时 , 执行以下三个操作 :访问根结点、遍历左子树、遍历右子 树。4) 中序遍历二叉树当二叉树为非空时 , 程序执行以下三个操作 :遍历左子树、访问根结点、遍历 右

6、子树。5) 后序遍历二叉树当二叉树为非空时 , 程序执行以下三个操作 :遍历左子树、遍历右子树、访问 根结点。6) 层次遍历二叉树当二叉树为非空时 , 程序执行以下三个操作 : 从根结点依次从上至下从左至 右进行遍历。7) 主程序需列出各个函数 , 然后进行函数调用。五、数据结构本实验数据以本人学号( 1)以 char 形式进行存储。六、源程序#include<iostream.h>#define maxsize 100typedef char elemtype;typedef struct binode/定义二叉树结点结构体，一装 data 域，两个指向左右孩子指针；elemty

7、pe data;binode *lchild,*rchild;bitree;void createbtree(bitree *&bt,char *str)/建树函数，传递进入根节点指针和字符串；bitree *stackmaxsize,*p;bt=NULL;int top=-1,k,j=0;char ch;ch=strj;while(ch!='#') / 判断是否是结尾；switch(ch) case '(':top+;stacktop=p;/ 建立一个堆栈存储数据；k=1;break;case ')':top-;break;case &

8、#39;,':k=2;break;default:p=new binode;p->data=ch;p->lchild=p->rchild=NULL;/ 判断叶节点； if(bt=NULL)bt=p;elseswitch(k)case 1: stacktop->lchild=p;break;case 2: stacktop->rchild=p;break;j+;ch=strj;void printree(bitree *boot) /打印二叉树函数，传入二叉树根节点指针；bitree *b=boot;if(b!=NULL) cout<<b->

9、;data;if(b->lchild!=NULL)|(b->rchild!=NULL)/ 如果结点左右孩子非空； cout<<"("printree(b->lchild);/指针指向左孩子；if (b->rchild!=NULL) cout<<","printree(b->rchild); / cout<<")"void Predigui(bitree *b)/if(b=NULL)return ;指针指向右孩子；递归前序遍历cout<<b->data&

10、lt;<" "Predigui(b->lchild);Predigui(b->rchild);void Middigui(bitree *b) /if(b=NULL)return ;Middigui(b->lchild); cout<<b->data<<" " Middigui(b->rchild);void Lastdigui(bitree *b) /if(b=NULL)return ;Lastdigui(b->lchild);Lastdigui(b->rchild); cout&

11、lt;<b->data<<" "void pretree(bitree *boot) /int top=-1;bitree *smaxsize,*bt=boot;递归中序遍历递归后序遍历前序遍历函数，传入二叉树根节点指针；while(bt!=NULL)|(top!=-1)while(bt!=NULL) cout<<bt->data<<" "/ 输出结点数据； s+top=bt;bt=bt->lchild; / 指针指向左孩子；if(top!=-1) bt=stop-;bt=bt->rchi

12、ld; /指针指向右孩子；void midtree(bitree *boot) /中序遍历函数，传入二叉树根节点指针；int top=-1;bitree *smaxsize,*bt=boot; while(bt!=NULL)|(top!=-1) while(bt!=NULL) s+top=bt;bt=bt->lchild; / 指针指向左孩子；if(top>-1) bt=stop-;cout<<bt->data<<" "/ 输出结点数据； bt=bt->rchild; / 指针指向右孩子；void backtree(bitre

13、e *boot) / 后序遍历函数，传入二叉树根节点指针 bitree *smaxsize,*pre=NULL,*bt=boot;int top=-1;while(bt!=NULL)|(top!=-1) / 如果根节点非空或堆栈非空； while(bt!=NULL) s+top=bt;/ 存入堆栈，栈顶指针 +； bt=bt->lchild; / 指针指向左孩子；if(top>-1) bt=stop;if(bt->rchild!=NULL&&bt->rchild!=pre) / 如果非空； bt=bt->rchild; / 指针指向右孩子；else

14、cout<<bt->data<<" "/输出结点数据；pre=bt;bt=NULL;top-;void leveltree(bitree *boot) /层次遍历函数，传入二叉树根节点指针；bitree *smaxsize,*bt=boot;int rear=0,front=0;循环队列非空srear+=bt; while(rear!=front) /bt=sfront;front=(front+1)%maxsize;/ 循环队列出对 cout<<bt->data<<" "/ 输出结点数据；if

15、(bt->lchild!=NULL) srear=bt->lchild; / 指针指向左孩子，把数据存入 a ； rear=(rear+1)%maxsize;/ 循环队列尾指针加一；if(bt->rchild!=NULL) srear=bt->rchild; /指针指向右孩子，数据存入 a ；rear=(rear+1)%maxsize; /循环队列尾指针加一；void main()/ 主函数以学号为数据建树bitree *bt;/定义一个二叉树根节点指针createbtree(bt,"6(3(5(3(,0),0(,0),1(7(,1(1),0)#")

16、;/ cout<<" 嵌套表示法 "<<endl;printree(bt);coutvvendl;coutvv"递归："vvendl;coutvv"前序遍历："Predigui(bt); coutvvendl; coutvv" 中序遍历：后序遍历:Middigui(bt); coutvvendl; coutvv""vvendl;"vvendl;前序打印二叉树"vvendl;中序打印二叉树"vvendl;后序打印二叉树"vvendl;层次打印二叉树Lastdigui(bt); coutvvendl; coutvv "非递归： coutvv"前序： pretree(bt);/ coutvvendl; coutvv"中序: midtree(bt); / coutvvendl; coutvv"后序: backtree(bt); / coutvvendl; coutvv"层次： leveltree(bt); / coutvvendl; 七、设计感想通过