实验报告课程名称数据结构实验项目二叉树的建立与遍历实验仪器PC系别：计算机科学与技术班级\学号：计科0902/2009011136姓名：高锋日期：2011.04成绩：指导老师：张仰森一、目的和要求：1、熟练掌握二叉树的定义、性质和存储结构；2、熟练掌握二叉树的三种遍历和线索化以及遍历算法的各种描述形式；3、学会编写实现树的各种操作的算法。二、实验题目：二叉树的建立与遍历：掌握建立二叉树的方法，实现先序、中序、后序三种遍历（递归和非递归）算法；三、源程序（递归和非递归遍历）#include#include#defineTRUE1#defineFALSE0//树节点结构体typedefstructTNode{chardata;structTNode*lc,*rc;}*Tree;//栈结构体typedefstructStack{Tree*top,*base;//元素为树节点指针的指针！intstacksize;}stack;//栈的初始化voidInitStack(stack&s){//printf("init\n");s.base=(Tree*)malloc(sizeof(TNode)*100);//初始化100个空间if(!s.base){printf("error!\n");return;}s.top=s.base;s.stacksize=0;}//压栈操作voidpush(stack&s,Treet){*s.top=t;//printf("push%c\n",(*s.top)->data);s.top++;//栈顶指针+1s.stacksize++;}//出栈操作Treepop(stack&s){//Tree*p;if(s.top==s.base)//判断是否为空栈{printf("stackemptyerror!\n");returnNULL;}s.stacksize--;//p=s.top-1;//printf("pop%c\n",(*p)->data);return*(--s.top);//返回栈顶元素：树节点指针}//获得栈顶元素TreegetTop(stack&s){if(s.top==s.base)returnNULL;return*(s.top-1);}//判断是否为空栈的函数intstackEmpty(stack&s){//printf("stackempty\n");if(s.top==s.base)returnTRUE;elsereturnFALSE;}//构造二叉树：递归先序创建voidcreateTree(Tree&T){//printf("createtree\n");charch;scanf("%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\n");if(T!=NULL)printf("%c",T->data);//打印dataelse{printf("NULLERROR!\n");return;}}//递归先序voidPreOrder(TreeT){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);}}//先序遍历voidpreOrder(TreeT){stacks;InitStack(s);//初始化栈Treet=T;while(t||!stackEmpty(s)){if(t){visit(t);push(s,t);t=t->lc;}//走到树的最左边同时进栈并且访问（先序）else{t=pop(s);//中间结点出栈t=t->rc;//右子树进栈}}}//中序遍历voidinOrder(TreeT){//printf("inorder\n");stacks;InitStack(s);Treet=T;while(t||!stackEmpty(s))//t不为NULL即t为真时不再调用stackEmpty判断{if(t){push(s,t);t=t->lc;}//走到树的最左边，进栈else{t=pop(s);//弹出相对的中间结点visit(t);//访问当前节点t=t->rc;//右子树进栈}}}//后序遍历hardvoidpostOrder(TreeT){stacks;InitStack(s);Treet=T;while(t||!stackEmpty(s))//循环结束条件{if(t){push(s,t);t=t->lc;}//走到最左边，进栈else{t=getTop(s);//获得栈顶元素if(t->rc!=NULL)//判断栈顶元素是否有右子树t=t->rc;//若有则右子树进栈else{do{t=pop(s);visit(t);//否则该节点可以弹出并且访问了}while(getTop(s)&&t==getTop(s)->rc);//直到栈顶为空或当前弹出元素不为栈顶元素右子树（这里更郁闷）if(getTop(s))//判断getTop(s)是否为空，否则会出错滴（这里好郁闷）t=getTop(s)->rc;//t为栈顶元素右子树，右子树接下来进栈elset=NULL;//提供整个循环结束条件}}}}//此程序二叉树的基本模型为左子树为空，只有右子树的二叉树//当左子树被访问之后，即可认为该左子树为空//后序遍历难点：（需要判断当前节点和parent节点的关系）//当前弹出（可visit）节点若为栈顶（parent）左子树，//则可直接转向右子树，使右子树进...
