数据结构实验报告.doc

中南民族大学管理学院学生实验报告
实验目的
〔1〕学会用先序创建一棵二叉树。
〔2〕学会采用递归算法对二叉树进行先序、中序、后序遍历。
〔3〕学会打印输出二叉树的遍历结果。
实验内容
【问题描述】建立一棵二叉树，块
构建先序二叉树模块
中南民族大学管理学院学生实验报告
二叉树遍历模块
〔三〕详细设计
1、元素类型，结点类型和指针类型
typedef struct node
{
char data; //二叉树的元素类型
struct node *lchild;
struct node *rchild;
}BTNode; //自定义二叉树的结类型
typedef BTNode *BTree; //定义二叉树的指针
2、定义类型之后，要以二叉链表作为存储结构，建立二叉树〔以先序来建立〕。
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);
}
}
当输入的叶子结点完整之后，要return(T)，否则输入将一直持续下去不能跳出来。在程序的设计过程中，在适当的位置插入#对于二叉树的遍历有着十分重要的作用，因此要明白二叉树的先序创建过程如何运行。
中南民族大学管理学院学生实验报告
3、对于二叉树进行先序、中序、后序的遍历。
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); //访问结点
}
}
4、主程序模块的链接。在这个模块中，不仅要实现二叉树先序序列从键盘的输入，还要实现选择三个遍历的输出。主函数的作用旨在使每个程序模块能够链接在一起，调用各个函数以实现最终的目的。
void main()
{
BTree root; //数的根结点
int i;