《数据结构》实验报告
实验序号：6                  实验项目名称：树和二叉树的操作
学  号
姓  名
专业、班
实验地点
指导教师
实验时间
一、实验目的及要求
1、进一步掌握指针变量、动态变量的含义。
2、掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。
3、掌握用指针类型描述、访问和处理二叉树的运算。
4、掌握用二叉树前序、中序、后序、层次遍历的方法。
二、实验设备（环境）及要求
微型计算机；
windows 操作系统；
Microsoft Visual Studio 6.0集成开发环境。
三、实验内容与步骤
1．根据P129的方法，将a*b-((c+d*e/f)+g)转化为表达式二叉树（绘图），并写出表达式二叉树的前序、中序和后序遍历顺序。
2. 链式表表示和实现二叉树如下：
#include <stdio.h>
#include <stdlib.h>
#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(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,x;
    i=1;
    root=NULL;            /*千万别忘了赋初值给root!*/
    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);    /*调用插入数据元素的函数*/
    }       
    while(x!=-9999);       
}
改写以上程序，实现功能如下(任选3题):
1).编写函数实现前序、中序和后序遍历。
2).编写函数实现计算叶节点个数。
3). 编写函数实现层序遍历。
4)．编写函数实现求二叉树的深度
5). 编写函数实现中序非递归遍历(利用栈)
四、分析与讨论
对上机实践结果进行分析，上机的心得体会。
五、教师评语
签名：
日期：
成绩
附源程序清单：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。