广东工业大学数据结构二叉树课程设计.doc
《广东工业大学数据结构二叉树课程设计.doc》由会员分享,可在线阅读,更多相关《广东工业大学数据结构二叉树课程设计.doc(21页珍藏版)》请在咨信网上搜索。
1、数据结构实验报告 题目:二叉树抽象数据类型 学 院 计算机学院 专 业 计算机科学与技术 年级班别 学 号 学生姓名 指导教师 成 绩 _2013年6月一实验概要实验项目名称: 二叉树抽象数据类型的实现实验项目性质: 设计性实验所属课程名称: 数据结构实验计划学时: 6二.实验目的1. 了解二叉树的定义以及各项基本操作。2. 实现二叉树存储、遍历及其他基本功能三. 实验仪器设备和材料 硬件:PC机 软件:Visual C+ 6.0四实验的内容1.二叉树类型定义以及各基本操作的简要描述;ADT BinaryTree 数据对象D:D是具有相同特性的数据元素的集合.数据关系R:若D=,则R=,称Bi
2、naryTree为空二叉树;若D,则R=H,H是如下二元关系:(1) 在D中存在惟一的称为根的数据元素root,它在关系H下无前驱;(2) 若D-root,则存在D-root=D1,Dr,且D1Dr=;(3) 若D1,则D1中存在惟一的元素x1,H,且存在Dr上的关系HrH;H=,H1,Hr;(4) (D1,H1)是一棵符合本定义的二叉树,称为根的左子树,是一棵符合本定义的二叉树,称为根的右子树。基本操作P:InitBiTree(&T);操作结果:构造空二叉树T。DestroyBiTree(&T);初始条件:二叉树T存在。操作结果:销毁二叉树T。CreateBiTree(&T,definiti
3、on);初始条件:definition给出二叉树T的定义。操作结果:按definition构造二叉树T。ClearBiTree(&T);初始条件:二叉树T存在。操作结果:将二叉树T清为空树。BiTreeEmpty(T);初始条件:二叉树T存在。操作结果:若T为空二叉树,则返回TURE,否则FALSE。BiTreeDepth(T);初始条件:二叉树T存在。操作结果:返回T的深度。Root(T);初始条件:二叉树T存在。操作结果:返回T的根。Value(T,e);初始条件:二叉树T存在,e是T中的某个结点。操作结果:返回e的值。Assign(T,&e,value); 初始条件:二叉树T存在,e是T
4、中的某个结点。 操作结果:结点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无左孩子或无左兄弟,则返回“空”。RightSibl
5、ing(T,e); 初始条件:二叉树T存在,e是T中的某个结点。操作结果:返回e的右兄弟。若e无右孩子或无右兄弟,则返回“空”。ADT BinaryTree2.存储结构:采用无头结点的链式存储结构实现3.源代码:头文件及存储结构:#include#include#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW 0#define MAXQSIZE 100 /最大队列长度typedef char TElemType; typedef struct BiTNode /二叉树结构体TElemType dat
6、a;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef BiTree QElemType;typedef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr; /结点结构体typedef struct QueuePtr front; QueuePtr rear; LinkQueue; /链队列结构体 算法设计:int InitQueue(LinkQueue &Q) /构造空队列 Q.front = Q.rear = (QueuePtr)malloc(size
7、of(QNode);if(!Q.front) /存储分配失败 exit(OVERFLOW); Q.front-next = NULL;return OK; int EnQueue(LinkQueue &Q, QElemType e) /新元素入队尾 QueuePtr p; p = (QueuePtr)malloc(sizeof(QNode); if(!p) /存储分配失败 exit (OVERFLOW); p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; int DeQueue(LinkQueue &Q, QE
8、lemType &e) /删除队头元素 QueuePtr p; if(Q.front = Q.rear) /队列为空队 return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if(Q.rear = p) /判断删除队头元素后,队列是否为空队 Q.rear = Q.front; free(p); return OK; int QueueEmpty(LinkQueue Q) /判断队列是否为空队 if (Q.front = Q.rear)return TURE;elsereturn FALSE;int InitBiTr
9、ee(BiTree &T) / 构造空二叉树 T = NULL;return OK;int DestroyTree(BiTree &T) /销毁二叉树if(!T)return ERROR;elseDestroyTree(T-lchild);DestroyTree(T-rchild);free(T);T=NULL;return OK;void CreateBiTree(BiTree &T) /用先序遍历的方式构建二叉树,以表示空结点。 TElemType ch;scanf(%c,&ch);if(ch=)T=NULL;elseif(!(T=(BiTree)malloc(sizeof(BiTNode
10、)exit(OVERFLOW); /分配存储空间失败T-data=ch;CreateBiTree(T-lchild); /构造左子树CreateBiTree(T-rchild); /构造右子树int ClearBiTree(BiTree &T) /清空二叉树函数if(!T)return ERROR;elseClearBiTree(T-lchild);ClearBiTree(T-rchild);free(T);T=NULL;return OK;int BiTreeEmpty(BiTree T) /判断二叉树是否为空if(!T)return TURE;elsereturn FALSE;int Bi
11、TreeDepth(BiTree T) /计算二叉树深度int lcd,rcd;if(!T)return 0;lcd=BiTreeDepth(T-lchild);rcd=BiTreeDepth(T-rchild);return (lcdrcd?lcd:rcd)+1);TElemType Root(BiTree T) /判断二叉树是否空,若非空返回其根if(BiTreeEmpty(T)return NULL;elsereturn (T-data);TElemType Value(BiTree T,BiTree e) /返回e结点的值return e-data;int Assign(BiTree
12、T,BiTree &e,TElemType value) / 将value的值给结点ee-data=value;return OK;TElemType Parent(BiTree T,TElemType e)/返回双亲LinkQueue q;QElemType a;if(T)InitQueue(q);EnQueue(q,T);/树根入队列while(!QueueEmpty(q)/队不空DeQueue (q, a);/出队,队列元素赋给aif(a-lchild&a-lchild-data=e|a-rchild&a-rchild-data=e) /找到ereturn a-data; /返回双亲的值
13、elseif(a-lchild)EnQueue(q,a-lchild);/入队列左孩子if(a-rchild)EnQueue(q,a-rchild);/入队列右孩子return NULL;BiTree Point(BiTree T,TElemType s)/返回二叉树T中指向元素值为S的结点指针LinkQueue q;QElemType a;if(T)InitQueue(q);EnQueue(q,T);while(!QueueEmpty(q)DeQueue(q,a);if(a-data=s)return a;if(a-lchild)EnQueue(q,a-lchild);if(a-rchild
14、)EnQueue(q,a-rchild);return NULL;TElemType LeftChild(BiTree T,TElemType e)/返回e的左孩子 BiTree a; if(T) a=Point(T,e);/a是指向结点e的指针 if(a&a-lchild)return a-lchild-data;return NULL;TElemType RightChild(BiTree T,TElemType e) /返回e的右孩子BiTree a;if(T)if(a=Point(T,e)&a-rchild)return a-rchild-data; return NULL;TElem
15、Type LeftSibling(BiTree T,TElemType e) /返回左兄弟TElemType a;BiTree p;if(T)a=Parent(T,e);/a为e的双亲if(a!=NULL)p=Point(T,a);/p指向结点a的指针if(p-lchild&p-rchild&p-rchild-data=e)/p存在左右孩子而且右孩子是ereturn p-lchild-data;return NULL;TElemType RightSibling(BiTree T,TElemType e) /返回右兄弟TElemType a;BiTree p;if(T)a=Parent(T,e
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 广东工业大学 数据结构 二叉 课程设计
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。