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

《抽象类型实现二叉树实验报告(共56页).doc》由会员分享，可在线阅读，更多相关《抽象类型实现二叉树实验报告(共56页).doc（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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中存在

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

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

4、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的右孩子或无右兄弟，则返回“空”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三、 存储结构定义及各基本操作的实现

7、1. 公用头文件base.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 csbin

8、fo;GetConsoleScreenBufferInfo(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)/移动光

9、标到（x，y）坐标COORD 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,uns

10、igned y)/在(x,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();SetCol

11、or();voidClearWindow(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,

12、y);putchar( );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

13、 T,inti)/ 返回第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

14、;elsereturn 0;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(PreOrderTra

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

16、节点stacktop+ = 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

17、) return OK;returnERROR;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;Stat

18、usPostOrderTraverse(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,Sta

19、tus (*Visit)(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;intSearchB

21、iTree(SqBiTree 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

22、+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(_);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(

23、T6 != &i=T0)gotoxy(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(

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

25、if(ch = ) T = 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

26、 = & | i = strlen(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-lch

27、ild);/ 销毁左子树DestroyBiTree(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

28、(dl dr ? dl:dr) + 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)/ 二

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

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