《树和二叉树(一) 数据结构实验》由会员分享，可在线阅读，更多相关《树和二叉树(一) 数据结构实验（15页珍藏版）》请在金锄头文库上搜索。
1、实验报告五月 142015姓名：陈斌 学号：E11314079 专业：13 计算机科学与技术数据结构 第三次实验学号 E11314079 专业 计算机科学与技术 姓名 陈 斌 实验日期 2015.05.14 教师签字 成绩 实 验 报 告【实验名称】 树和二叉树（一） 【实验目的】 1. 掌握二叉树的二叉链表存储表示；2. 掌握二叉树的遍历算法；3. 运用遍历算法求解有关问题。【实验内容】1. 必做内容任务 1：以算法 6.4 创建二叉树的存储结构，树的具体形态自定。任务 2：对任务 1 中的二叉树分别实现先序、中序、后序遍历（递归实现）和中序遍历的非递归实现以及层序遍历；任务 3：统计 1
2、中树的结点总数、叶子结点总数以及树的高度；源代码：head.h: #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/OVERFLO
3、W 在 math.h 中已定义为 3typedef int Status;typedef int Boolean; / 布尔类型head2.h:#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structSElemType *base;SElemType *top;int stacksize;SqStack;typedef struct QNodeQElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front,rear; /* 队
4、头、队尾指针 */LinkQueue;Status InitStack(SqStack &S) /* 构造一个空栈 S */S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW); /* 存储分配失败 */S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status StackEmpty(SqStack &S) /* 若栈 S 为空栈，则返回 TRUE，否则返回 FALSE */if(S.top=S.base)return
5、TRUE;elsereturn FALSE;Status GetTop(SqStack &S,QElemType &e) /* 若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK；否则返回 ERROR */if(S.topS.base)e=*(S.top-1);return OK;elsereturn ERROR;Status Push(SqStack &S,QElemType &e) /* 插入元素 e 为新的栈顶元素 */if(S.top-S.base=S.stacksize) /* 栈满，追加存储空间 */S.base=(SElemType *)realloc(S.base,(S.s
6、tacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)exit(OVERFLOW); /* 存储分配失败 */S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,QElemType &e) /* 若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK；否则返回ERROR */if(S.top=S.base)return ERROR;e=*-S.top;return OK;Status InitQ
7、ueue(LinkQueue &Q) /* 构造一个空队列 Q */Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;return OK;Status QueueEmpty(LinkQueue &Q) /* 若 Q 为空队列, 则返回 TRUE,否则返回 FALSE */if(Q.front=Q.rear)return TRUE;elsereturn FALSE;Status EnQueue(LinkQueue &Q,QElemType e) /* 插入元素 e
8、为 Q 的新的队尾元素 */QueuePtr p=(QueuePtr)malloc(sizeof(QNode);if(!p) /* 存储分配失败 */exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;Status DeQueue(LinkQueue &Q,QElemType &e) /* 若队列不空,删除 Q 的队头元素,用 e 返回其值,并返回 OK,否则返回 ERROR */QueuePtr p;if(Q.front=Q.rear)return ERROR;p=Q.front-next;e=p-data
9、;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;main.cpp:typedef char TElemType;#includehead.htypedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef BiTree QElemType; /* 设队列元素为二叉树的指针类型 */typedef BiTree SElemType; /* 设栈元素为二叉树的指针类型 */#includehead2
10、.hStatus InitBiTree(BiTree &T) /* 操作结果 : 构造空二叉树 T */T=NULL;return OK;Status CreateBiTree(BiTree &T) / 算法 6.4:按先序次序输入二叉树中结点的值(字符型) ，构造二叉链表表示的二叉树 T。TElemType ch;scanf(%c,if(ch= ) /* 空 */T=NULL;elseT=(BiTree)malloc(sizeof(BiTNode);if(!T)exit(OVERFLOW);T-data=ch; /* 生成根结点 */CreateBiTree(T-lchild); /* 构造
11、左子树 */CreateBiTree(T-rchild); /* 构造右子树 */return OK;Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType) /* 初始条件 : 二叉树 T 存在,Visit 是对结点操作的应用函数。算法 6.1 */* 操作结果: 先序递归遍历 T,对每个结点调用函数 Visit 一次且仅一次 */if(T) /* T 不空 */if(Visit(T-data) /* 先访问根结点 */if(PreOrderTraverse(T-lchild,Visit) /* 再先序遍历左子树 */if(PreO
12、rderTraverse(T-rchild,Visit) /* 最后先序遍历右子树 */return OK;return ERROR;elsereturn OK;Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType) /* 初始条件 : 二叉树 T 存在,Visit 是对结点操作的应用函数 */* 操作结果: 中序递归遍历 T,对每个结点调用函数 Visit 一次且仅一次 */if(T) if(InOrderTraverse(T-lchild,Visit) /* 先中序遍历左子树 */if(Visit(T-data) /* 再访问根结
13、点 */if(InOrderTraverse(T-rchild,Visit) /* 最后中序遍历右子树 */return OK;return ERROR;elsereturn OK;Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType) /* 初始条件 : 二叉树 T 存在,Visit 是对结点操作的应用函数 */* 操作结果: 后序递归遍历 T,对每个结点调用函数 Visit 一次且仅一次 */if(T) /* T 不空 */if(PostOrderTraverse(T-lchild,Visit) /* 先后序遍历左子树 */i
14、f(PostOrderTraverse(T-rchild,Visit) /* 再后序遍历右子树 */if(Visit(T-data) /* 最后访问根结点 */return OK;return ERROR;elsereturn OK;Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType) /* 采用二叉链表存储结构，Visit 是对数据元素操作的应用函数。 */* 中序遍历二叉树 T 的非递归算法( 利用栈)，对每个数据元素调用函数 Visit */SqStack S;InitStack(S);while(T|!StackEmpty
15、(S)if(T) /* 根指针进栈 ,遍历左子树 */Push(S,T);T=T-lchild;else /* 根指针退栈 ,访问根结点,遍历右子树 */Pop(S,T);if(!Visit(T-data)return ERROR;T=T-rchild; printf(n);return OK;Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType) /* 采用二叉链表存储结构，Visit 是对数据元素操作的应用函数。算法 6.2 */* 中序遍历二叉树 T 的非递归算法( 利用栈)，对每个数据元素调用函数 Visit */SqStack S;BiTree p;InitStack(S);Push(S,T); /* 根指针进栈 */while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-lchild); /* 向左走到尽头 */Pop(S,p); /* 空指针退栈 */if(!StackEmpty(S) /* 访问结点 ,向右一步 */Pop(S,p);if(!Vis
