(完整word版)二叉树抽象大数据类型大数据结构实验报告材料

1、实用标准文档数据结构实验报告题目： 二叉树抽象数据类型的实现学院* 学院专业*年级班别*学号*学生姓名*指导教师成绩 _2012年6月文案大全实用标准文档报告：内容：详细完整不完整设计方案：非常合理合理较差实现：全部实现部分实现未实现文档格式：规范基本规范不规范答辩：理解题目透彻，问题回答流利理解题目较透彻，回答问题基本正确部分理解题目，部分问题回答正确未能完全理解题目，答辩情况较差总评成绩：优良中及格不及格文案大全实用标准文档一实验概要二叉树抽象数据类型的实现二 . 实验目的1. 了解二叉树的定义以及各项基本操作。2. 实现二叉树存储、遍历及其他基本功能三.实验仪器设备和材料Visual s

2、tudio 2010四实验的内容1. 二叉树类型定义以及各基本操作的简要描述；ADT BinaryTree 数据对象 D:D 是具有相同特性的数据元素的集合.数据关系 R:若 D=?，则 R=,称 BinaryTree 为空二叉树；若 D，则 R=H， H 是如下二元关系：(1) 在 D中存在惟一的称为根的数据元素 root ，它在关系 H 下无前驱；(2) 若 D-root ?，则存在 D-root=D1,Dr ，且 D1 Dr=?；(3) 若 D1?，则 D1 中存在惟一的元素 x1，H，且存在 Dr上的关系 HrH；H=， ，H1,Hr ；(4) （D1， H1 ）是一棵符合本定义的二叉

3、树，称为根的左子树，是一棵符合本定义的二叉树，称为根的右子树。基本操作 P:InitBiTree(&T);操作结果：构造空二叉树T。DestroyBiTree(&T);初始条件：二叉树T 存在。操作结果：销毁二叉树T。CreateBiTree(&T,definition);初始条件： definition给出二叉树 T 的定义。操作结果：按 definition构造二叉树 T。ClearBiTree(&T);初始条件：二叉树T 存在。操作结果：将二叉树T 清为空树。BiTreeEmpty(T);初始条件：二叉树T 存在。操作结果：若 T 为空二叉树，则返回TURE,否则 FALSE。BiTre

4、eDepth(T);初始条件：二叉树T 存在。文案大全实用标准文档操作结果：返回T 的深度。Root(T);初始条件：二叉树T 存在。操作结果：返回T 的根。Value(T,e);初始条件：二叉树T 存在， e 是 T 中的某个结点。操作结果：返回 e 的值。Assign(T,&e,value);初始条件：二叉树T 存在， e 是 T 中的某个结点。操作结果：结点e 赋值为 value 。Parent(T,e);初始条件：二叉树T 存在， e 是 T 中的某个结点。操作结果：若 e 是 T 的非跟结点，则返回它的双亲，否则返回“空”。LeftChild(T,e);初始条件：二叉树T 存在， e

5、 是 T 中的某个结点。操作结果：返回e 的左孩子。若 e 无左孩子，则返回“空” 。RightChild(T,e);初始条件：二叉树T 存在， e 是 T 中的某个结点。操作结果：返回e 的右孩子。若 e 无右孩子，则返回“空” 。LeftSibling(T,e);初始条件：二叉树T 存在， e 是 T 中的某个结点。操作结果：返回 e 的左兄弟。若 e 无左孩子或无左兄弟，则返回“空” 。RightSibling(T,e);初始条件：二叉树T 存在， e 是 T 中的某个结点。操作结果：返回 e 的右兄弟。若 e 无右孩子或无右兄弟，则返回“空” 。ADT BinaryTree2. 所选择

6、的存储结构描述及在此存储结构上各基本操作的实现；3. 源代码主文件 :main.ccp:#includebase.h/公用头文件、公共常量及公共函数等#includebitree.h/二叉树二叉链表基本操作voidMenu();/菜单函数voidProduce(char *str);/随机产生二叉树先序序列函数intmain()/主函数BiTree T,bt,insert_bt;charcmd,strMAXSIZE,elem;intloc,temp;文案大全实用标准文档InitBiTree(T);/初始化二叉链表二叉树Menu();/显示菜单while(1)ClearLine();/清空结果显

7、示区printf(请选择操作： ( 按 Q 退出 );cmd = getch();ClearLine();fflush(stdin);switch(cmd)case 0:/随机创建一棵二叉树while(cmd != y & cmd != Y)Produce(str);/随机产生二叉树先序序列CreateBiTree(T,str);/用此序列建树ShowBiTree(T);/广义表形式显示printf(使用创建的这个二叉树?);cmd = getch();ClearLine();break;case 2:/手动创建一棵二叉树printf( 请按二叉树先序序列输入二叉树： ( 空结点用空格 表示

8、)n ); CreateBiTree(T);ClearLine();printf(二叉树创建成功!n);ShowBiTree(T);getch();break;case 4:/销毁二叉树DestroyBiTree(T);printf(二叉树已被销毁!);getch();break;case 6:/判空if(BiTreeEmpty(T) printf(二叉树是空二叉树。);elseprintf(二叉树非空 );getch();break;case 8:/求深度printf(深度是 %d,BiTreeDepth(T);getch();break;文案大全实用标准文档case a:/求左孩子Show

9、BiTree(T);printf(你想求哪个字符的左孩子？);doelem = getchar();ClearLine();bt = SearchBiTree(T,elem);/查找指定的结点值elemif(!bt) printf(你输入的结点不存在! 请重新输入：);while(!bt);ClearLine();bt = LeftChild(T,bt);/求左孩子if(bt) printf( %c的左孩子是 %c,elem,bt-data);elseprintf( %c没有左孩子 ,elem);printf(n参照二叉树 :);ShowBiTree(T);getch();break;case

10、 c:/求右孩子ShowBiTree(T);printf(你想求哪个字符的右孩子？);doelem = getchar();ClearLine();bt = SearchBiTree(T,elem);if(!bt) printf(你输入的结点不存在! 请重新输入：);while(!bt);ClearLine();bt = RightChild(T,bt);if(bt) printf( %c的右孩子是 %c,elem,bt-data);elseprintf( %c没有右孩子 ,elem);printf(n参照二叉树 :);ShowBiTree(T);getch();break;case 1:/先

11、序遍历if(!BiTreeEmpty(T)printf(先序遍历序列为：);PreOrderTraverse(T,Visit);else printf(二叉树空，请先建树!);getch();break;case 3:/中序遍历文案大全实用标准文档if(!BiTreeEmpty(T)printf(中序遍历序列为：);InOrderTraverse(T,Visit);else printf(二叉树空，请先建树!);getch();break;case 5:/后序遍历if(!BiTreeEmpty(T)printf(后序遍历序列为：);PostOrderTraverse(T,Visit);else

12、 printf(二叉树空，请先建树!);getch();break;case 7:/层次遍历if(!BiTreeEmpty(T)printf(层次遍历序列为：);LevelOrderTraverse(T,Visit);else printf(二叉树空，请先建树!);getch();break;case 9:/插入一棵二叉树为另一棵二叉树的子树do/随机创建一棵右孩子为空Produce(str);/且层数小于4 的树CreateBiTree(insert_bt,str);while(insert_bt-rchild|BiTreeDepth(insert_bt) 3);printf(先随机创建一棵

13、右子树空的二叉树如图n);ShowBiTree(insert_bt);/新创建的树getch();printf(你想插入这棵树为原树哪个结点的子树:n);ShowBiTree(T);bt = SearchBiTree(T,getchar();ClearLine();printf(你想插入为0.左孩子1.右孩子 :);fflush(stdin);scanf(%d,&loc);if(!InsertChild(T, bt, loc, insert_bt)printf(插入出错 !);else文案大全实用标准文档ClearLine();printf(插入成功 ! 插入后 T 广义表形式为:n);Sho

14、wBiTree(T);getch();break;case b:/删除指定结点的子树ShowBiTree(T);printf(你想删除哪个结点的子树?);fflush(stdin);bt = SearchBiTree(T,getchar();printf(n你想删除0. 左子树 1. 右子树 : );fflush(stdin);scanf(%d,&loc);ClearLine();if(!DeleteChild(T,bt,loc) printf(删除出错 !);else printf(删除成功，检查结果n);ShowBiTree(T);getch();break;case e:/返回先序序列第

15、i 个结点的值printf(请输入一个结点的先序序列序号: );scanf(%d,&loc);temp = loc;ClearLine();elem = Value(T,temp);printf(参照二叉树 :);ShowBiTree(T);printf(n);if(elem = )printf(该结点不存在。);else printf(先序序列第 %d个结点值为 %c,loc,elem);getch();break;case d:/结点赋值ShowBiTree(T);printf(请输入要赋值的结点: );doelem = getchar();ClearLine();bt = SearchB

16、iTree(T,elem);if(!bt) printf(你输入的结点不存在! 请重新输入：);while(!bt);ClearLine();printf(请输入新值 : );fflush(stdin);文案大全实用标准文档elem = getchar();Assign(T,bt,elem);printf(赋值成功，请查看二叉树状态.n);ShowBiTree(T);getch();break;case Q:/退出case q: exit(0);return 0;voidMenu()/显示菜单函数printf( 0.随机创建 CreateBiTree()1.先序遍历 PreOrderTrave

17、rse();printf(nn2.手 动创 建CreateBiTree()3.中序 遍历InOrderTraverse();printf(nn4.销 毁DestoryBiTree()5.后 序 遍 历PostOrderTraverse();printf(nn6.判 空BiTreeEmpty()7.层 次 遍 历LevelOrderTraverse();printf(nn 8.求深度BiTreeDepth()9.插入子树InsertChild();printf(nn a.求左孩子 LeftChild()b.删除子树DeleteChild();printf(nn c.求右孩子 RightChild

18、()d.结点赋值Assign();printf(nn e.求结点值 Value();printf(nn);voidProduce(char *str)/ 用随机数产生二叉树层次字符序列/使所有节点的字符不相同，空节点用&表示intexist27 , i , elem, maxnodes = rand()%41;while( maxnodes 31) maxnodes = rand()%41; /* 随机产生一个 大于 15 小于 31 的随机数作为结点个数 */for(i = 0; i 27 ;i+) existi = 0;/初始化存在数组，用于使所有结点值不同i = 1;while(i ma

19、xnodes)elem = rand() % 26 ;if(!existelem & stri/2 != &) /结点未生成且存在父节点文案大全实用标准文档stri+ = elem + A;existelem = 1;else stri+ = &;stri = 0;头文件 :base.h:#includestdio.h#includeconio.h#includestdlib.h#includewindows.h#includemalloc.h#includemath.h#defineOK1#defineTRUE1#defineERROR0#defineFALSE0#defineMAXSIZE

20、100typedefintStatus;typedefcharTElemType;shortwherex()/返回光标的 x 坐标shortwherey()/ 返回光标的y 坐标void gotoxy(short x,short y)/ 移动光标到（x， y）坐标COORD point = x, y;SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), point);文案大全实用标准文档void ClearLine(unsigned y = 17)/ 清除第 y 行与 y+1 行的字符，并使光标在行首，默认清除第17至19行for(

21、int i = 0;i 256;i+)gotoxy(i,y);putchar( );gotoxy(0,wherey()-3);void ClearAera(unsigned x = 96, unsigned y = 17)/ 清除 (0,y)-(x,y+1)区域的字符，并使光标移动到yfor(unsigned i = 0; ilchild);/删除左子树DestroyBiTree(T-rchild);/删除右子树free(T);T = NULL;return OK;StatusCreateBiTree(BiTree &T)/先序建立二叉树T, 空格表示空结点TElemType ch;fflus

22、h(stdin);ch=getche();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 为当前要创建结点对应的数组序号节点/由字符数组st

23、r先序建立一棵二叉树Tif(stri = & | 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;文案大全实用标准文档StatusBiTreeEmpty(BiTree T)/若 T 为空二叉树，则返回TRUE，否则返回FALSEif

24、(!T)return TRUE;elsereturn FALSE;intBiTreeDepth(BiTree T)/ 返回 T 的深度/ 利用层次遍历求深度if(!T) return 0;BiTreequeue200;int dep =0;intrear = 0 ,front = 0;queuerear+ = T;while(rear != front)T = queuefront+;if(T-data)dep+;if(T-lchild) queuerear+ = T-lchild;if(T-rchild) queuerear+ = T-rchild;else dep-;return dep;

25、TElemTypeValue(BiTree T,int&k)/ 返回二叉树先序遍历第 k 个节点的值，不存在则返回空格 if(!T | k data;BiTree stack100,p = T;/定义数组栈inttop = 0 ,i=-1;/初始化栈顶指针while(p | top 0 )/当结点不空或栈不空if(p)文案大全实用标准文档i+;if(i=k)return p-data;stacktop+ = p;/根指针入栈，遍历左子树p = p-lchild;else/根指针退栈，遍历右子树p = stack-top;p = p-rchild;voidAssign(BiTree T,BiTr

26、ee &p,TElemType value)/ 二叉树 T 存在， e 是 T 中某个结点/ 结点 p 赋值为 valueif(p) p-data = value;BiTreeLeftChild(BiTree T,BiTree p)/ 返回 p 的左孩子。若 p 无左孩子，则返回“空”return p-lchild;BiTreeRightChild(BiTree T,BiTree p)/ 返回 p 的右孩子。若 p 无右孩子，则返回“空”return p-rchild;StatusInsertChild(BiTree &T,BiTree &p,int LR,BiTree &c)/二叉树 T 存

27、在， 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 = c;文案大全实用标准文档if(LR = 1)/插入为右子树c-rchild = p-rchild;p-rchild = c;return OK;StatusDelet

28、eChild(BiTree &T,BiTree &p,int LR)/ 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 = 0 & p-lchild)/ LR为 0 且所删除左孩子存在queuerear+ = p-lchild;/则左孩子入队p-lchild = NULL;if(LR = 1 & p-rc

29、hild)/ LR为 1 且所删除右孩子存在queuerear+ = p-rchild;/则右孩子入队p-rchild = NULL;while(rear != front)/用队列层次遍历，删除所要求的子树p = queuefront+;if(p-lchild) queuerear+ = p-lchild;if(p-rchild) queuerear+ = p-rchild;free(p);return OK;StatusPreOrderTraverse(BiTree T,Status (*Visit)(TElemType e)/非递归先序遍历二叉树。对每个节点调用Visit函数BiTree

30、 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-top;p = p-rchild;return OK;StatusInOrderTraverse(BiTree T,Status (*Visit)(TElemType e)/非递归中序遍历二叉树，对每个节点调用Visit。BiTr

31、ee 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。/与非递归先序中序的区别在于，多定义一visited数组，用来记录访问次

32、数/ 第二次访问时才退栈。文案大全实用标准文档BiTreestack100 , p = T;/定义数组栈inttop = 0, visited100;/初始化栈顶指针与访问次数数组while(p | top 0)if(p)/遍历左子树，置访问数组为第一次访问stacktop+ = p;visitedtop-1 = 0;p = p-lchild;elseif(visitedtop-1 = 0)/若栈顶结点只访问一次，遍历右子树p = stacktop-1;visitedtop-1 +;p = p-rchild;else if(visitedtop-1 = 1)/若第二次访问，则根指针退栈，访问根节点。if(!Visit(stack-top-data) return ERROR;return OK;StatusLevelOrderTraverse(BiTree T,Status (*Visit)(TElemType e)/用队列层次遍历二叉树T。/对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败if(!T)return OK;BiTreequeue200;/定义数组队列intrear = 0 ,front = 0;/初始化队头、队尾指针queuerear+ = T;/根