数据结构实验报告.docx

实验目的
（ 1 ）学会用先序创建一棵二叉树。
（ 2 ）学会采用递归算法对二叉树进行先序、中序、后序遍历。
（ 3 ）学会打印输出二叉树的遍历结果。
实验内容
【问题描述】建立一棵二叉树，并对其进行遍历（先序、中序、后序） ，打印输出遍历结果。
【基本要求】
从键盘接受输入（先序） ，以二叉链表作为存储结构，建立二叉树（以先序来建立） ，并采用递归
算法对其进行遍历（先序、中序、后序） ，将遍历结果打印输出。
【测试数据】
ABC 4）（|DE（t）G（t）（t）F（t）（t）水其中小表示空格字符）
则输出结果为 先序： ABCDEGF
中序： CBEGDFA
后序： CGBFDBA
【选作内容】
采用非递归算法实现二叉树遍历。
实验步骤
（一）需求分析
1、在这个过程中，接受遍历的二叉树是从键盘接受输入（先序） ，以二叉链表作 为存储结构，建立的二叉树。因此，首先要创建一棵二叉树，而这棵二叉树是先 序二叉树。本演示程序中，集合的元素设定为大写字母 ABCDEFG ,输出的先序，
中序，后序遍历 。二叉树可以表示为：ABCDEGF,CBEGDFA,CGBFDBA分别 为
中南民族大学管理学院学生实验报告 ..
A B D C F E G
接受的输入数据在进行递归的先序，中序，后序遍历后，分别将 结果打印出来。、
在程序运行的过程中可以看到，以计算机提示用户执行的方2式进行下去，即在
计算机终端上提示“输入二叉树的先序序列”，之后相应的选择
ABC##DE#G##F###后，由用户在键盘上输入 遍历及遍历结果显示出来。、程序
执行的命令包括：首先是二叉树的先序序列被创建输入， 3其次是对输入进去的
先序序列有次序的进行先序，中序，后序遍 历。最后是打印出二叉树的遍历结
果。、测试数据4ABC##DE#G##F### 1)在键盘上输入的先序序列 (ABCDEGF
)先序遍历结果2 (.
中南民族大学管理学院学生实验报告
(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); //先序遍历右子树
} }
中序遍历 // 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)
结点单元模块
构建先序二叉树模块
二叉树遍历模块
主程序模块
各模块之间的调用关系如下:
主程序模块
结点单元模块
构建先序二叉树模块
I二叉树遍历模块
(三)详细设计1、元素类型，结点类型和指针类型 typedef struct node
{
二叉树的元素类型 // char data;
struct node *lchild;
struct node *rchild;
自定义二叉树的结类型 / }BTNode;
定义二叉树的指针 // typedef