二叉树的建立与遍历实验报告(c语言编写,附源代码).doc

二叉树的建立与遍历实验报告
级班年月日姓名学号_

建立一棵二叉树,并对其进行遍历(先序、中序、后序),打印输出遍历结果。

本程序用VC编写,实现建立一棵二叉树的功能,并对其进行遍历(先序、中序、后序),并且打印输出遍历结果。
输入的形式和输入值的范围:
输入二叉树的先序,当其结点为空时,需要输入#。(输入的先序仅含字母和#)
输出的形式:输出二叉树的先序、中序、后序。
程序所能达到的功能:实现建立一棵二叉树的功能,并对其进行遍历(先序、中序、后序),并且打印输出遍历结果。
测试数据:
输入数据:
输入ABC##DE#G##F###
输出结果:
二叉树的先序遍历为:
ABCDEGF
二叉树的中序遍历为:
CBEGDFA
二叉树的后序遍历为:
CGEFDBA

为了实现上述程序功能,需要定义二叉链表的抽象数据类型:
typedef struct BinaryTreeNode
{
TElemType data;//二叉树结点中的数据域
struct BinaryTreeNode *lchild , *rchild; //二叉树结点的左孩子和右孩子指针
}BinaryTreeNode ,*BiTree;
基本操作:
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);
主函数main()
CreateBinaryTree
PreOrder
MidOrder
PostOrder
各函数间关系如下:

二叉链表的定义
typedef struct BinaryTreeNode
{
定义一个树结点的数据域;
定义一个该结点的左孩子指针和右孩子指针;
}
void CreateBinaryTree (BiTree &T)//先序建立二叉树
{
输入一个字符量;
if(输入字符== '#') T指针置值为NULL;
else
{
动态申请一个指向二叉树结构体的指针
把输入字符赋值给新指针的数据域data;
调用CreateBinaryTree(新指针的lchild成员);
调用CreateBinaryTre