文档介绍：.
17 / 17
实验目的
（1）学会用先序创建一棵二叉树。
（2）学会采用递归算法对二叉树进行先序、中序、后序遍历。
（3）学会打印输出二叉树的遍历结果。
实验容
[问题描述]建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。
[基本要求]
从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。
[测试数据]
ABCффDEфGффFффф(其中ф表示空格字符)
则输出结果为 先序：ABCDEGF
中序：CBEGDFA
后序：CGBFDBA
[选作容]
采用非递归算法实现二叉树遍历。
实验步骤
（一）需求分析
1、在这个过程中，接受遍历的二叉树是从键盘接受输入（先序），以二叉链表作为存储结构，建立的二叉树。因此，首先要创建一棵二叉树，而这棵二叉树是先序二叉树。本演示程序中，集合的元素设定为大写字母ABCDEFG，输出的先序，中序，后序遍历分别为ABCDEGF,CBEGDFA,CGBFDBA。二叉树可以表示为：
.
2 / 18
A
B
D
G
F
E
C
接受的输入数据在进行递归的先序，中序，后序遍历后，分别将结果打印出来。
2、在程序运行的过程中可以看到，以计算机提示用户执行的方式进行下去，即在计算机终端上提示“输入二叉树的先序序列”后，由用户在键盘上输入ABC##DE#G##F###，之后相应的选择遍历与遍历结果显示出来。
3、程序执行的命令包括：首先是二叉树的先序序列被创建输入，其次是对输入进去的先序序列有次序的进行先序，中序，后序遍历。最后是打印出二叉树的遍历结果。
4、测试数据
（1）在键盘上输入的先序序列ABC##DE#G##F###
（2）先序遍历结果ABCDEGF
.
3 / 18
（3）中序遍历结果CBEGDFA
（4）后序遍历结果CGBFDBA
（二）概要设计
1、为实现上述程序功能，应以二叉树定义的相关操作和二叉树递归遍历的相关操作为依据。有关以二叉链表作为存储结构，建立二叉树的操作为：
typedef BTNode *BTree; //定义二叉树的指针
BTree CreatBTree(void)
{
BTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#，返回空指针
else{
T=(BTNode *)malloc(sizeof(BTNode)); //分配空间，生成结点
T->data=ch;
T->lchild=CreatBTree(); //构造左子树
T->rchild=CreatBTree(); //构造右子树
return(T);
}
}
2、而有关先序、中序、后序遍历的递归操作为：
void Preorder(BTree T) //先序遍历
{
if(T){
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
.
4 / 18
void Inorder(BTree T) //中序遍历
{
if(T)
{
Inorder(T->lchild); //中序遍历左子树
printf("%c",T->data); //访问结点
Inorder(T->rchild); //中序遍历右字树
}
}
void Postorder(BTree T) //后序遍历
{
if(T)
{
Postorder(T->lchild); //后序遍历左子树
Postorder(T->rchild); //后序遍历右子树
printf("%c",T->data); //访问结点
}
}
3、本程序包含的模块
（1）结点单元模块
（2）构建先序二叉树模块
（3）二叉树遍历模块
（4）主程序模块
各模