1、以这3种方式遍历一棵树时，若按访问结点的先后次序将结点排列起来，就可分别得到树中所有结点的前序列表，中序列表和后序列表。相应的结点次序分别称为结点的前序、中序和后序。二、 基本要求建立一棵二叉树，编写程序，对二叉树进行前、中、后序和层次进行遍历，给出算法，并打印结果，本程序用VC6.0编写，实现建立一棵二叉树的功能输入二叉树数据1 输入形式和输入值的范围：输入数据格式不限，具体定义为char字符格式输入，并以嵌套表示法输入，以#字符结尾。2 输出的形式：输出二叉树的前序、中序、后序以及层次遍历结果。3 程序所能达到的功能：a） 输入二叉树的先序序列构造相应的二叉树；b） 前序递归遍历二叉树,输
2、出得到的节点序列；c） 中序递归遍历二叉树,输出得到的节点序列；d） 后序递归遍历二叉树,输出得到的节点序列；e） 前序非递归遍历二叉树,输出得到的节点序列；f） 中序非递归遍历二叉树,输出得到的节点序列；g） 后序非递归遍历二叉树,输出得到的节点序列h） 层次遍历二叉树,输出得到的节点序列三、 测试数据本实验采用本人学号631507030101进行数据测试具体二叉树结构如下：在建立时以createbtree（bt,6（3（5（3（,0）,0（,0）,1（7（,1（1）,0）#）方法建立。四、 算法思想1） 建立二叉树结构建立二叉树时要明确建立的树的结构，本实验以嵌套表示法进行建树，二叉树用链
3、表存储来实现,因此要先定义一个二叉树链表存储结构。因此要先定义一个结构体。此结构体的每个结点都是由数据域data、左指针域Lchild、右指针域Rchild两个指针域分别指向该结点的左、右孩子,若某结点没有左孩子或者右孩子时,对应的指域就为空。最后,还需要一个链表的头指针指向根结点。第一步的时候一定要先定义一个结束标志符号,例如空格键、#等。当它遇到该标志时,就指向为空。建立左右子树时,仍然是调用createbtree（）函数,依此递归进行下去,直到遇到结束标志时停止操作。2） 输入二叉树元素输入二叉树时,是按上面所确定的遍历规则输入的。最后,用一个返回值来表示所需要的。3） 先序遍历二叉树当
4、二叉树为非空时,执行以下三个操作:访问根结点、遍历左子树、遍历右子树。4） 中序遍历二叉树当二叉树为非空时,程序执行以下三个操作:遍历左子树、访问根结点、遍历右子树。5） 后序遍历二叉树遍历左子树、遍历右子树、访问根结点。6） 层次遍历二叉树从根结点依次从上至下从左至右进行遍历。7） 主程序需列出各个函数,然后进行函数调用。五、 数据结构本实验数据以本人学号（631507030101）以char形式进行存储。六、 源程序#include#define maxsize 100typedef char elemtype;typedefstructbinode/定义二叉树结点结构体，一装data域，
5、两个指向左右孩子指针； elemtype data; binode *lchild,*rchild;bitree; void createbtree（bitree *&bt,char *str）/建树函数，传递进入根节点指针和字符串； bitree *stackmaxsize,*p; bt=NULL; int top=-1,k,j=0; charch; ch=strj; while（ch!=#） /判断是否是结尾； switch（ch） case （:top+; stacktop=p;/建立一个堆栈存储数据； k=1; break;）top-;, k=2; default: p=new bin
6、ode; p-data=ch;lchild=p-rchild=NULL;/判断叶节点； if（bt=NULL）bt=p; else switch（k） case 1: stacktop-lchild=p;break; case 2:rchild=p; j+; void printree（bitree *boot） /打印二叉树函数，传入二叉树根节点指针； bitree *b=boot; if（b!=NULL） coutdata; if（b-lchild!=NULL）|（b-rchild!=NULL）/如果结点左右孩子非空； coutlchild）;/指针指向左孩子； if （b-=NULL）
7、coutrchild）;/指针指向右孩子；） void Predigui（bitree *b）/递归前序遍历 if（b=NULL） return ;coutdatavoid Middigui（bitree *b） /递归中序遍历Middigui（b-void Lastdigui（bitree *b） /递归后序遍历Lastdigui（b-void pretree（bitree *boot）/前序遍历函数，传入二叉树根节点指针； int top=-1; bitree *smaxsize,*bt=boot; while（bt!=NULL）|（top!=-1） while（bt!bt-/输出结点数据
8、； s+top=bt; bt=bt-lchild; if（top!=-1） bt=stop-;bt=bt-rchild;void midtree（bitree *boot） /中序遍历函数，传入二叉树根节点指针；=-1） =NULL） if（top-1） void backtree（bitree *boot） /后序遍历函数，传入二叉树根节点指针 bitree *smaxsize,*pre=NULL,*bt=boot;=-1） /如果根节点非空或堆栈非空；/存入堆栈，栈顶指针+； bt=stop; if（bt-=NULL&=pre） /如果非空； bt=bt- else cout srear=
9、bt-/指针指向左孩子，把数据存入a； rear=（rear+1）%maxsize;/循环队列尾指针加一；/指针指向右孩子，数据存入a；void main（）/主函数 bitree *bt;/定义一个二叉树根节点指针createbtree（bt,）;/以学号为数据建树 cout嵌套表示法endl; printree（bt）;递归：前序遍历： Predigui（bt）;中序遍历： Middigui（bt）;后序遍历： Lastdigui（bt）;非递归：前序： pretree（bt）;/前序打印二叉树中序： midtree（bt）;/中序打印二叉树后序： backtree（bt）;/后序打印二叉树层次： leveltree（bt）;/层次打印二叉树七、 设计感想通过这次实验使我对二叉树的两种遍历格式和三种遍历方法有了进一步的了解，熟悉了二叉树的基本操作，掌握了二叉树的实现以及实际的应用，加深了对二叉树的理解，逐步培养解决实际问题的编程能力和如何使用递归方法和，使我跟深刻的认识到了二叉树的遍历，所谓二叉树的遍历，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础，同时知道了如果知道了一棵树的先序遍历和中序遍历或者同时知道后序遍历和中序遍历，就能确定一棵二叉树，
