抽象类型实现二叉树实验报告

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，H,且存在D1上的关系H1H； 若Dr，则Dr中存在惟一的元素xr，H,且存在

2、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构造二叉树TClearBiTree(&T);初始条件：二叉树T存在操作结果：将二叉树T清为空树BiTreeEmpty(T);初

3、始条件：二叉树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中某个结点操作结果：若e是T的非根节点，则返回它的双亲，否则返回“空”LeftChild(T,e);初始条件：二叉树T存在，e是T中某个结点操

4、作结果：返回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的右孩子或无右兄弟，则返回“空”InsertChild(T,p,LR,c);初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子 树为空。操作

5、结果：根据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（）失败，则操 作失败。InOrderTraverse(T,Visit();初始条件：二叉树T存在，Visit是对结点操作的应用函数操作结果：中序遍历

6、T，对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操 作失败PostOrderTraverse(T,Visit();初始条件：二叉树T存在，Visit是对结点操作的应用函数操作结果：后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操 作失败LevelOrderTraverse(T,Visit();初始条件：二叉树T存在，Visit是对结点操作的应用函数操作结果：层次遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操 作失败 ADT BinaryTree三、 存储结构定义及各基本操作的实现1. 公用头文件base.

7、h/*Includes*#includestdio.h#includeconio.h#includestdlib.h#includewindows.h#includemalloc.h#includemath.h#define OK 1#define TRUE1#defineERROR0#defineFALSE0#defineMAXSIZE100/最多结点数typedefintStatus;typedefcharTElemType;/结点类型为字符型/*其它操作*shortwherex()/返回光标的x坐标CONSOLE_SCREEN_BUFFER_INFO csbinfo;GetConsole

8、ScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE),&csbinfo); return csbinfo.dwCursorPosition.X;shortwherey()/返回光标的y坐标CONSOLE_SCREEN_BUFFER_INFO csbinfo;GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE),&csbinfo); return csbinfo.dwCursorPosition.Y;void gotoxy(short x,short y)/移动光标到（x，y）坐标COOR

9、D point = x, y; SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), point);void SetColor(unsigned short TextColor=7)/设置字体颜色 unsigned BackGroundColor = 0;HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hCon,TextColor|BackGroundColor); voidPrint(unsigned x,unsigned y)/在(x,

10、y)位置显示方框SetColor(14);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( ); gotoxy(x,y+);printf( ); gotoxy(x,y+);printf( ); gotoxy(x,y+);printf( ); gotoxy(x,y+);printf();SetColor();voidClea

11、rWindow(unsigned x1 = 50,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( )

12、;gotoxy(0,wherey()-1);voidClearAera(unsigned x = 96, unsigned y = 22)/清除(0,y)-(x,y+1)区域的字符，并使光标移动到yfor(unsigned i = 0; i T0 | !i) return ERROR;Ti = value;return OK;intParent(SqBiTree T,inti)/ 若结点i是T的非根节点，则返回它的双亲的序号，否则返回0if(iT0 | i2 | Ti = &) return 0;elsereturn i/2;intLeftChild(SqBiTree T,inti)/ 返回第

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

14、;intRightSibling(SqBiTree T,inti)/ 返回第i个结点的右兄弟的序号if(i+1 0 & Ti+1 != & & Ti/2 = T(i+1)/2)/ 父亲相同return i+1;elsereturn 0;StatusPreOrderTraverse(SqBiTree T,Status (*Visit)(TElemType e), int i = 1)/ 递归先序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败。if(i = T0 & Ti != &)if(Visit(Ti)if(PreOrderTraverse(T, Visi

15、t, 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)/ 用栈非递归先序遍历二叉树Tintstack100,top = 0;/ 初始化栈顶指针while(i 0)/ 结点存在或栈不空if(i = T0 & Ti != &)/ 根指针入栈，遍历左子树if(!Visit(Ti) return ERROR;/ 访问根节点stacktop+ =

16、 i; i = i*2;else/ 根指针退栈，遍历右子树i = stack-top;i = i*2+1;return OK;StatusInOrderTraverse(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;r

17、eturnERROR;return OK;StatusInOrderTraverse2(SqBiTree T,Status (*Visit)(TElemType e),int i = 1)/ 用栈非递归中序遍历二叉树Tintstack100,top = 0;while(i 0)/ 结点存在或栈不空if(i = T0 & Ti != &)/ 根指针入栈，遍历左子树stacktop+ = i; i = i*2;else/ 根指针退栈，遍历右子树i = stack-top;if(!Visit(Ti) return ERROR;i = i*2+1;return OK;StatusPostOrderTr

18、averse(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;StatusPostOrderTraverse2(SqBiTree T,Status (*Visit)(

19、TElemType e)/ 非递归后序遍历二叉树T/ 与非递归先序中序的区别在于，多定义一tag数组，用来记录访问次数/ 第二次访问时才退栈。intstack100 ,top = 0, tag100, i = 1;while(i 0)if(i = T0 & Ti != &)/ 根指针入栈，遍历左子树tagtop = 0;stacktop+ = i;i = 2 * i;elseif(tagtop-1 = 0)/ 若第一次访问，则遍历右子树tagtop-1 +;i = stacktop-1;i = 2 * i + 1;else if(tagtop-1 = 1)/ 若第二次访问，则访问根节点，根指针

20、退栈if(!Visit(Tstack-top) return ERROR; return OK;StatusLevelOrderTraverse(SqBiTree T,Status (*Visit)(TElemType e)/ 层次遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败/ 由于顺序存储的二叉树刚好是层次遍历所成，只需从数组1到T0访问即可inti, k = 1;for(i = 1; i = T0 & k; i+) if(Ti != &) k = Visit(Ti);/ k记录访问是否出错returnk;intSearchBiTree(SqBiTre

21、e T,TElemType value)/ 返回二叉树T中值为value的结点的下标，如不存在则返回0if(!T | !T0) return 0;/ 若为空树inti;for(i = 1; i 5) return ; char l = 47, r = 92, i = 0;/ l为/,r为字符shortx = 46,y = 0;/ 初始化根节点到屏幕右上角打印/* 由于前3层结点位置无规律，只能逐个打印 */gotoxy(x+18,y+1); putchar(T1); if(T2 != &i=T0)gotoxy(x+15,y+2);putchar(l);gotoxy(x+14,y+2);putc

22、har(_);gotoxy(x+12,y+3);putchar(T2); if(T3 != &i=T0)gotoxy(x+21,y+2);putchar(r);gotoxy(x+22,y+2);putchar(_);gotoxy(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)g

23、otoxy(x+22,y+4);putchar(l);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)gotoxy(x,y-1);else gotoxy(x+1,y-1);putc

24、har(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 & ilchild);/ 删除左子树DestroyBiTree(T-rchild);/ 删除右子树free(T);T = NULL;return OK;StatusCreateBiTree(BiTree &T)/ 先序建立二叉树T,空格表示空结点TElemType ch;fflush(stdin);ch = getch();putchar(ch);if(ch = ) T =

25、 NULL;elseT = (BiTree)malloc(sizeof(BiTNode);if(!T) exit(OVERFLOW);T-data = ch;/ 生成头结点CreateBiTree(T-lchild);/ 构造左子树CreateBiTree(T-rchild);/ 构造右子树return OK;StatusCreateBiTree(BiTree &T,char *str,unsigned i = 1)/ str储存着二叉树的层次序列，stri=&表示结点不存在/ i为当前要创建结点对应的数组序号节点/ 由字符数组str先序建立一棵二叉树Tif(stri = & | i = st

26、rlen(str) T = NULL;/ 第i个结点不存在elseT = (BiTree)malloc(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);/ 销毁左子树D

27、estroyBiTree(T-rchild);/ 销毁右子树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:d

28、r) + 1;/ 深度等于左右子树较大值加1BiTreeRoot(BiTree T)/ 返回二叉树T的根return T;TElemTypeValue(BiTree T,int&k)/ 返回二叉树先序遍历第k个节点的值，不存在则返回空格 if(!T | k data;char elem = Value(T-lchild,k);/ 遍历左孩子if(elem != )return elem ;/ 若第k个结点在左子树else return Value(T-rchild,k);voidAssign(BiTree T,BiTree &p,TElemType value)/ 二叉树T存在，e是T中某个结

29、点/ 结点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,p) ;/ 遍历左子树if(f)returnf;/ 所求父亲在根的左子树elsereturnParent(T-rchild,p);BiTreeLeftChild(BiTree T,BiTree p)/ 返回

30、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 = Parent(T,p);/ 求所求结点p的双亲if(f & f-rchild = p)/ 若双亲存在且p为右孩子return f-lchild;/ 则返回双亲的左孩子elsereturn NULL;BiTreeRightSibl

31、ing(BiTree T,BiTree p)/ 返回p的右兄弟。若p是T的右孩子或无右兄弟，则返回“空”BiTree f = Parent(T,p);/ 求结点p双亲if(f & f-lchild = p)/ 若双亲存在且p为左孩子return f-rchild;/ 则返回双亲的右孩子elsereturn 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所指结点的原有左或

32、右子树则成为c的右子树。if( !T | !c | !p | (LR != 0 & LR != 1)return ERROR;/ 不符合条件if(LR =0 )/ 插入为左子树c-rchild = p-lchild;p-lchild = 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 & L

33、R != 0) return ERROR;BiTreequeue200;/ 定义数组队列intrear = 0, front = 0 ;/ 初始化队列的头指针和尾指针if(LR = 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+

34、;if(p-lchild) queuerear+ = p-lchild;if(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 O

35、K;return ERROR;elsereturn 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 = s

36、tack-top;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;StatusInOrderTraverse2(BiTree

37、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

38、)(TElemType e)/ 后序遍历T。/ 对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败if(T)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverse(T-rchild,Visit) if(Visit(T-data)return OK;return ERROR;elsereturn OK;StatusPostOrderTraverse2(BiTree T,Status (*Visit)(TElemType e)/ 用栈非递归后序遍历二叉树T。/ 与非递归先序中序的区别在于，多定义一visited数组，用来记录访问次数/ 第二次访问时才退栈。BiTreestack100 , p = T;/ 定义数组栈inttop = 0, visited100;/ 初始化栈顶指针与访问次数数组while