数据结构实验报告(共18页).doc

精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
实验目的
（1）学会用先序创建一棵二叉树中序遍历右字树
}
}
void Postorder(BTree T) //后序遍历
{
if(T)
{
Postorder(T->lchild); //后序遍历左子树
Postorder(T->rchild); //后序遍历右子树
printf("%c",T->data); //访问结点
}
}
3、本程序包含的模块
（1）结点单元模块
（2）构建先序二叉树模块
（3）二叉树遍历模块
（4）主程序模块
各模块之间的调用关系如下：
主程序模块
结点单元模块
构建先序二叉树模块
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
二叉树遍历模块
（三）详细设计
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);