重庆交通大学数据结构课程设计树的遍历算法实验报告Word下载.docx
《重庆交通大学数据结构课程设计树的遍历算法实验报告Word下载.docx》由会员分享，可在线阅读，更多相关《重庆交通大学数据结构课程设计树的遍历算法实验报告Word下载.docx（12页珍藏版）》请在冰点文库上搜索。
以这3种方式遍历一棵树时，若按访问结点的先后次序将结点排列起来，就可分别得到树中所有结点的前序列表，中序列表和后序列表。
相应的结点次序分别称为结点的前序、中序和后序。
二、基本要求
建立一棵二叉树，编写程序，对二叉树进行前、中、后序和层次进行遍历，给出算法，并打印结果，本程序用VC6.0编写，实现建立一棵二叉树的功能输入二叉树数据
1．输入形式和输入值的范围：
输入数据格式不限，具体定义为char字符格式输入，并以嵌套表示法输入，以‘#’字符结尾。
2．输出的形式：
输出二叉树的前序、中序、后序以及层次遍历结果。
3．程序所能达到的功能：
a）输入二叉树的先序序列构造相应的二叉树；
b）前序递归遍历二叉树,输出得到的节点序列；
c）中序递归遍历二叉树,输出得到的节点序列；
d）后序递归遍历二叉树,输出得到的节点序列；
e）前序非递归遍历二叉树,输出得到的节点序列；
f）中序非递归遍历二叉树,输出得到的节点序列；
g）后序非递归遍历二叉树,输出得到的节点序列
h）层次遍历二叉树,输出得到的节点序列
三、测试数据
本实验采用本人学号631507030101进行数据测试
具体二叉树结构如下：
在建立时以createbtree（bt,"
6（3（5（3（,0））,0（,0））,1（7（,1
（1））,0））#"
）方法建立。
四、算法思想
1）建立二叉树结构
建立二叉树时要明确建立的树的结构，本实验以嵌套表示法进行建树，二叉树用链表存储来实现,因此要先定义一个二叉树链表存储结构。
因此要先定义一个结构体。
此结构体的每个结点都是由数据域data、左指针域Lchild、右指针域Rchild两个指针域分别指向该结点的左、右孩子,若某结点没有左孩子或者右孩子时,对应的指域就为空。
最后,还需要一个链表的头指针指向根结点。
第一步的时候一定要先定义一个结束标志符号,例如空格键、#等。
当它遇到该标志时,就指向为空。
建立左右子树时,仍然是调用createbtree（）函数,依此递归进行下去,直到遇到结束标志时停止操作。
2）输入二叉树元素
输入二叉树时,是按上面所确定的遍历规则输入的。
最后,用一个返回值来表示所需要的。
3）先序遍历二叉树
当二叉树为非空时,执行以下三个操作:
访问根结点、遍历左子树、遍历右子树。
4）中序遍历二叉树
当二叉树为非空时,程序执行以下三个操作:
遍历左子树、访问根结点、遍历右子树。
5）后序遍历二叉树
遍历左子树、遍历右子树、访问根结点。
6）层次遍历二叉树
从根结点依次从上至下从左至右进行遍历。
7）主程序
需列出各个函数,然后进行函数调用。
五、数据结构
本实验数据以本人学号（631507030101）以char形式进行存储。
六、源程序
#include<
iostream.h>
#definemaxsize100
typedefcharelemtype;
typedefstructbinode{//定义二叉树结点结构体，一装data域，两个指向左右孩子指针；
elemtypedata;
binode*lchild,*rchild;
}bitree;
voidcreatebtree（bitree*&
bt,char*str）{//建树函数，传递进入根节点指针和字符串；
bitree*stack[maxsize],*p;
bt=NULL;
inttop=-1,k,j=0;
charch;
ch=str[j];
while（ch!
='
#'
）{//判断是否是结尾；
switch（ch）{
case'
（'
:
top++;
stack[top]=p;
//建立一个堆栈存储数据；
k=1;
break;
）'
top--;
'
k=2;
default:
p=newbinode;
p->
data=ch;
lchild=p->
rchild=NULL;
//判断叶节点；
if（bt==NULL）
bt=p;
else
switch（k）
{case1:
stack[top]->
lchild=p;
break;
case2:
rchild=p;
}
}
j++;
}
voidprintree（bitree*boot）{//打印二叉树函数，传入二叉树根节点指针；
bitree*b=boot;
if（b!
=NULL）{
cout<
<
b->
data;
if（（b->
lchild!
=NULL）||（b->
rchild!
=NULL））{//如果结点左右孩子非空；
cout<
"
（"
;
printree（b->
lchild）;
//指针指向左孩子；
if（b->
=NULL）cout<
"
printree（b->
rchild）;
//指针指向右孩子；
）"
}
voidPredigui（bitree*b）//递归前序遍历
{
if（b==NULL）
return;
cout<
data<
"
Predigui（b->
voidMiddigui（bitree*b）//递归中序遍历
Middigui（b->
voidLastdigui（bitree*b）//递归后序遍历
Lastdigui（b->
voidpretree（bitree*boot）{//前序遍历函数，传入二叉树根节点指针；
inttop=-1;
bitree*s[maxsize],*bt=boot;
while（（bt!
=NULL）||（top!
=-1））{
while（bt!
bt->
//输出结点数据；
s[++top]=bt;
bt=bt->
lchild;
if（top!
=-1）{
bt=s[top--];
bt=bt->
rchild;
voidmidtree（bitree*boot）{//中序遍历函数，传入二叉树根节点指针；
=-1））{
=NULL）{
if（top>
-1）{
voidbacktree（bitree*boot）{//后序遍历函数，传入二叉树根节点指针
bitree*s[maxsize],*pre=NULL,*bt=boot;
=-1））{//如果根节点非空或堆栈非空；
//存入堆栈，栈顶指针++；
bt=s[top];
if（bt->
=NULL&
&
=pre）{//如果非空；
bt=bt->
}
else{
cout<
pre=bt;
bt=NULL;
top--;
voidleveltree（bitree*boot）{//层次遍历函数，传入二叉树根节点指针；
intrear=0,front=0;
s[rear++]=bt;
while（rear!
=front）{//循环队列非空
bt=s[front];
front=（front+1）%maxsize;
//循环队列出对
if（bt->
s[rear]=bt->
//指针指向左孩子，把数据存入a[]；
rear=（rear+1）%maxsize;
//循环队列尾指针加一；
//指针指向右孩子，数据存入a[]；
voidmain（）{//主函数
bitree*bt;
//定义一个二叉树根节点指针
createbtree（bt,"
）;
//以学号为数据建树
cout<
嵌套表示法"
endl;
printree（bt）;
递归：
前序遍历：
Predigui（bt）;
中序遍历：
Middigui（bt）;
后序遍历：
Lastdigui（bt）;
非递归：
前序：
pretree（bt）;
//前序打印二叉树
中序：
midtree（bt）;
//中序打印二叉树
后序：
backtree（bt）;
//后序打印二叉树
层次：
leveltree（bt）;
//层次打印二叉树
七、设计感想
通过这次实验使我对二叉树的两种遍历格式和三种遍历方法有了进一步的了解，熟悉了二叉树的基本操作，掌握了二叉树的实现以及实际的应用，加深了对二叉树的理解，逐步培养解决实际问题的编程能力和如何使用递归方法和，使我跟深刻的认识到了二叉树的遍历，所谓二叉树的遍历，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。
访问结点所做的操作依赖于具体的应用问题。
遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础，同时知道了如果知道了一棵树的先序遍历和中序遍历或者同时知道后序遍历和中序遍历，就能确定一棵二叉树，
升级会员 