数据结构实验树和二叉树操作.doc

文档介绍：《数据结构》实验报告
实验序号:6 实验项目名称:树和二叉树的操作
学号
姓名
专业、班
实验地点
指导教师
实验时间
一、实验目的及要求
1、进一步掌握指针变量、动态变量的含义。
2、掌握二叉树的结构特征,以及各种存储结构的特点及适用范围。
3、掌握用指针类型描述、访问和处理二叉树的运算。
4、掌握用二叉树前序、中序、后序、层次遍历的方法。
二、实验设备(环境)及要求
微型计算机;
windows 操作系统;
Microsoft Visual Studio 。
三、实验内容与步骤
根据P129的方法,将a*b-((c+d*e/f)+g)转化为表达式二叉树(绘图),并写出表达式二叉树的前序、中序和后序遍历顺
先序:-*ab++c*d/efg
中序:a*b-c+d*e/f+g
后序:ab*cdef/*+g+-
2. 链式表表示和实现二叉排序树如下:
#include <>
#include <>
typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiNode, *Bitree;
Bitree root;//定义根结点
void insert_data(int x) /*生成/树*/
{
Bitree p,q,s;
s=(Bitree)malloc(sizeof(BiNode)); //创建结点
s->data=x; //结点赋值
s->lchild=NULL;
s->rchild=NULL;
if(!root)
{
root=s;
}
else
{
p=root;
while(p) /*如何接入二叉排序树的适当位置*/
{
q=p;
if(p->data==x) //相同结点不能重复插入
{
printf("data already exist! \n");
return;
}
else if(x<p->data)
p=p->lchild;
else
p=p->rchild;
}
if(x<q->data)
q->lchild=s;
else
q->rchild=s;
}
}
void main() /*先生成二叉排序树*/
{
int i=1,x; //i记录结点个数,x存放结点值
root=NULL; /*千万别忘了赋初值给root!*/
printf("请输入数据,-9999表示输入结束\n");
do
{
printf("please input data %d:",i);
i++;
scanf("%d",&x); /*从键盘采集数据,以-9999表示输入结束*/
if(x==-9999){
printf("\nNow output data value:\n");
}
else
insert_data(x); /*调用插入数据元素的函0, 0, 数*/
}while(x!=-9999);
}
改写以上程序,实现功能如下(任选三题):
1. 编写函数实现前序、中序和后序遍历。
2. 编写函数实现计算叶节点个数。
3. 编写函数实现层序遍历。
4. 编写函数实现查询二叉树中的某个结点(分查到和查不到两种情况)。

6. 编写函数实现中序非递归遍历(利用栈)
四、实验结果与数据处理
详细记录程序在调试过程中出现的问题及解决方法。记录程序执行的结果(贴图)。
五、分析与讨论
对上机实践结果进行分析,上机的心得体会。
六、教师评语
签名:
日期:
成绩
附源程序清单:
1.#include <>
#include <>
typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiNode, *Bitree;
DLR( Bitree root )
{ if (root !=NULL) { //非空二叉树
printf("%d",root->data); //访问D
DLR(root->lchild); //递归遍历左子树
DLR(root->rchild); //递归遍历右子树
}
return(0);