二叉树实验报告模板

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 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