二叉树的遍历实验报告
一、需求分析
在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进展某种处理，这就是二叉树的遍历问题。
对二叉树的数据构造进展定义，建立一棵二叉树，然后进展各种实验操作。 二叉树是一个非线性构造，遍历时要先明确遍历的规那么，先访问根结点还时先访问子树，然后先访问左子树还是先访问有右子树，这些要事先定好，因为采用不同的遍历规那么会产生不同的结果。本次实验要实现先序、中序、后序三种遍历。
基于二叉树的递归定义，以及遍历规那么，本次实验也采用的是先序遍历的规那么进展建树的以及用递归的方式进展二叉树的遍历。
二、系统总框图
主程序 建立二叉树 输入二叉树 先序遍历 中序遍历 后序遍历 结点构造 二叉树结点 Data Lchild data Rchild Lchild Rchild
三、各模块设计分析
〔1〕建立二叉树构造 建立二叉树时，要先明确是按哪一种遍历规那么输入，该二叉树是按你所输入的遍历规那么来建立的。本实验用的是先序遍历的规那么进展建树。
二叉树用链表存储来实现，因此要先定义一个二叉树链表存储构造。因此要先定义一个构造体。此构造体的每个结点都是由数据域data、左指针域Lchild、右指针域Rchild组成，两个指针域分别指向该结点的左、右孩子，假设某结点没有左孩子或者右孩子时，对应的指
页脚下载后可删除，如有侵权请告知删除！
针域就为空。最后，还需要一个链表的头指针指向根结点。
要注意的是，第一步的时候一定要先定义一个完毕标志符号，例如空格键、＃等。当它遇到该标志时，就指向为空。
建立左右子树时，仍然是调用create〔〕函数，依此递归进展下去，直到遇到完毕标志时停顿操作。
〔2〕输入二叉树元素
输入二叉树时，是按上面所确定的遍历规那么输入的。最后，用一个返回值来表示所需要的结果。
〔3〕先序遍历二叉树
当二叉树为非空时，执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。
〔4〕中序遍历二叉树
当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。
〔5〕后序遍历二叉树
当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。
〔6〕主程序
需列出各个函数，然后进展函数调用。
四、各函数定义及说明
因为此二叉树是用链式存储构造存储的，所以定义一个构造体用以存储。 typedef struct BiTNode
{ char data;
struct BiTNode *Lchild; struct BiTNode *Rchild;
}BiTNode,*BiTree;
〔1〕主函数main〔〕
主程序要包括：定义的二叉树T、建树函数create〔〕、先序遍历函数Preorder〔〕、中序遍历函数Inorder〔〕、后序遍历函数Postorder〔〕。 〔2〕建树函数Create〔〕
定义一个输入的数是字符型的，当ch为空时，T就为空值，否那么的话就分配空间给T，T就指向它的结点，然后左指针域指向左孩子，右指针指向右孩子，假设还有，继续调用Create〔〕，依次循环下去，直到ch遇到空时，完毕。 最后要返回建立的二叉树T。 〔3〕先序遍历函数Preorder〔〕
根据先序遍历规那么，当T为非空时，先输出结点处的数据，指针指向左、右孩子，依次进展下去。
(4) 中序遍历函数Inorder〔〕
根据中序遍历规那么，当T为非空时，先左指针指向左孩子数据，然后输出结点处的数据，再右指针指向右孩子，依次进展下去。 〔5〕后序遍历函数Postorder〔〕
根据后序遍历规那么，当T为非空时，先右指针指向右孩子，然后左指针指向左孩子，最后输出结点处的数据，依次进展下去。
五、使用说明
页脚下载后可删除，如有侵权请告知删除！
在Turbo C的环境下，先按Ctrl+F9运行程序，此时就是建立二叉树的过程，例如输入序列-+a *b -c d /e f 输入过程中不要加回车，因为回车也有对应的ASCII码，是要算字符的，输入完之后再按回车，用户界面上就能够看到结果了。 另外你必须会手动建立一棵二叉树，保证你输入的序列能构成一棵二叉树，否那么你怎么输入，按最后按多少回车程序也不会完毕！
六、源程序
#include \"stdio.h\" #include \"string.h\" #include \"alloc.h\" #define NULL 0
typedef struct BiTNode {
char data;
struct BiTNode *Lchild; struct BiTNode *Rchild; }BiTNode,*BiTree;
BiTree Create() {
char ch; BiTree T;
scanf(\"%c\ if(ch==' ') T=NULL; else
{ T=(BiTNode *)malloc(sizeof(BiTNode)); T->data=ch;
T->Lchild=Create(); T->Rchild=Create(); } return T; }
void Preorder(BiTree T) { if(T) {
printf(\"%c\ Preorder(T->Lchild); Preorder(T->Rchild); } }
void Inorder(BiTree T) {
页脚下载后可删除，如有侵权请告知删除！
if(T) {
Inorder(T->Lchild); printf(\"%c\ Inorder(T->Rchild); } }
void Postorder(BiTree T) { if(T) {
Postorder(T->Lchild); Postorder(T->Rchild); printf(\"%c\ } }
main() {
BiTree T; clrscr();
printf(\"The elements is : \"); T=Create(); printf(\"\\n\");
printf(\"The Preorder's result is : \"); Preorder(T); printf(\" \\n\\n\");
printf(\"The Inorder's result is : \"); Inorder(T); printf(\"\\n\\n\");
printf(\"The Postorder's result is : \"); Postorder(T); getch(); }
七、测试数据
- + / a * e f b c - 页脚下载后可删除，如有侵权请告知删除！
d
八、测试结果
先序遍历序列：-,+,a,*,b,-,c,d,/,e,f ； 中序遍历序列：a,+,b,*,c,-,d,-,e,/,f ； 后序遍历序列：a,b,c,d,-,*,+,e,f,/,- ；
【本文档内容可以自由复制内容或自由编辑修改内容期待你的好评和关注，我们将会做得更好】
页脚下载后可删除，如有侵权请告知删除！
