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

北信-实验三-二叉树实验报告 课程名称 数据结构实验项目二叉树的建立与遍历实验仪器PC系别:计算机科学与技术班级\学号:计科0902/姓名:高锋日期:成绩:指导老师:张仰森一、目的和要求:1、熟练掌握二叉树的定义、性质和存储结构;2、熟练掌握二叉树的三种遍历和线索化以及遍历算法的各种描述形式;3、学会编写实现树的各种操作的算法。二、实验题目:二叉树的建立与遍历:掌握建立二叉树的方法,实现先序、中序、后序三种遍历(递归和非递归)算法;三、源程序(递归和非递归遍历)#include<>#include<>#RUE1#defineFALSE0//树节点结构体typedefstructTNode{chardata;structTNode*lc,*rc;}*Tree;//栈结构体typedefstructStack{Tree*top,*base;//元素为树节点指针的指针!intstacksize;}stack;//栈的初始化voidInitStack(stack&s){//printf("init\n");=(Tree*)malloc(sizeof(TNode)*100);//初始化100个空间if(!){printf("error!\n");return;}=;=0;}//压栈操作voidpush(stack&s,Treet){*=t;//printf("push%c\n",(*)->data);++;//栈顶指针+1++;}//出栈操作Treepop(stack&s){//Tree*p; if(==)//判断是否为空栈{ printf("stackemptyerror!\n"); returnNULL; };//p=;//printf("pop%c\n",(*p)->data);return*();//返回栈顶元素:树节点指针}//获得栈顶元素TreegetTop(stack&s){ if(==) returnNULL;return*();}//判断是否为空栈的函数intstackEmpty(stack&s){//printf("stackempty\n");if(==)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==NU