数据结构实验6_树和二叉树的操作

《数据结构》实验报告

实验序号：6 实验项目名称：树和二叉树的操作 学 号 实验地点 姓 名 指导教师 专业、班 实验时间 一、实验目的及要求 1、进一步掌握指针变量、动态变量的含义。 2、掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算。 4、掌握用二叉树前序、中序、后序、层次遍历的方法。 二、实验设备（环境）及要求 微型计算机； windows 操作系统； Microsoft Visual Studio 6.0集成开发环境。 三、实验内容与步骤 1．根据P129的方法，将a*b-((c+d*e/f)+g)转化为表达式二叉树（绘图），并写出表达式二叉树的前序、中序和后序遍历顺序。 2. 链式表表示和实现二叉树如下： #include #include #define max 50 typedef struct liuyu { int data; struct liuyu *lchild,*rchild; }test; liuyu *root,*p,*q[max]; int sum=0; int m=sizeof(test); void insert_data(int x) /*生成二叉排序树*/ { liuyu *p,*q,*s;

s=(test*)malloc(m); s->data=x; s->lchild=NULL; s->rchild=NULL; if(!root) { root=s; } p=root; while(p) /*如何接入二叉排序树的适当位置*/ { q=p; if(p->data==x) { printf(\"data already exist! \\n\"); return; } else if(xdata) p=p->lchild; else p=p->rchild; } if(xdata) q->lchild=s; else q->rchild=s; } void main() /*先生成二叉排序树*/ { int i,x; i=1; root=NULL; /*千万别忘了赋初值给root!*/ do { printf(\"please input data%d:\ i++; scanf(\"%d\从键盘采集数据，以-9999表示输入结束*/ if(x==-9999){ printf(\"\\nNow output data value:\\n\"); } else insert_data(x); /*调用插入数据元素的函数*/ }

while(x!=-9999); } 改写以上程序，实现功能如下(任选3题): 1).编写函数实现前序、中序和后序遍历。 2).编写函数实现计算叶节点个数。 3). 编写函数实现层序遍历。 4)．编写函数实现求二叉树的深度 5). 编写函数实现中序非递归遍历(利用栈) 四、分析与讨论 对上机实践结果进行分析，上机的心得体会。 五、教师评语 签名： 日期： 附源程序清单：

成绩