实用标准文档文案大全数据结构实验报告题目：二叉树抽象数据类型的实现学院* 学院专业* 年级班别* 学号*学生姓名 * 指导教师成绩 _2012 年 6 月精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 24 页实用标准文档文案大全报告：内容：详细完整不完整设计方案：非常合理合理较差实现：全部实现部分实现未实现文档格式：规范基本规范不规范答辩：理解题目透彻，问题回答流利理解题目较透彻，回答问题基本正确部分理解题目，部分问题回答正确未能完全理解题目，答辩情况较差总评成绩：优良中及格不及格精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 24 页实用标准文档文案大全一实验概要二叉树抽象数据类型的实现二. 实验目的1. 了解二叉树的定义以及各项基本操作。2. 实现二叉树存储、遍历及其他基本功能三. 实验仪器设备和材料 Visual studio 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 ）是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的右子树。基本操作 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 。BiTreeDepth(T); 初始条件：二叉树T存在。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 24 页实用标准文档文案大全操作结果：返回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 是 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. 所选择的存储结构描述及在此存储结构上各基本操作的实现；3. 源代码主文件 :main.ccp: #includebase.h / 公用头文件、公共常量及公共函数等#includebitree.h / 二叉树二叉链表基本操作void Menu(); / 菜单函数void Produce(char *str); / 随机产生二叉树先序序列函数int main() / 主函数 BiTree T,bt,insert_bt; char cmd,strMAXSIZE,elem; int loc,temp; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 24 页实用标准文档文案大全InitBiTree(T); / 初始化二叉链表二叉树Menu(); / 显示菜单while(1) ClearLine(); / 清空结果显示区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( 请按二叉树先序序列输入二叉树：( 空结点用空格 表示 )n ); CreateBiTree(T); ClearLine(); printf( 二叉树创建成功!n); ShowBiTree(T); getch(); break; case 4:/ 销毁二叉树DestroyBiTree(T); printf( 二叉树已被销毁!); getch(); break; case 6:/ 判空if(BiTreeEmpty(T) printf(二叉树是空二叉树。); else printf(二叉树非空 ); getch(); break; case 8:/ 求深度printf(深度是 %d,BiTreeDepth(T); getch(); break; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 24 页实用标准文档文案大全case a:/ 求左孩子ShowBiTree(T); printf(你想求哪个字符的左孩子？); do elem = getchar(); ClearLine(); bt = SearchBiTree(T,elem); / 查找指定的结点值elem if(!bt) printf( 你输入的结点不存在! 请重新输入：); while(!bt); ClearLine(); bt = LeftChild(T,bt); / 求左孩子if(bt) printf( %c的左孩子是 %c,elem,bt-data); else printf( %c没有左孩子 ,elem); printf(n参照二叉树 :); ShowBiTree(T); getch(); break; case c:/ 求右孩子ShowBiTree(T); printf( 你想求哪个字符的右孩子？); do elem = getchar(); ClearLine(); bt = SearchBiTree(T,elem); if(!bt) printf( 你输入的结点不存在! 请重新输入：); while(!bt); ClearLine(); bt = RightChild(T,bt); if(bt) printf( %c的右孩子是 %c,elem,bt-data); else printf( %c没有右孩子 ,elem); printf(n参照二叉树 :); ShowBiTree(T); getch(); break; case 1:/ 先序遍历if(!BiTreeEmpty(T) printf(先序遍历序列为：); PreOrderTraverse(T,Visit); else printf(二叉树空，请先建树!); getch(); break; case 3:/ 中序遍历精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 24 页实用标准文档文案大全if(!BiTreeEmpty(T) printf(中序遍历序列为：); InOrderTraverse(T,Visit); else printf(二叉树空，请先建树!); getch(); break; case 5:/ 后序遍历if(!BiTreeEmpty(T) printf(后序遍历序列为：); PostOrderTraverse(T,Visit); else 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( 先随机创建一棵右子树空的二叉树如图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 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 24 页实用标准文档文案大全ClearLine(); printf( 插入成功 ! 插入后 T 广义表形式为:n); ShowBiTree(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:/ 返回先序序列第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( 请输入要赋值的结点: ); do elem = getchar(); ClearLine(); bt = SearchBiTree(T,elem); if(!bt) printf( 你输入的结点不存在! 请重新输入：); while(!bt); ClearLine(); printf( 请输入新值 : ); fflush(stdin); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 24 页实用标准文档文案大全elem = getchar(); Assign(T,bt,elem); printf( 赋值成功，请查看二叉树状态.n); ShowBiTree(T); getch(); break; case Q:/ 退出case q: exit(0); return 0; void Menu() / 显示菜单函数 printf( 0. 随机创建 CreateBiTree() 1. 先序遍历 PreOrderTraverse(); printf(nn 2. 手 动创 建CreateBiTree() 3. 中序 遍历InOrderTraverse(); printf(nn 4. 销 毁DestoryBiTree() 5. 后 序 遍 历PostOrderTraverse(); printf(nn 6. 判 空BiTreeEmpty() 7. 层 次 遍 历LevelOrderTraverse(); printf(nn 8. 求深度 BiTreeDepth() 9. 插入子树 InsertChild(); printf(nn a. 求左孩子 LeftChild() b. 删除子树 DeleteChild(); printf(nn c. 求右孩子 RightChild() d. 结点赋值 Assign(); printf(nn e. 求结点值 Value(); printf(nn); void Produce(char *str) / 用随机数产生二叉树层次字符序列/ 使所有节点的字符不相同，空节点用&表示 int exist27 , 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 maxnodes) elem = rand() % 26 ; if(!existelem & stri/2 != &) / 结点未生成且存在父节点精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 24 页实用标准文档文案大全 stri+ = elem + A; existelem = 1; else stri+ = &; stri = 0; 头文件 :base.h: #includestdio.h #includeconio.h #includestdlib.h #includewindows.h #includemalloc.h #includemath.h #define OK 1 #define TRUE 1 #define ERROR 0 #define FALSE 0 #define MAXSIZE 100 typedef int Status; typedef char TElemType; short wherex() / 返回光标的x 坐标 CONSOLE_SCREEN_BUFFER_INFO csbinfo; GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE),&csbinfo); return csbinfo.dwCursorPosition.X; short wherey() / 返回光标的y 坐标 CONSOLE_SCREEN_BUFFER_INFO csbinfo; GetConsoleScreenBufferInfo(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); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 24 页实用标准文档文案大全void ClearLine(unsigned y = 17) / 清除第 y 行与 y+1 行的字符，并使光标在行首，默认清除第17 至 19 行 for(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)区域的字符，并使光标移动到y for(unsigned i = 0; ilchild); / 删除左子树DestroyBiTree(T-rchild); / 删除右子树free(T); T = NULL; return OK; Status CreateBiTree(BiTree &T) / 先序建立二叉树T, 空格表示空结点 TElemType ch; fflush(stdin); ch=getche(); if(ch = ) T = NULL; else T = (BiTree)malloc(sizeof(BiTNode); if(!T) exit(OVERFLOW); T-data = ch; / 生成头结点CreateBiTree(T-lchild); / 构造左子树CreateBiTree(T-rchild); / 构造右子树 return OK; Status CreateBiTree(BiTree &T,char *str,unsigned i = 1) / str储存着二叉树的层次序列，stri=&表示结点不存在/ i为当前要创建结点对应的数组序号节点/ 由字符数组str先序建立一棵二叉树T if(stri = & | i = strlen(str) T = NULL; / 第 i 个结点不存在else T = (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; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 24 页实用标准文档文案大全Status BiTreeEmpty(BiTree T) / 若 T 为空二叉树，则返回TRUE ，否则返回FALSE if(!T) return TRUE; else return FALSE; int BiTreeDepth(BiTree T) / 返回 T的深度/ 利用层次遍历求深度 if(!T) return 0; BiTree queue200; int dep =0; int rear = 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; TElemType Value(BiTree T,int &k) / 返回二叉树先序遍历第k 个节点的值，不存在则返回空格 if(!T | k data; BiTree stack100,p = T; / 定义数组栈int top = 0 ,i=-1; / 初始化栈顶指针while(p | top 0 ) / 当结点不空或栈不空 if(p) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 24 页实用标准文档文案大全 i+; if(i=k) return p-data; stacktop+ = p; / 根指针入栈，遍历左子树p = p-lchild; else / 根指针退栈，遍历右子树p = stack-top; p = p-rchild; void Assign(BiTree T,BiTree &p,TElemType value) / 二叉树 T 存在， e 是 T 中某个结点/ 结点 p赋值为 value if(p) p-data = value; BiTree LeftChild(BiTree T,BiTree p) / 返回 p的左孩子。若p 无左孩子，则返回“空” return p-lchild; BiTree RightChild(BiTree T,BiTree p) / 返回 p的右孩子。若p 无右孩子，则返回“空” return p-rchild; Status InsertChild(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 = c; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 24 页实用标准文档文案大全 if(LR = 1) / 插入为右子树 c-rchild = p-rchild; p-rchild = c; return OK; Status DeleteChild(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; BiTree queue200; / 定义数组队列int rear = 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+; if(p-lchild) queuerear+ = p-lchild; if(p-rchild) queuerear+ = p-rchild; free(p); return OK; Status PreOrderTraverse(BiTree T,Status (*Visit)(TElemType e) / 非递归先序遍历二叉树。对每个节点调用Visit函数 BiTree stack100,p = T; / 定义数组栈int top = 0 ; / 初始化栈顶指针精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 24 页实用标准文档文案大全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; Status InOrderTraverse(BiTree T,Status (*Visit)(TElemType e) / 非递归中序遍历二叉树，对每个节点调用Visit。 BiTree stack100,p = T; / 定义数组栈int top = 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; Status PostOrderTraverse(BiTree T,Status (*Visit)(TElemType e) / 用栈非递归后序遍历二叉树T。/ 与非递归先序中序的区别在于，多定义一visited数组，用来记录访问次数/ 第二次访问时才退栈。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 24 页实用标准文档文案大全BiTree stack100 , p = T; / 定义数组栈int top = 0, visited100; / 初始化栈顶指针与访问次数数组while(p | top 0) if(p) / 遍历左子树，置访问数组为第一次访问 stacktop+ = p; visitedtop-1 = 0; p = p-lchild; else if(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; Status LevelOrderTraverse(BiTree T,Status (*Visit)(TElemType e) / 用队列层次遍历二叉树T。/ 对每个结点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败 if(!T) return OK; BiTree queue200; / 定义数组队列int rear = 0 ,front = 0; / 初始化队头、队尾指针queuerear+ = T; / 根指针入队while(rear != front) / 队不空 T = queuefront+; / 根指针出队if(Visit(T-data) / 访问根节点 if(T-lchild) queuerear+ = T-lchild;/ 若左子树不空，则左孩子入队if(T-rchild) queuerear+ = T-rchild;/ 若右孩子不空，则右孩子入队 else return ERROR; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 24 页实用标准文档文案大全 return OK; BiTree SearchBiTree(BiTree T,TElemType value) / 在二叉树T 中查找值为value 的结点，返回指向该结点的指针/ （假设树上所有结点值不同）如未找到，则返回空 if(T) if(T-data = value) return T; BiTree p = SearchBiTree(T-lchild,value); / 递归遍历左子树if(p) return p; / 若在左子树找到else return SearchBiTree(T-rchild,value); / 遍历右子树 return NULL; void ShowBiTree(BiTree T) / 递归显示二叉树的广义表形式 if(!T) return ; putchar(T-data); / 打印根节点if(T-lchild |T-rchild) putchar(); ShowBiTree(T-lchild); / 递归显示左子树putchar(,); ShowBiTree(T-rchild); / 递归显示右子树putchar(); 4. 程序清单（计算机打印） ，输入的数据及各基本操作的测试结果；功能：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 24 页实用标准文档文案大全第一步：随机创建第二部：手动创建精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 24 页实用标准文档文案大全第三步：重新创建和求深度注：以下由 C V , X K , F , S G N , Q , 二叉树做测试第四步：求左孩子第五步：求右孩子精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 24 页实用标准文档文案大全第六步：先序遍历中序遍历后序遍历第七步：层次遍历第八步：插入子树精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 24 页实用标准文档文案大全插入为 V 的左孩子结果：第九步：删除子树精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 24 页实用标准文档文案大全删除结点 Q 的左孩子结果：第十步：结点赋值为结点 S赋值为 M 第十一步：求结点值求第 4 个结点的值：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 24 页实用标准文档文案大全六. 实验总结和体会。抽象数据类型是模块化思想的发展，有助于我们从更抽象的高度去讨论算法和数据结构的问题。通过这次实验，我对二叉树的抽象数据类型更加了解和熟悉，我们只需关心它的逻辑特征而不需要了解它的存储方式。数据结构是每个程序员的必修课， 但是我们还要学的还有很多很多，而且现在计算机技术发展迅速，我们要学的可以说是无穷无尽的。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 24 页，共 24 页