二叉树的建立与遍历实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
级 班 年 月 日 姓名 学号_
1．实验题目
建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。
2．需求分析
本程序用VC编写，实现建立一棵二叉树的功能，并对其进行遍历（先序、中序、后序），并且打印输出遍历结果。
1 输入的形式和输入值的范围：
输入二叉树的先序，当其结点为空时，需要输入#。（输入的先序仅含字母和#）
2 输出的形式：输出二叉树的先序、中序、后序。
3 程序所能达到的功能：实现建立一棵二叉树的功能，并对其进行遍历（先序、中序、 后序），并且打印输出遍历结果。
4 测试数据：
输入数据：
输入ABC##DE#G##F###
输出结果：
二叉树的先序遍历为：
ABCDEGF
二叉树的中序遍历为：
CBEGDFA
二叉树的后序遍历为：
CGEFDBA
3．概要设计
1) 为了实现上述程序功能，需要定义二叉链表的抽象数据类型：
typedef struct BinaryTreeNode
{
TElemType data;//二叉树结点中的数据域
struct BinaryTreeNode *lchild , *rchild; //二叉树结点的左孩子和右孩子指针
}BinaryTreeNode ,*BiTree;
基本操作：
A. void CreateBinaryTree (BiTree &T)
初始条件：无
操作结果：建立了二叉树。
B. void PreOrder(BiTree T)
初始条件：存在一棵二叉树
操作结果：先序遍历二叉树，并且输出先序遍历的结果。
C. void MidOrder(BiTree T)
初始条件：存在一棵二叉树
操作结果：中序遍历二叉树，并且输出中序遍历的结果。
D. void PostOrder(BiTree T)
初始条件：存在一棵二叉树
操作结果：后序遍历二叉树，并且输出后序遍历的结果。
程序包含5个函数：
主函数main()
先序建立二叉树 void CreateBinaryTree (BiTree &T)
先序遍历二叉树，并且输出先序遍历的结果 void PreOrder(BiTree T);
中序遍历二叉树，并且输出中序遍历的结果 void MidOrder(BiTree T);
序遍历二叉树，并且输出后序遍历的结果 void PostOrder(BiTree T);
各函数间关系如下：
4．详细设计
1) 二叉链表的定义
typedef struct BinaryTreeNode
{
定义一个树结点的数据域;
定义一个该结点的左孩子指针和右孩子指针;
}
2) void CreateBinaryTree (BiTree &T)//先序建立二叉树
{
输入一个字符量;
if(输入字符== '#') T指针置值为NULL;
else
{
动态申请一个指向二叉树结构体的指针
把输入字符赋值给新指针的数据域data;
调用CreateBinaryTree(新指针的lchild成员);
调用CreateBinaryTree(新指针的rchild成员);
}
}
3) void PreOrder(BiTree T) //先序遍历二叉树
{
if(T指针不为NULL)
{
输出T的data域;
先序遍历左子树;
先序遍历右子树;
}
}
4) void MidOrder(BiTree T) //中序遍历二叉树
{
if(T指针不为NULL)
{
中序遍历左子树;
输出T的data域;
中序遍历右子树;
}
}
5) void PostOrder(BiTree T) //中序遍历二叉树
{
if(T指针不为NULL)
{
后序遍历左子树;
后序遍历右子树;
输出T的data域;
}
}
5．调试分析
在编写程序过程中，我将scanf（”%c”,&ch）中的%c写成%d，程序运行了一段时间没有结果，经过检查，发现了这个错误。编写程序不能有一点马虎，否则后续纠错工作很辛苦，编写程序的进度变慢。
6．使用说明
程序名为：二叉树遍历.exe，运行环境为DOS。程序执行后显示
输入字符，先序建立二叉树：
此时请输入一棵二叉树的先序，并且当结点为空时，输入#
输入完成后，会输出该二叉树的先序遍历、中序遍历和后序遍历
7．测试结果
1) 输入数据：
输入ABC##DE#G##F###
输出结果：
二叉树的先序遍历为：
ABCDEGF
二叉树的中序遍历为：
CBEGDFA
二叉树的后序遍历为：
CGEFDBA
2) 输入数据：
输入AB##C##
输出结果：
二叉树的先序遍历为：
ABC
二叉树的中序遍历为：
BAC
二叉树的后序遍历为：
BCA
3) 二叉树如下：
先序输入这棵二叉树，程序运行结果为：
程序源代码：
#include
#include
typedef char TElemType;
typedef struct BinaryTreeNode//二叉链表的存储结构
{
TElemType data;
struct BinaryTreeNode *lchild , *rchild;
}BinaryTreeNode ,*BiTree;
void CreateBinaryTree (BiTree &T)//先序建立二叉树
{
char ch;
scanf("%c",&ch);
if(ch == '#') T=NULL;
else
{
if(!(T = (BinaryTreeNode *)malloc (sizeof(BinaryTreeNode))))
exit (-1);
//判断malloc函数是否获得符合要求的内存块，是则继续程序，否则使用exit函数强制退出程序
//如果malloc函数无法获得符合要求的内存块，malloc函数会返回NULL指针
T->data=ch;
CreateBinaryTree(T->lchild);
CreateBinaryTree(T->rchild);
}
}
void PreOrder(BiTree T)//先序遍历二叉树
{
if(T)
{
printf("%c ",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void MidOrder(BiTree T)//中序遍历二叉树
{
if(T)
{
MidOrder(T->lchild);
printf("%c ",T->data);
MidOrder(T->rchild);
}
}
void PostOrder(BiTree T)//后序遍历二叉树
{
if(T)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c ",T->data);
}
}
void main()
{
BiTree Tree;
printf("输入字符，先序建立二叉树：\n");
CreateBinaryTree(Tree);
printf("二叉树的先序遍历为：\n");
PreOrder(Tree);
printf("\n二叉树的中序遍历为：\n");
MidOrder(Tree);
printf("\n二叉树的后序遍历为：\n");
PostOrder(Tree);
getchar();
getchar();
}
浙公网安备 33021202002483