北信-实验三-二叉树.doc

《北信-实验三-二叉树.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告课程名称数据结构实验项目二叉树的建立与遍历实验仪器PC系别：计算机科学与技术班级学号：计科0902/姓名：高锋日期：2011.04成绩：指导老师：张仰森一、目的和要求：1、熟练掌握二叉树的定义、性质和存储结构；2、熟练掌握二叉树的三种遍历和线索化以及遍历算法的各种描述形式；3、学会编写实现树的各种操作的算法。二、实验题目：二叉树的建立与遍历：掌握建立二叉树的方法，实现先序、中序、后序三种遍历（递归和非递归）算法；三、源程序（递归和非递归遍历）#include#include#defineTRUE1#defineFA

2、LSE0//树节点结构体typedefstructTNode{chardata;structTNode*lc,*rc;}*Tree;//栈结构体typedefstructStack{Tree*top,*base;//元素为树节点指针的指针！intstacksize;}stack;//栈的初始化voidInitStack(stack&s){//printf("init");s.base=(Tree*)malloc(sizeof(TNode)*100);//初始化100个空间if(!s.base){printf("error!");return;}s.top

3、=s.base;s.stacksize=0;}//压栈操作voidpush(stack&s,Treet){*s.top=t;//printf("push%c",(*s.top)->data);s.top++;//栈顶指针+1s.stacksize++;}//出栈操作Treepop(stack&s){//Tree*p;if(s.top==s.base)//判断是否为空栈{printf("stackemptyerror!");returnNULL;}s.stacksize--;//p=s.top-1;//printf("pop%c",(*p)->data

4、);return*(--s.top);//返回栈顶元素：树节点指针}//获得栈顶元素TreegetTop(stack&s){if(s.top==s.base)returnNULL;return*(s.top-1);}//判断是否为空栈的函数intstackEmpty(stack&s){//printf("stackempty");if(s.top==s.base)returnTRUE;elsereturnFALSE;}//构造二叉树：递归先序创建voidcreateTree(Tree&T){//printf("createtree");charch;sc

5、anf("%c",&ch);if(ch=='')//空格代表空节点T=NULL;else{T=(Tree)malloc(sizeof(TNode));T->data=ch;createTree(T->lc);//创建左子树createTree(T->rc);//创建右子树}}//访问树节点voidvisit(TreeT){//printf("visit");if(T!=NULL)printf("%c",T->data);//打印dataelse{printf("NULLERROR!");return;}}//递归先序voidPreOrder(TreeT)

6、{if(T==NULL)return;else{printf("%c",T->data);PreOrder(T->lc);PreOrder(T->rc);}}//递归中序voidInOrder(TreeT){if(T==NULL)return;else{InOrder(T->lc);printf("%c",T->data);InOrder(T->rc);}}//递归后序voidPostOrder(TreeT){if(T==NULL)return;else{PostOrder(T->lc);PostOrder(T->rc);printf("%c",T->data)

7、;}}//先序遍历voidpreOrder(TreeT){stacks;InitStack(s);//初始化栈Treet=T;while(t

8、

9、!stackEmpty(s)){if(t){visit(t);push(s,t);t=t->lc;}//走到树的最左边同时进栈并且访问（先序）else{t=pop(s);//中间结点出栈t=t->rc;//右子树进栈}}}//中序遍历voidinOrder(TreeT){//printf("inorder");stacks;InitStack(s);Treet=T;while(t

10、

11、!stackEmpty(s))//

12、t不为NULL即t为真时