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

实 验 报 告 课程名称 数据结构 实验项目 二叉树的建立与遍历 实验仪器 PC 系 别： 计算机科学与技术 班级学号： 计科0902/2009011136 姓 名： 高锋 日 期： 2011.04 成 绩： 指导老师 ： 张 仰 森 一、目的和要求： 1、熟练掌握二叉树的定义、性质和存储结构； 2、熟练掌握二叉树的三种遍历和线索化以及遍历算法的各种描述形式； 3、学会编写实现树的各种操作的算法。 二、实验题目： 二叉树的建立与遍历：掌握建立二叉树的方法，实现先序、中序、后序三种遍历（递归和非递归）算法；三、源程序（递归和非递归遍历）#includestdio.h#includestdlib.h#define TRUE 1#define FALSE 0/树节点结构体typedef struct TNodechar data;struct TNode *lc,*rc;*Tree;/栈结构体typedef struct StackTree *top,*base; /元素为树节点指针的指针！int stacksize;stack;/栈的初始化void InitStack(stack s)/ printf(initn); s.base=(Tree *)malloc(sizeof(TNode)*100);/初始化100个空间 if(!s.base) printf(error!n); return; s.top=s.base; s.stacksize=0;/压栈操作void push(stack s,Tree t) *s.top = t;/ printf(push %cn,(*s.top)-data); s.top+; /栈顶指针+1 s.stacksize+;/出栈操作Tree pop(stack s)/ Tree *p;if(s.top=s.base) /判断是否为空栈 printf(stack empty error!n); return NULL; s.stacksize-;/ p=s.top-1;/ printf(pop %cn,(*p)-data); return *(-s.top); /返回栈顶元素：树节点指针/获得栈顶元素Tree getTop(stack s)if(s.top=s.base) return NULL; return *(s.top-1);/判断是否为空栈的函数int stackEmpty(stack s)/ printf(stackemptyn); if(s.top=s.base) return TRUE; else return FALSE;/构造二叉树：递归先序创建void createTree(Tree T) / printf(createtreen); char ch; scanf(%c,ch); if(ch= ) /空格代表空节点 T = NULL; else T=(Tree)malloc(sizeof(TNode); T-data = ch; createTree(T-lc); /创建左子树 createTree(T-rc); /创建右子树 /访问树节点void visit(Tree T)/ printf(visitn); if(T!=NULL) printf(%c ,T-data); /打印data else printf(NULL ERROR!n); return; /递归先序void PreOrder(Tree T) if(T=NULL)return;else printf(%c ,T-data);PreOrder(T-lc);PreOrder(T-rc); /递归中序void InOrder(Tree T) if(T=NULL)return;else InOrder(T-lc);printf(%c ,T-data);InOrder(T-rc); /递归后序void PostOrder(Tree T) if(T=NULL)return;else PostOrder(T-lc);PostOrder(T-rc);printf(%c ,T-data); /先序遍历void preOrder(Tree T) stack s; InitStack(s); /初始化栈 Tree t=T; while(t | !stackEmpty(s) if(t) visit(t); push(s,t); t=t-lc; /走到树的最左边同时进栈并且访问（先序） else t=pop(s); /中间结点出栈 t=t-rc; /右子树进栈 /中序遍历void inOrder(Tree T)/ printf(inordern); stack s; InitStack(s); Tree t=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;/右子树进栈 /后序遍历hardvoid postOrder(Tree T) stack s; InitStack(s); Tree t=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为栈顶元素右子树，右子树接下来进栈 else t=NULL;/提供整个循环结束条件 /此程序二叉树的基本模型为左子树为空，只有右子树的二叉树/当左子树被访问之后，即可认为该左子树为空/后序遍历难点：（需要判断当前节点和parent节点的关系）/当前弹出（可visit）节点若为栈顶（parent）左子树，/则可直接转向右子树，使右子树进栈/若为栈顶（parent）右子树，则得连续出栈，直到当前节点为parent左子树或栈顶为空/主函数，各种调用int main() Tree T=NULL; printf(请先序输入二叉树：(空格代表空树)n); createTree(T); printf(前序序列（递归）：n); PreOrder(T); printf(n); printf(前序序列（非递归）：n); preOrder(T); printf(n); printf(中序序列（递归）：n); InOrder(T); printf(n); printf(中序序列（非递归）：n); inOrder(T); printf(n); printf(后序序列（递归）：n); PostOrder(T); printf(n); printf(后序序列（非递归）：n); postOrder(T