树和二叉树(一)数据结构实验.docx

文档介绍：实验报告
五月 14
2015
姓名:陈斌学号:E11314079 专业:13计算机科学与技术
数据结构第三次实验
学号 E11314079 专业计算机科学与技术姓名陈斌
实验日期 教师签字成绩
实验报告
【实验名称】树和二叉树(一)
【实验目的】
掌握二叉树的二叉链表存储表示;
掌握二叉树的遍历算法;
运用遍历算法求解有关问题。
【实验内容】
必做内容
任务1:,树的具体形态自定。
任务2:对任务1中的二叉树分别实现先序、中序、后序遍历(递归实现) 和中序遍历的非递归实现以及层序遍历;
任务3:统计1中树的结点总数、叶子结点总数以及树的高度;
源代码:
:
#include<>
#include<>
#include<> //malloc( )
#include<> // INT ,MAX
#include<> //EOF,NULL
#include<> //atoi( )
#include<> //eof( )
#include<> //floor( ),ceil( ),abs( )
#include<> //exit( )
#include<> //cout,cin
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
//OVERFLOW 在 中已定义为3
typedef int Status;
typedef int Boolean; // 布尔类型
:
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,rear; /* 队头、队尾指针*/
}LinkQueue;
Status InitStack(SqStack &S)
{ /* 构造一个空栈S */
=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!)
exit(OVERFLOW); /* 存储分配失败*/
=;
=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack &S)
{ /* 若栈S为空栈,则返回TRUE,否则返回FALSE */
if(==)
return TRUE;
else
return FALSE;
}
Status GetTop(SqStack &S,QElemType &e)
{ /* 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR */
if(>)
{
e=*(-1);
return OK;
}
else
return ERROR;
}
Status Push(SqStack &S,QElemType &e)
{ /* 插入元素e为新的栈顶元素*/
if(->=) /* 栈满,追加存储空间*/
{
=(SElemType *)realloc(,(+STACKINCREMENT)*sizeof(SElemType));
if(!)
exit(OVERFLOW); /* 存储分配失败*/
=+;
+=STACKINCREMENT;
}
*++=e;
return OK;
}
Status Pop(SqStack &S,QElemType &e)
{ /* 若栈