《二叉树实验报告模板.doc》由会员分享，可在线阅读，更多相关《二叉树实验报告模板.doc（9页珍藏版）》请在三一文库上搜索。
1、 1、 目的1、 学会实现对二叉树的基本操作；2、 掌握对二叉树各种操作的具体实现，学会运用递归和非递归方法编写对二叉树这种递归数据结构进行处理的算法。2、 实验内容与设计思想1、 实验内容 以顺序存储和二叉链表存储二叉树，建立一棵二叉树并采用前序、中序、后序三种递归和非递归的遍历算法进行二叉树的遍历。2、程序设计（1）.头文件：#include#include#include /* malloc()等 */#include /* INT_MAX等 */#include /* EOF(=Z或F6),NULL */#include /* atoi() */#include /* eof() */
2、#include /* floor(),ceil(),abs() */#include /* exit() */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1 typedef int Status; typedef int Boolean; typedef char TElemType;#define ClearBiTree DestroyBiTreetypedef struct BiNodeint data;struct BiNode *lchild;struct BiNode *rc
3、hild;BiTNode,*BiTree;void CreateBiTree(BiTree &T);void PreOrderTraverse_1(BiTree T);void PreOrderTraverse_2(BiTree T);void InOrderTraverse_1(BiTree T);void InOrderTraverse_2(BiTree T);void PostOrderTraverse_1(BiTree T);void PostOrderTraverse_2(BiTree T); typedef BiTree SElemType; #define STACK_INIT_
4、SIZE 100 typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;void InitStack(SqStack &s);void DestroyStack(SqStack &s);void ClearStack(SqStack &s);int StackLength(SqStack s);int StackEmpty(SqStack s);int Push(SqStack &s,SElemType e);int Pop(SqStack &s,SElemType &e);int GetTop(SqSta
5、ck s,SElemType &e);void DispStack(SqStack s);（2）.函数声明#include Tree1.h#include Tree4.hvoid InitStack(SqStack &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; void ClearStack(SqStack &s)free(s.base)
6、;s.base=s.top=0;s.stacksize=0;int StackLength(SqStack s)return(s.top-s.base);int StackEmpty(SqStack s)if(s.top=s.base)return 1;else return 0;int Push(SqStack &s,SElemType e)if (s.top - s.base = s.stacksize) return OVERFLOW; *s.top+ = e; return OK;int Pop(SqStack &s,SElemType &e)if (s.top = s.base) r
7、eturn ERROR; e = *-s.top; return OK; int GetTop(SqStack s,SElemType &e)if (s.top = s.base) return ERROR; e=*(s.top-1); return OK;void DispStack(SqStack s)SElemType *p;for (p=s.base;pdata=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);void PreOrderTraverse_1(BiTree T)if(T!=NULL)printf(%cn,T-data);P
8、reOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);return OK;void InOrderTraverse_1(BiTree T)if(T!=NULL) InOrderTraverse_1(T-lchild);printf(%c,T-data);InOrderTraverse_1(T-rchild);return OK;void PostOrderTraverse_1(BiTree T):if(T!=NULL) PostOrderTraverse_1(T-lchild); PostOrderTraverse_1(T-lchild);
9、printf(%c,T-data); return OK;void PreOrderTraverse_2(BiTree T)SqStack s;BiTree p; InitStack(s);p=T;while (p!=null | !StackEmpty(s) while (p!=null) visite(p-data); push(s,p); p=p-lchild; if (!StackEmpty(s) p=pop(s); p=p-rchild; PreOrderUnrecvoid InOrderTraverse_2(BiTree T)SqStack s; BiTree p; InitSta
10、ck(s);p=T;while(p|!StackEmpty(s)if (p) Push(s,p); p=p-lchild;elsePop(s,p); printf(%c ,p-data);p=p-rchild;void PostOrderTraverse_2(BiTree T) SqStack s;BiTree p; InitStack(s);p=T; BiTree lastvist = NULL; while (T!=NULL|!StackEmpty(S) while (P!=NULL) Push(S,P); P= P-lchild; GetTop(S,P); if (NULL=P-rchi
11、ld|lastvist=P-rchild) printf(%c,P-data); Pop(S,lastvist); P = P-rchild; (3）.主程序 #include Tree1.h#include Tree4.hint main() BiTree T; CreateBiTree(T); printf(the PreOrderTraverse_1 result is :n); PreOrderTraverse(T); printf(n the InOrderTraverse_1 result is :n); InOrderTraverse_1(T); printf(n the Pos
12、tOrderTraverse_1 result is :n); PostOrderTraverse(T); printf(the PreOrderTraverse_2 result is :n); PreOrderTraverse(T); printf(n the InOrderTraverse_2 result is :n); InOrderTraverse_1(T); printf(n the PostOrderTraverse_2 result is :n); PostOrderTraverse(T); return 1;三、测试数据设计、测试结果分析。 输入数据： a b c d e
13、f g 测试结果：the PreOrderTraverse_1 result is a b c d e f gthr InOrderTraverse_1 result is c b d a e g fthe PostOrderTraverse_1 result is c d b g f e athe PreOrderTraverse_2 result is a b c d e f gthe InOrderTraverse_2 result is c b d a e g fthe PostOrderTraverse_2 result is c d b g f e a四、实验中遇到的问题及解决过程、实验体会和收获。 后续遍历的非递归函数涉及到回溯的方法，开始设计的方案想的太过于简单，所以形成了死循环，总是在最后的节点处不停地循环，后改成回溯后，该问题得到解决。