抽象类型实现二叉树实验报告(共56页)

1、精选优质文档-倾情为你奉上一、 设计任务、要求及所用软件环境或工具设计任务：选用顺序存储结构和二叉链表存储结构实现抽象数据类型二叉树的基本操作编译环境：VC+6.0二、 抽象数据类型定义二叉树抽象类型定义如下ADT BinaryTree基本对象D：D是具有相同特性的数据元素的集合。数据关系R：若D，则R，称BinaryTree为空二叉树；若D，则RH，H是如下二元关系：(1)在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；(2)若D-root，则存在D-root=D1，Dr，且D1Dr；(3)若D1，则D1中存在惟一的元素x1，<root,x1>H,且存在D1上的关系

2、H1H； 若Dr，则Dr中存在惟一的元素xr，<root,xr>H,且存在D1上的关系HrH； Hroot，xl，root，xr，Hl，Hr；(4)(Dl，Hl)是一棵符合本定义的二叉树，称为根的左子树，(Dr，Hr)是一棵符合本定 义的二叉树，称为根的右子树。基本操作P：InitBiTree(&T);操作结果：构造空二叉树T。DestroyBiTree(&T);初始条件：二叉树T存在操作结果：销毁二叉树TCreateBiTree(&T, definition);初始条件：definition给出二叉树T的定义操作结果：按definition构造二叉树TCl

3、earBiTree(&T);初始条件：二叉树T存在操作结果：将二叉树T清为空树BiTreeEmpty(T);初始条件：二叉树T存在操作结果：若T为空二叉树，则返回TRUE，否则返回FALSEBiTreeDepth(T);初始条件：二叉树T存在操作结果：返回T的深度Root(T);初始条件：二叉树T存在操作结果：返回T的根Value(T,e);初始条件：二叉树T存在，e是T中某个结点操作结果：返回e的值Assign(T,&e,value);初始条件：二叉树T存在，e是T中某个结点操作结果：结点e赋值为valueParent(T,e);初始条件：二叉树T存在，e是T中某个结点操作结

4、果：若e是T的非根节点，则返回它的双亲，否则返回“空”LeftChild(T,e);初始条件：二叉树T存在，e是T中某个结点操作结果：返回e的左孩子。若e无左孩子，则返回“空”RightChild(T,e);初始条件：二叉树T存在，e是T中某个结点操作结果：返回e的右孩子。若e无右孩子，则返回“空”LeftSibling(T,e);初始条件：二叉树T存在，e是T中某个结点操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”RightSibling(T,e);初始条件：二叉树T存在，e是T中某个结点操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”InsertChi

5、ld(T,p,LR,c);初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子 树为空。操作结果：根据LR为0或1，插入c为T中p所指向结点的左或右子树。p所指结点的原有左或 右子树则成为c的右子树DeleteChild(T,p,LR);初始条件：二叉树T存在，p指向T中某个结点，LR为0或1.操作结果：根据LR为0或1，删除T中P所指结点的左或右子树PreOrderTraverse(T,Visit();初始条件：二叉树T存在，Visit是对结点操作的应用函数操作结果：先序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操 作失败。

6、InOrderTraverse(T,Visit();初始条件：二叉树T存在，Visit是对结点操作的应用函数操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操 作失败PostOrderTraverse(T,Visit();初始条件：二叉树T存在，Visit是对结点操作的应用函数操作结果：后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操 作失败LevelOrderTraverse(T,Visit();初始条件：二叉树T存在，Visit是对结点操作的应用函数操作结果：层次遍历T，对每个结点调用函数Visit一次且仅一次。一

7、旦visit（）失败，则操 作失败 ADT BinaryTree三、 存储结构定义及各基本操作的实现1. 公用头文件base.h/*Includes*#include"stdio.h"#include"conio.h"#include"stdlib.h"#include"windows.h"#include"malloc.h"#include"math.h"#define OK 1#define TRUE1#defineERROR0#defineFALSE0#defineMA

8、XSIZE100/最多结点数typedefintStatus;typedefcharTElemType;/结点类型为字符型/*其它操作*shortwherex()/返回光标的x坐标CONSOLE_SCREEN_BUFFER_INFO csbinfo;GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE),&csbinfo); return csbinfo.dwCursorPosition.X;shortwherey()/返回光标的y坐标CONSOLE_SCREEN_BUFFER_INFO csbinfo;GetConsole

9、ScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE),&csbinfo); return csbinfo.dwCursorPosition.Y;void gotoxy(short x,short y)/移动光标到（x，y）坐标COORD point = x, y; SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), point);void SetColor(unsigned short TextColor=7)/设置字体颜色 unsigned BackGroundColor =

10、0;HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hCon,TextColor|BackGroundColor); voidPrint(unsigned x,unsigned y)/在(x,y)位置显示方框SetColor(14);gotoxy(x,y+);printf("");gotoxy(x,y+);printf(" "); gotoxy(x,y+);printf(" "); gotoxy(x,y+);printf(" &qu

11、ot;); gotoxy(x,y+);printf(" "); gotoxy(x,y+);printf(" "); gotoxy(x,y+);printf(" "); gotoxy(x,y+);printf(" "); gotoxy(x,y+);printf(" "); gotoxy(x,y+);printf(" "); gotoxy(x,y+);printf("");SetColor();voidClearWindow(unsigned x1 = 50,

12、unsigned y1 = 0,unsigned x2 = 80,unsigned y2 = 10)/将屏幕(x1,y1,x2,y2)区域清屏,并显示方框unsignedi,j;for(i = x1;i < x2;i+)for(j = y1; j < y2;j+)gotoxy(i,j);printf(" ");Print(x1-2,y1);voidClearLine(unsigned y = 23)/清除第y行与y+1行的字符，并使光标在行首，默认清除第23与24行for(int i = 0;i < 158;i+) gotoxy(i,y);putchar(

13、' ');gotoxy(0,wherey()-1);voidClearAera(unsigned x = 96, unsigned y = 22)/清除(0,y)-(x,y+1)区域的字符，并使光标移动到yfor(unsigned i = 0; i<x;i+)gotoxy(i%(x/2),y+(i/48);putchar(' ');gotoxy(0,y);/*StatusVisit(TElemType e)/二叉树结点Visit函数，显示字符的值printf("%c ",e);return OK;2. 顺序存储结构存储结构定义：/ *二

14、叉树顺序存储结构*/* 在一棵具有n个结点的满二叉树中，从树根起，自上层到下层，/* 逐层从左到右给所有结点从1开始编号到n，非满二叉树补为满二叉树再编号，/* 存储到数组中（0号单元存储结点个数），空结点规定为'&'。 */ typedefTElemType*SqBiTree;/ 0号单元存储结点个数算法设计：voidInitBiTree(SqBiTree &T)/ 构造空二叉树TT=NULL;voidDestroyBiTree(SqBiTree &T)/ 销毁二叉树Tif(T)free(T);T = NULL;StatusCreateBiTree(S

15、qBiTree &T)/ 以完全二叉树形式层次建立二叉树T，不存在的结点用'&'表示,'#'结束录入inti = 0;charch;if(T)free(T);T = (SqBiTree)malloc(MAXSIZE * sizeof(char);if(!T)exit(OVERFLOW);fflush(stdin);scanf("%c",&ch);while(ch != '#')T+i = ch;/ 保存到从下标1开始的数组Tscanf("%c",&ch);T0 = i;/ 0

16、号单元记录总结点格式（包括无效结点'&'）return OK;StatusCreateBiTree(SqBiTree &T, char *str)/ 字符串str储存着完全二叉树的层次序列，'&'表示空节点/ 由字符串数组str建立顺序存储二叉树Tif(T)free(T);T = (SqBiTree)malloc(MAXSIZE * sizeof(char);if(!T)exit(OVERFLOW);strcpy(T,str);/ 直接复制T0 = strlen(str)-1 ;/ 长度减去0号单元return OK;voidClearB

17、iTree(SqBiTree &T)/ 将二叉树置为空树if(T)free(T);T = NULL;StatusBiTreeEmpty(SqBiTree T)/ 若T为空二叉树，则返回TRUE，否则返回FALSEif(!T | !T0)return TRUE;elsereturn FALSE;intBiTreeDepth(SqBiTree T)/ 返回T的深度if(!BiTreeEmpty(T)/ 若完全二叉树不空return (int)(log(T0) / log(2) +1);/ 深度为log2N+1elsereturn 0;intRoot(SqBiTree T)/ 返回T的根节点

18、的序号，若不存在，则返回0if(T && T0)return 1;elsereturn 0;TElemTypeValue(SqBiTree T,int i)/ 二叉树T存在，i是T中某个结点/ 返回i结点的值，如果i结点不存在，则返回&returnTi;StatusAssign(SqBiTree T,int i,TElemType value)/ 二叉树T存在，i是T中某个结点/ 若结点i存在，则赋值为value，并返回OK，否则返回ERRORif(Ti='&' | i > T0 | !i) return ERROR;Ti = value;

19、return OK;intParent(SqBiTree T,inti)/ 若结点i是T的非根节点，则返回它的双亲的序号，否则返回0if(i>T0 | i<2 | Ti = '&') return 0;elsereturn i/2;intLeftChild(SqBiTree T,inti)/ 返回第i个结点的左孩子的序号。若i无左孩子，则返回0if(i<= T0 && i>0 && 2*i<T0 && T2*i!='&')return 2*i;elsereturn 0;

20、intRightChild(SqBiTree T,inti)/ 返回第i个结点的右孩子的序号。若i无左孩子，则返回“空”if(i<=T0 && i>0 && (2*i+1)<T0 && T2*i+1!='&')return 2*i+1;elsereturn 0;intLeftSibling(SqBiTree T,inti)/ 返回第i个结点的左兄弟的序号if(i <= T0 && i > 0 && Ti-1 != '&' &&am

21、p; Ti/2 = T(i-1)/2)/ 父亲相同return i-1;elsereturn 0;intRightSibling(SqBiTree T,inti)/ 返回第i个结点的右兄弟的序号if(i+1 <= T0 && i > 0 && Ti+1 != '&' && Ti/2 = T(i+1)/2)/ 父亲相同return i+1;elsereturn 0;StatusPreOrderTraverse(SqBiTree T,Status (*Visit)(TElemType e), int i = 1)/

22、 递归先序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败。if(i <= T0 && Ti != '&')if(Visit(Ti)if(PreOrderTraverse(T, Visit, 2 * i)if(PreOrderTraverse(T, Visit, 2 * i +1) return OK;return ERROR;return OK; StatusPreOrderTraverse2(SqBiTree T,Status (*Visit)(TElemType e), int i = 1)/ 用栈非递归先

23、序遍历二叉树Tintstack100,top = 0;/ 初始化栈顶指针while(i <= T0 && Ti != '&') | top > 0)/ 结点存在或栈不空if(i <= T0 && Ti != '&')/ 根指针入栈，遍历左子树if(!Visit(Ti) return ERROR;/ 访问根节点stacktop+ = i; i = i*2;else/ 根指针退栈，遍历右子树i = stack-top;i = i*2+1;return OK;StatusInOrderTraverse(

24、SqBiTree T,Status (*Visit)(TElemType e),int i = 1)/ 递归中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败if(i <= T0 && Ti != '&')if(InOrderTraverse(T, Visit, 2 * i)if(Visit(Ti)if(InOrderTraverse(T, Visit, 2 * i +1) return OK;returnERROR;return OK;StatusInOrderTraverse2(SqBiTree T,Sta

25、tus (*Visit)(TElemType e),int i = 1)/ 用栈非递归中序遍历二叉树Tintstack100,top = 0;while(i <= T0 && Ti != '&') | top > 0)/ 结点存在或栈不空if(i <= T0 && Ti != '&')/ 根指针入栈，遍历左子树stacktop+ = i; i = i*2;else/ 根指针退栈，遍历右子树i = stack-top;if(!Visit(Ti) return ERROR;i = i*2+1;retu

26、rn OK;StatusPostOrderTraverse(SqBiTree T,Status (*Visit)(TElemType e),int i = 1)/ 递归后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败if(i <= T0 && Ti != '&')if(PostOrderTraverse(T, Visit, 2 * i)if(PostOrderTraverse(T, Visit, 2 * i +1) if(Visit(Ti)return OK;return ERROR;return OK;St

27、atusPostOrderTraverse2(SqBiTree T,Status (*Visit)(TElemType e)/ 非递归后序遍历二叉树T/ 与非递归先序中序的区别在于，多定义一tag数组，用来记录访问次数/ 第二次访问时才退栈。intstack100 ,top = 0, tag100, i = 1;while(i <= T0 && Ti != '&') | top > 0)if(i <= T0 && Ti != '&')/ 根指针入栈，遍历左子树tagtop = 0;stacktop

28、+ = i;i = 2 * i;elseif(tagtop-1 = 0)/ 若第一次访问，则遍历右子树tagtop-1 +;i = stacktop-1;i = 2 * i + 1;else if(tagtop-1 = 1)/ 若第二次访问，则访问根节点，根指针退栈if(!Visit(Tstack-top) return ERROR; return OK;StatusLevelOrderTraverse(SqBiTree T,Status (*Visit)(TElemType e)/ 层次遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败/ 由于顺序存储的二叉

29、树刚好是层次遍历所成，只需从数组1到T0访问即可inti, k = 1;for(i = 1; i <= T0 && k; i+) if(Ti != '&') k = Visit(Ti);/ k记录访问是否出错returnk;intSearchBiTree(SqBiTree T,TElemType value)/ 返回二叉树T中值为value的结点的下标，如不存在则返回0if(!T | !T0) return 0;/ 若为空树inti;for(i = 1; i <= T0; i+)/ 搜索数组值为value的序号if(Ti = value) r

30、eturn i;return 0;voidPrintBiTree(SqBiTree T)/* 以二叉树的逻辑结构形式显示二叉树/* 计算好满二叉树每个编号的结点的对应的位置/* 根据二叉树是否存在结点，到相应位置显示/ 和结点的值 */ClearWindow();/ 每次显示新的二叉树要把原区域信息清除SetColor(2); if(T0 = 0 | BiTreeDepth(T) > 5) return ; char l = 47, r = 92, i = 0;/ l为/',r为字符''shortx = 46,y = 0;/ 初始化根节点到屏幕右上角打印/* 由于

31、前3层结点位置无规律，只能逐个打印 */gotoxy(x+18,y+1); putchar(T1); if(T2 != '&'&&i<=T0)gotoxy(x+15,y+2);putchar(l);gotoxy(x+14,y+2);putchar('_');gotoxy(x+12,y+3);putchar(T2); if(T3 != '&'&&i<=T0)gotoxy(x+21,y+2);putchar(r);gotoxy(x+22,y+2);putchar('_');g

32、otoxy(x+24,y+3);putchar(T3); if(T4 != '&'&&i<=T0)gotoxy(x+10,y+4);putchar(l); gotoxy(x+8,y+5);putchar(T4); if(T5 != '&'&&i<=T0)gotoxy(x+14,y+4);putchar(r);gotoxy(x+14,y+5);putchar(T5); if(T6 != '&'&&i<=T0)gotoxy(x+22,y+4);putchar(l

33、);gotoxy(x+22,y+5);putchar(T6); if(T7 != '&'&&i<=T0)gotoxy(x+26,y+4);putchar(r);gotoxy(x+28,y+5);putchar(T7);/* 打印第4层 */ for(i = 8,x += 5 ,y+=7;i <= 15&& i <= T0;i+,x+=4) if(i=10|i=14) -x; if(Ti != '&') gotoxy(x,y);putchar(Ti); if(i%2=0) if(i=14)gotox

34、y(x,y-1);else gotoxy(x+1,y-1);putchar(l); else if(i=9)gotoxy(x,y-1); else gotoxy(x-1,y-1);putchar(r);/* 打印第5层 */ for(i = 16,x -= 31,y += 2;i <= 31 && i<=T0; i+,x += 2) if(i=20|i=28) -x; if(Ti != '&') gotoxy(x,y);putchar(Ti);gotoxy(x,y-1); if(i%2=0) putchar(l); else putchar(

35、r); gotoxy(0,23);SetColor();3. 二叉链表存储结构存储结构定义：typedef charTElemType;typedefstructBiTNodeTElemTypedata;structBiTNode*lchild;structBiTNode*rchild;/ 左右孩子指针BiTNode, *BiTree;算法设计：voidInitBiTree(BiTree &T)/ 构造空二叉树TT=NULL;StatusDestroyBiTree(BiTree &T)/ 销毁二叉树Tif(!T)return ERROR;DestroyBiTree(T->

36、lchild);/ 删除左子树DestroyBiTree(T->rchild);/ 删除右子树free(T);T = NULL;return OK;StatusCreateBiTree(BiTree &T)/ 先序建立二叉树T,空格表示空结点TElemType ch;fflush(stdin);ch = getch();putchar(ch);if(ch = ' ') T = NULL;elseT = (BiTree)malloc(sizeof(BiTNode);if(!T) exit(OVERFLOW);T->data = ch;/ 生成头结点Create

37、BiTree(T->lchild);/ 构造左子树CreateBiTree(T->rchild);/ 构造右子树return OK;StatusCreateBiTree(BiTree &T,char *str,unsigned i = 1)/ str储存着二叉树的层次序列，stri='&'表示结点不存在/ i为当前要创建结点对应的数组序号节点/ 由字符数组str先序建立一棵二叉树Tif(stri = '&' | i >= strlen(str) T = NULL;/ 第i个结点不存在elseT = (BiTree)mal

38、loc(sizeof(BiTNode);if(!T) exit(OVERFLOW);T->data = stri;/ 生成根节点CreateBiTree(T->lchild, str, i*2);/ 构造左子树CreateBiTree(T->rchild, str, i*2+1);/ 构造右子树return OK;StatusClearBiTree(BiTree &T)/ 递归后序遍历，将二叉树T清为空树if(!T)return ERROR;DestroyBiTree(T->lchild);/ 销毁左子树DestroyBiTree(T->rchild);/

39、 销毁右子树free(T);/ 删除根节点T = NULL;return OK;StatusBiTreeEmpty(BiTree T)/ 若T为空二叉树，则返回TRUE，否则返回FALSEif(!T)return TRUE;elsereturn FALSE;intBiTreeDepth(BiTree T)/ 返回T的深度intdl, dr;if(!T)return 0;dl = BiTreeDepth(T->lchild);/ 求左子树深度dr = BiTreeDepth(T->rchild);/ 求右子树深度return (dl > dr ? dl:dr) + 1;/ 深度

40、等于左右子树较大值加1BiTreeRoot(BiTree T)/ 返回二叉树T的根return T;TElemTypeValue(BiTree T,int&k)/ 返回二叉树先序遍历第k个节点的值，不存在则返回空格' 'if(!T | k < 1)return ' 'if(-k = 0 && T)return T->data;char elem = Value(T->lchild,k);/ 遍历左孩子if(elem != ' ')return elem ;/ 若第k个结点在左子树else return V

41、alue(T->rchild,k);voidAssign(BiTree T,BiTree &p,TElemType value)/ 二叉树T存在，e是T中某个结点/ 结点p赋值为value if(p) p->data = value;BiTreeParent(BiTree T,BiTree p)/ 若p指向T的非根节点，则返回它的双亲，否则返回“空”if(!T|T = p) return NULL;/ 树空或所求为根的双亲if(T->lchild = p|T->rchild = p) return T;BiTreef = Parent(T->lchild,

42、p) ;/ 遍历左子树if(f)returnf;/ 所求父亲在根的左子树elsereturnParent(T->rchild,p);BiTreeLeftChild(BiTree T,BiTree p)/ 返回p的左孩子。若p无左孩子，则返回“空”return p->lchild;BiTreeRightChild(BiTree T,BiTree p)/ 返回p的右孩子。若p无右孩子，则返回“空”return p->rchild;BiTreeLeftSibling(BiTree T,BiTree p)/ 返回p的左兄弟。若p是T的左孩子或无左兄弟，则返回“空”BiTree f =

43、 Parent(T,p);/ 求所求结点p的双亲if(f && f->rchild = p)/ 若双亲存在且p为右孩子return f->lchild;/ 则返回双亲的左孩子elsereturn NULL;BiTreeRightSibling(BiTree T,BiTree p)/ 返回p的右兄弟。若p是T的右孩子或无右兄弟，则返回“空”BiTree f = Parent(T,p);/ 求结点p双亲if(f && f->lchild = p)/ 若双亲存在且p为左孩子return f->rchild;/ 则返回双亲的右孩子elseretu

44、rn NULL;StatusInsertChild(BiTree &T,BiTree &p,int LR,BiTree &c)/ 二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。/ 根据LR为0或1，插入c为T中p所指向结点的左或右子树。/ p所指结点的原有左或右子树则成为c的右子树。if( !T | !c | !p | (LR != 0 && LR != 1)return ERROR;/ 不符合条件if(LR =0 )/ 插入为左子树c->rchild = p->lchild;p->lchild =

45、 c;if(LR = 1)/ 插入为右子树c->rchild = p->rchild;p->rchild = c;return OK;StatusDeleteChild(BiTree &T,BiTree &p,intLR)/ p指向T中某个结点，LR为0或1./ 用队列，根据LR为0或1，删除T中P所指结点的左或右子树if(!T | !p | (LR != 1 && LR != 0) return ERROR;BiTreequeue200;/ 定义数组队列intrear = 0, front = 0 ;/ 初始化队列的头指针和尾指针if(LR

46、= 0 && p->lchild)/ LR为0且所删除左孩子存在queuerear+ = p->lchild;/ 则左孩子入队p->lchild = NULL;if(LR = 1 && p->rchild)/ LR为1且所删除右孩子存在queuerear+ = p->rchild;/ 则右孩子入队p->rchild = NULL;while(rear != front)/ 用队列层次遍历，删除所要求的子树p = queuefront+;if(p->lchild) queuerear+ = p->lchild;if(

47、p->rchild) queuerear+ = p->rchild;free(p);return OK;StatusPreOrderTraverse(BiTree T,Status (*Visit)(TElemType e)/ 递归先序遍历T。/ 对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败。if(T)if(Visit(T->data)if(PreOrderTraverse(T->lchild,Visit)if(PreOrderTraverse(T->rchild,Visit) return OK;return ERROR;else

48、return OK; StatusPreOrderTraverse2(BiTree T,Status (*Visit)(TElemType e)/ 非递归先序遍历二叉树。对每个节点调用Visit函数BiTree stack100,p = T;/ 定义数组栈inttop = 0 ;/ 初始化栈顶指针while(p | top > 0 )/ 当结点不空或栈不空if(p)if(!Visit(p->data)/ 访问根节点return ERROR;stacktop+ = p;/ 根指针入栈，遍历左子树p = p->lchild;else/ 根指针退栈，遍历右子树p = stack-t

49、op;p = p->rchild;return OK;StatusInOrderTraverse(BiTree T,Status (*Visit)(TElemType e)/ 递归中序遍历T。/ 对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败if(T)if(PreOrderTraverse(T->lchild,Visit)if(Visit(T->data)if(PreOrderTraverse(T->rchild,Visit) return OK;return ERROR;elsereturn OK;StatusInOrderTravers

50、e2(BiTree T,Status (*Visit)(TElemType e)/ 非递归中序遍历二叉树，对每个节点调用Visit。BiTree stack100,p = T;/ 定义数组栈inttop = 0 ;/ 初始化栈顶指针while(p | top > 0 )if(p)/ 根指针入栈，遍历左子树stacktop+ = p;p = p->lchild;else/ 根指针退栈，遍历右子树p = stack-top;if(!Visit(p->data) return ERROR;p = p->rchild;return OK;StatusPostOrderTraverse(BiTree T,Status (*Visit)(TElemType e)/ 后序遍历T。/ 对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败if(T)if(PreOrderTraverse(T->lchild,Vi