《DS 实验报告二》 3208006375-何绮珊
PAGE1 / NUMPAGES10
管理 学院 08信管 专业 5 班
学号 3208006375 姓名 何绮珊
协作者_____________ 教师评定___________
实验题目 二叉树操作
实验目的及要求
1.掌握二叉树的存储实现；
2.掌握二叉树的遍历思想；
3.掌握二叉树的常见算法的程序实现。
实验内容
1. 编写函数,输入字符序列,建立二叉树的二叉链表。
2. 编写函数, 实现该二叉树的先序遍历、中序遍历和后序遍历递归算法，输出各遍历序列；3. 编写函数,实现二叉树的中序非递归遍历算法。
4. 编写函数,求二叉树的叶子个数。
5. 编写函数,交换二叉树每个结点的左子树和右子树。
6. 编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。
实验步骤
（1）认真阅读二叉树的内容，从而掌握二叉树的相关内容，为编写程序做好第一步；
（2）熟悉C语言编程环境（在本次实验中用了VC++6.0）,了解实验的注意事项，以便在实验时能很好地应付可能出现的问题；
（3）通过前面两步，在实验前找到自己的问题，实验前好好思考，若不能自行解决，要问老师和同学解决该问题，做好实验前的充分准备；
（4）上机以前好好编写程序,这样可以利用在机房的时间问老师你所碰到的问题,从而有效解决你的问题;
（5）对该程序进行编译，调试等操作直至程序没有错误，同时可以美化你的程序，使得实验运行结构看上去十分清晰，美观。再运行该程序，从而得到所须结果，记录该结果；
（6）实验结束后，将自己的心得及对相关问题的体会都认真写在实验报告里，好好做好实验报告 。
程序功能需求分析
本程序应具有以下功能：
建立二叉树：
进入程序运行界面后，提示我们输入需要建立的二叉树，并默认以先序序列输入。若第一个输入为“#”，则为空树。否则按照从左子树到右子树的顺序建立该二叉树。建立完二叉树后按“ENTER”键自动进入下一个功能模块的实现。
实现各个遍历递归算法：
实现该二叉树的先序遍历、中序遍历和后序遍历递归算法，逐个访问该二叉树的左右子树，并输出各遍历序列。
实现该二叉树的中序遍历非递归算法：
利用顺序栈的结构实现对该二叉树进行中序遍历，且在实现这个子函数前必须完成对栈的结构的定义、创建空栈、判栈空、判栈满、进栈、退栈、当栈非空时取栈顶元素等函数的建立。最后并能输出其中序遍历非递归结果。
统计出该二叉树中叶子结点个数：
只要该二叉树的移动指针t所指向的结点非空，刚进一步判断其左右子树是否也都为空，让表示叶子结点的变量能够记录叶子结点个数。
实现交换该二叉树所有结点左右子女的操作。
该二叉树非空，刚实现对其交换所有结点左右子女的操作。并分别按照先序遍历、中序遍历和后序遍历递归算法对该交换后的二叉树进行输出。
数据结构设计
1.二叉树结构
typedef struct node
{ char data; /*数据域*/
struct node *lchild; /*左孩子域*/
struct node *rchild; /*右孩子域*/} BTNode;
2.栈的结构
typedef BTNode *DataType;
typedef struct
{ DataType data[MAX];
int top;} SeqStack;
SeqStack *s;
编码设计
#include "stdio.h"
#define PR printf
#define ERROR 0
#define MAX 100
/*============================建立各结构体===============================*/
typedef struct node
{
char data; /*数据域*/
struct node *lchild;
struct node *rchild; /*结点的左右指针，分别指向结点的左右孩子*/
}BTNode;
typedef BTNode *DataType;
typedef struct
{
DataType data[MAX];
int top;
}SeqStack;
SeqStack *s;
/*============================栈的操作===================================*/
SeqStack *createemptystacks() /*创建一个空栈*/
{
SeqStack *s;
s=(SeqStack*)malloc(sizeof(SeqStack));
s->top=0;
return s;
}
int stackemptys(SeqStack *s) /*判栈空*/
{
return s->top==0;
}
int stackfulls(SeqStack *s) /*判栈满*/
{
return s->top==MAX;
}
void pushs(SeqStack *s,DataType x) /*进栈*/
{
if(stackfulls(s))
PR("over flow\n");
else
s->data[s->top++]=x;
}
void pops(SeqStack *s) /*退栈*/
{
if(stackemptys(s))
PR("underflow\n");
else
s->top--;
}
DataType gettops(SeqStack *s) /*栈非空时取栈顶元素*/
{
return s->data[s->top-1];
}
/*============================建立二叉树==================================*/
BTNode *createbintree() /*输入扩充的先序序列，建立二叉树*/
{
BTNode *t;
char x;
scanf("%c",&x);
if(x=='#')
t=NULL; /*读入#，返回空指针 */
else
{
t=(BTNode *)malloc(sizeof(BTNode)); /*生成结点*/
t->data=x;
t->lchild=createbintree(); /*构造左子树*/
t->rchild=createbintree(); /*构造右子树*/
}
return(t);
}
/*==============================树的遍历===================================*/
void preorder(BTNode *t) /*NLR 先序遍历*/
{
if(t!=NULL)
{
PR(" %c\t",t->data); /*访问结点*/
preorder(t->lchild); /*中序遍历左子树*/
preorder(t->rchild); /*中序遍历右子树*/
}
}
/*=========================================================================*/
void inorder(BTNode *t) /*LNR 中序遍历*/
{
if(t!=NULL)
{
inorder(t->lchild); /*中序遍历左子树*/
PR(" %c\t",t->data); /*访问结点*/
inorder(t->rchild); /*中序遍历右子树*/
}
}
/*=========================================================================*/
void postorder(BTNode *t) /*LRN 后序遍历*/
{
if(t!=NULL)
{
postorder(t->lchild); /*后序遍历左子树*/
postorder(t->rchild); /*后序遍历右子树*/
PR(" %c\t",t->data); /*访问结点*/
}
}
/*=========================================================================*/
void inorder1 (BTNode *t) //中序非递归遍历
{
SeqStack *st;
BTNode *p;
if(t==NULL) return;
st=createemptystacks();
p=t;
do{
while(p)
{
pushs(st,p);
p=p->lchild;
}
if(!stackemptys(st))
{
p=gettops(st);
pops(st);
PR("%c",p->data);
p=p->rchild;
}
}
while(!stackemptys(st)||p);
}
/*==========================================================================*/
int leaf(BTNode *t,int n) /*计算叶子结点数*/
{
if(t!=NULL)
{
if(t->lchild==NULL&&t->rchild==NULL)
n++;
n=leaf(t->lchild,n);
n=leaf(t->rchild,n);
}
return(n);
}
/*==========================================================================*/
int Exchange(BTNode *t) /*交换左右子树*/
{
if (t)
{
BTNode *temp;
temp = t->lchild;
t->lchild = t->rchild;
t->rchild = temp;
Exchange ( t->lchild );
Exchange ( t->rchild );
}
}
/*==========================================================================*/
void Display(BTNode *t) /*显示交换左右子树后的整个树*/
{
PR("\n\n ->> 按先序遍历输出为：\n");
preorder(t); /*NLR 先序遍历*/
PR("\n 按中序遍历输出为：\n");
inorder(t); /*LNR 中序遍历*/
PR("\n 按后序遍历输出为：\n");
postorder(t); /*LRN 后序遍历*/
}
/*===============================主函数=============================-=======*/
void main()
{
BTNode *t;
int n=0;
PR("\n——★—☆——★—☆——☆—★—Welcome—☆—★——☆—☆——★—\n");
PR("\n * 实验二 树和二叉树\n");
PR(" * 08信管5班\n");
PR(" * 何绮珊 3208006375\n\n");
PR("* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\n");
PR(" 本程序实现二叉树的常见算法。\n\n");
PR(" ->> 请输入二叉树各元素:(例如 abd##e##cf##g##)\n"); //例如 abd##e##cf##g##
t=createbintree();
PR("\n\n ->> 1.按先序遍历输出为：\n");
preorder(t); /*NLR 先序遍历*/
PR("\n 按中序遍历输出为：\n");
inorder(t); /*LNR 中序遍历*/
PR("\n 按后序遍历输出为：\n");
postorder(t); /*LRN 后序遍历*/
printf("\n\n ->> 2.按中序遍历非递归输出为: ");
inorder1 (t);
n=leaf(t,n);
PR("\n\n ->> 3.该树的叶子结点数是:%d",n);
PR("\n\n ->> 4.交换左右子树的二叉树为(如下按三种方式输出)：");
Exchange(t);
Display(t);
}
实验数据及处理结果
实验数据：
输出结果：
输入界面设计：
各功能模块的输出结果如下：
实验总结
通过这次实验，我体会到深刻理解数据结构的重要性。只有真正理解定义数据类型的好处，才能用好这样一种数据结构。
在一开始定义数据结构时，我因为不细心，总会有或多或少的问题出现，如数据域与指针域的定义类型的不同。在输好了结构体之后，我开始一个个编写本次实验要求实现功能的子函数。
以前在学C语言时总觉得函数的递归调用是一样很复杂的算法，经常会理解不了而导致编程的错误。但在这次实验中，二叉树的先序、中序与后序的输出都用了递归算法。而且用起来并不复杂，这使我更进一步学习理解了函数的递归调用并得到灵活的运用。
当然，本次实验发现自己还有不足的就是对指针认识的不深入，也常常使所设计的程序无法实现需求功能；再者，在利用中序非递归遍历的时候也出现了程序崩溃的错误，这是因为我一开始是打算用链栈的存储结构来实现该子函数的，但在利用栈中的元素是指向二叉链表结点的指针时，我并不能够写出其各遍历的算法语句，因此，经过多番的调试都无法使程序正常运行。于是，我便放弃用链栈，转而用栈的顺序存储结构来实现。
经过本次实验基本上解决的一些所遇到的问题，我对二叉树的结构等有了较为深入的理解。我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步。