数据结构-树的实现实验报告.doc

数据结构设计性实验报告 课程名称_ _ 题目名称 学生学院 专业班级 学 号 学生姓名 指导教师 2010 年 7 月 6 日 抽象数据类型：树的实现1 需求分析 树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，直观来看，树是以分支关系定义的内部结构。树的结构在客观世界广泛存在，如人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得广泛应用，如在编译程序中，可用树来表示源程序的语法结构，又如在数据库系统中，树形结构也是信息的重要组织形式之一。2 实验目的 对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。 进而达到熟练地运用本课程中的基础知识及技术的目的。3 实验环境 1、 硬件：PC机 2、 软件：Microsoft Visual C+ 6.04 设计说明 本程序采用树的二叉链表（孩子指针-兄弟指针-双亲指针）存储表示，以下是树的结构定义和基本操作：ADT Tree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 若D仅含有一个数据元素，则R为空集，否则R=H，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-rootNULL，则存在D-root的一个划分D1,D2,D3, ,Dm(m0)，对于任意jk(1j,km)有DjDk=NULL,且对任意的i(1im)，唯一存在数据元素xiDi有H;(3) 对应于D-root的划分，H-,有唯一的一个划分H1，H2,Hm(m0)，对任意jk(1j,km)有HjHk=NULL，且对任意i(1im),Hi是Di上的二元关系，(Di,Hi)是一棵符合本定义的树，称为根root的子树。 基本操作P：InitTree(&T);操作结果：构造空树T。DestroyTree(&T);初始条件：树T存在。操作结果：销毁树T。CreateTree(&T,definition);初始条件：definition给出树T的定义。操作结果：按definition构造树T。ClearTree(&T);初始条件：树T存在。操作结果：将树T清为空树。TreeEmpty(T);初始条件：树T存在。操作结果：若T为空树，则返回TRUE，否则返回FALSE。TreeDepth(T);初始条件：树T存在。操作结果：返回的深度。Root(T);初始条件：树T存在。操作结果：返回T的根。Value(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：返回cur_e的值。Assign(T,cur_e,value);初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e赋值为value。Parent(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。LeftChild(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。RightSibling(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回“空”。InsertChild(&T,&p,I,c);初始条件：树存在，指向中某个结点，1ip指结点的度，非空树与不相交。操作结果：插入c为中指结点的第棵子树。DeleteChild(&T,&p,i);初始条件：树T存在，p指向T中某个结点，1ip指结点的度。操作结果：删除中所指结点的第棵子树。TraverseTree(T,visit();初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。CSTree Search(CSTree T,TElemType cur_e);初始条件：树T存在，cur_e可能是树T中某一个结点的值。操作结果：在树T中查找值为cur_e的结点，找到返回指向这个结点的指针，否则返回空指针。这个函数的作用是为了几个基本操作而服务的。void LevelOrderTraverseTree(CSTree T,void (* visit)(TElemType);初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按层次次序对T的每一个结点调用函数visit()一次且至多一次。void PreOrderTraverseTree(CSTree T,void(*visit)(TElemType);初始条件：树T存在，visit是对结点操作的应用函数。操作函数：按先序次序（先根遍历）对T的每一个结点调用函数visit()一次且至多一次。函数的功能实现是递归实现的。void PostOrderTraverseTree(CSTree T,void (*visit)(TElemType);初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按后根遍历对T的每一个结点调用函数visit()一次且至多一次。函数的功能实现是递归实现的。void visit_print(CSTree p);初始条件：树T存在，visit_print是对结点操作的应用函数。操作函数：对T的每一个结点调用函数visit_print()一次且至多一次。与visit函数不一样的是，visit函数只是输出一个结点的值，而visit_print还输出其结点，第一个孩子，其右兄弟和双亲的值void Print(CSTree T,void (*visit)(CSTree);附加函数：用于显示树的所有内容。初始条件：树T存在；操作结果：将树T的所有结点显示出来。ADT TreeR RRRR5 数据处理 树型数据存储样本： B RRRRC RRRRA RRRRF RRRRE RRRRD RRRRH RRRRG RRRRK RRRRR 转化后树的二叉链表存储：ABDECFGHHK 以下为数据样本测试：l 操作：判断树书否为空？ 结果：不为空l 返回树T的深度？ 结果： 4l 返回树T的根结点？ 结果： Al 返回树F结点的值？ 结果： Fl 将树根节点重新赋值为W ? 结果：AWl 求出结点A的双亲? 结果： Wl 求出结点A的第一个孩子结点? 结果： Dl 求出G的第一个兄弟结点? 结果： HXl 插入子树C至A中第2科子树？ ZY W 结果：ADBXCYEZGFHHK l 删除树结点为R的第三颗子树？结果：W ADBXYEZ l 多种遍历方式遍历树前序遍历树： W-A-D-X-Y-Z-E-B层次序遍历树： W-A-B-D-X-E-Y-Z后序遍历树： D-Y-Z-X-E-A-B-W 以下为运行EXE程序测试过程：选择1： 选择14:选择15：选择16：选择4：选择5： 选择6：选择7：选择8：选择9：选择10：选择11：选择12：选择13：选择14： 选择15：选择16： 选择2：6 程序清单解读/*抽象数据类型树-源码*/#include#includeusing namespace std;const int TRUE=1;const int FALSE=0;const int OK=1;const int ERROR=0;const int OVERFLOW=1;const int MAX=30;const char NIL= ; /*树的二叉链表孩子-兄弟-双亲存储表示*/typedef struct CSnode char data; CSnode *firstchild,*nextsibling,*parent; /*最左孩子指针 、下一个兄弟指针、双亲指针*/CSNode,*CSTree;/*树的辅助队列结构定义和操作*/typedef struct QNode CSTree data; QNode *next;QNode,*QueuePtr; /*队列的单链式存储结构*/typedef struct LinkQueue QueuePtr front,rear; /*队头、队尾指针*/LinkQueue;/*队列定义*/*构造一个空队列*/int InitQueue (LinkQueue &Q) if(!(Q.front=Q.rear=new QNode) exit(OVERFLOW); Q.front-next=NULL; return OK; /*销毁队列Q*/int DestroyQueue(LinkQueue &Q) while(Q.front) Q.rear=Q.front-next; delete Q.front; Q.front=Q.rear; return OK;/*将Q清为空队列*/int ClearQueue (LinkQueue &Q) QueuePtr p,q; Q.rear=Q.front; p=Q.front-next; Q.front-next=NULL; while(p) q=p; p=p-next; delete q; return OK;/*若队列Q为空队列则返回TRUE，否则返回FALSE*/int QueueEmpty( LinkQueue Q) if(Q.front=Q.rear) return TRUE; else return FALSE;/* 插入元素e为Q的新的队尾元素 */int EnQueue(LinkQueue &Q, CSTree e) QueuePtr p; if(!(p=new QNode) exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;/*若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR*/int DeQueue(LinkQueue &Q,CSTree &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; delete p; return OK;/*/*树的二叉链表孩子-兄弟-双亲存储定义*/*操作结果: 构造空树T*/int InitTree(CSTree &T)T=NULL;return OK;/*初始条件: 树T存在*/*操作结果: 销毁树T*/void DestroyTree(CSTree &T) if(T) if(T-firstchild) DestroyTree(T-firstchild); if(T-nextsibling) DestroyTree(T-nextsibling); delete T;/*初始条件：树T存在*/*操作结果：按层次次序创建树T*/int CreateTree(CSTree &T)char cMAX;CSTree p,p1,temp; LinkQueue q;InitQueue(q); coutdata=c0;T-nextsibling=NULL;T-parent=NULL;EnQueue(q,T);while(!QueueEmpty(q)DeQueue(q,p);coutn请输入datafirstchild=new CSNode; /*建立长子节点*/temp=p; /*保存该根节点*/ p1-parent=temp; /*建立双亲域*/p1-data=c0; EnQueue(q,p1); /*第一个孩子节点入队列*/for(int i=1;inextsibling=new CSNode; /*建立下一个兄弟节点*/ p1-nextsibling-data=ci; /* 下一个兄弟节点赋值*/ p1-nextsibling-parent=temp; /*建立下一个兄弟节点双亲域*/ EnQueue(q,p1-nextsibling); /*各兄弟入队*/ p1=p1-nextsibling;p1-nextsibling=NULL; /*最后的兄弟结点的nextsibling指针置为空*/ else /*树无孩子只有根节点*/p-firstchild=NULL;else T=NULL; /*空树*/return OK;/*初始条件：树T存在*/*操作结果：将树T清为空树*/void ClearTree(CSTree &T) if(T) if(T-firstchild) DestroyTree(T-firstchild); if(T-nextsibling) DestroyTree(T-nextsibling); delete T; T=NULL;/*初始条件：树T存在*/*操作结果：若T为空树，则返回TRUE，否则返回FALSE*/int TreeEmpty(CSTree T)if(T=NULL) return TRUE;else return FALSE;/*初始条件：树T存在*/*操作条件：返回T的深度*/int TreeDepth(CSTree T)CSTree p;int depth,max=0;if(!T)return 0;if(!T-firstchild)return 1;for(p=T-firstchild;p;p=p-nextsibling)depth=TreeDepth(p); /*递归求深度*/if(depthmax) max=depth;return max+1; /*返回深度要加上根节点*/ /*初始条件: 树T存在*/*操作结果: 返回T的根*/char Root(CSTree T)if(T) return T-data;else coutdata=cur_e) return a;if(a-firstchild) EnQueue(q,a-firstchild); if(a-nextsibling) EnQueue(q,a-nextsibling); return NULL;/*初始条件：树T存在，cur_e可能是树T中某个结点*/*操作结果：返回cur_e的值*/char Value(CSTree T, char cur_e)CSTree p;if(T)p=Search(T,cur_e); if(p) return p-data;elsecoutn在树中找不到值为cur_e的节点;return NIL;elsecoutn树空，无值为cur_e的节点; return NIL;/*初始条件：树T存在，cur_e可能是T中的某个结点*/*操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为空*/char Parent(CSTree T,char cur_e)CSTree p;if(T)p=Search(T,cur_e); if(!p)coutn在树中找不到值为cur_eparent) coutn值为cur_eparent-data; else coutn树空，无节点;return NIL;/*初始条件: 树T存在,cur_e是树T中结点的值*/*操作结果: 改cur_e为value*/int Assign(CSTree &T,char cur_e,char value) CSTree p; if(T) p=Search(T,cur_e); if(p) coutn找到节点cur_e,赋新值为data=value; return OK; else coutn找不到节点cur_e,操作无法完成; return ERROR; else coutn树为空，操作无法完成; return ERROR; /*初始条件：树T存在，cur_e可能是T中某个结点*/*操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回函数值为空。*/char LeftChild(CSTree T,char cur_e)CSTree p;if(T)p=Search(T,cur_e);if(!p)coutn找不到值为cur_efirstchild)coutfirstchild-data;elsecoutn树空，不存在值为cur_e的节点;return NIL;/*初始条件：树T存在，cur_e可能是T中的某个结点*/*操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回函数值为空*/char RightSibling(CSTree T,char cur_e)CSTree p;if(T)p=Search(T,cur_e);if(!p)coutn找不到值为cur_enextsibling)coutnextsibling-data;elsecoutn树空，不存在值为cur_e的节点;return NIL;/*初始条件：树T存在，p指向T中某个结点，1=i=p所指结点的度+1，非空树c与T不相交*/*操作结果：插入c为T中p指结点的第i棵子树*/int InsertChild(CSTree &T,CSTree p,int i,CSTree c)CSTree temp=p; /*保存根节点*/int j; if(!c)coutn子树为空，不执行操作;return OK;if(i1)coutn插入地址选择出错，不执行操作;return ERROR;if(!p)coutfirstchild&i1)coutnextsibling=p-firstchild;p-firstchild=c;c-parent=p; elsep=p-firstchild;j=2;while(p&jnextsibling;j+; if(j=i) /*找到插入位置*/ c-nextsibling=p-nextsibling;p-nextsibling=c;c-parent=temp; /*设置双亲节点*/else /*找不到插入位置*/ coutn插入节点错误; return ERROR; return OK;else /*树空*/coutn树空，操作不执行;return ERROR;/*初始条件：树T存在，p指向T中的某个结点，1=i=p所指结点的度*/*操作结果：删除T中p所指结点的第i棵子树*/int DeleteChild(CSTree &T,CSTree p,int i)CSTree q; int j; if(!T)coutn树为空，不执行操作;return OK;if(i1)coutn插入地址选择出错，不执行操作;return ERROR;if(!p)coutfirstchild&i1)coutfirstchild;p-firstchild=q-nextsibling; /*原次子现为长子*/ q-nextsibling=NULL;DestroyTree(q); /*销毁以q为根的子树*/ else /*删除非长子*/p=p-firstchild;j=2; while(p&jnextsibling;j+;if(j=i) /*找到第i棵子数*/q=p-nextsibling; p-nextsibling=q-nextsibling;q-nextsibling=NULL; DestroyTree(q); else /* 找不到该子树*/coutn删除节点错误，不执行操作;return ERROR;return OK;else /*树空*/coutn树空，删除错误，不执行操作;return ERROR;/*访问对结点操作的应用函数*/void visit(char value)coutdata); PreOrderTraverseTree(T-firstchild,visit) ; PreOrderTraverseTree(T-nextsibling,visit) ;/*初始条件：树T存在，visit是对结点操作的应用函数*/*操作结果：按后根遍历对T的每一个结点调用函数visit()一次且至多一次*/void PostOrderTraverseTree(CSTree T,void (*visit)(char)CSTree p; if(T) /*树不空*/if(T-firstchild) PostOrderTraverseTree(T-firstchild,visit); /*后根遍历长子子树*/ p=T-firstchild-nextsibling; /*p指向长子下一个兄弟*/ while(p) PostOrderTraverseTree(p,visit); /* 后根遍历下一个兄弟子树*/ p=p-nextsibling; /*p指向下一个兄弟*/ visit(T-data); /*最后访问根节点*/ /*初始条件：树T存在，visit是对结点操作的应用函数。*/*操作结果：按层次次序对T的每一个结点调用函数visit()一次且至多一次*/void LevelOrderTraverseTree(CSTree T,void (* visit)(char)LinkQueue Q;CSTree p,q;if(T) /*树不空*/InitQueue(Q);EnQueue(Q,T);while(!QueueEmpty(Q) /*队列不空*/DeQueue(Q,q);visit(q-data); /*访问节点*/if(q-firstchild) p=q-firstchild; EnQueue(Q,p); /*第一个孩子入队列*/while(p-nextsibling)p=p-nextsibling; EnQueue(Q,p); /*兄弟节点入队列*/else /*树空*/coutn树空，层次遍历失败!;/*/*界面函数*/int menu() int choose; do system(cls);/*清屏*/ coutt *endl; coutt *抽象数据类型: 树的孩子-兄弟-双亲存储表*endl; coutt *endl; cout endl; coutttt 1. 创建一棵树endl; coutttt 2. 销毁树endl; coutttt 3. 将树清为空树endl; coutttt 4. 判断树是否为空endl; coutttt 5. 返回树的深度endl; coutttt 6. 返回树的根节点endl; coutttt 7. 返回树中某个节点值endl; coutttt 8. 将树中某个节点重新赋值endl; coutttt 9. 求树中某节点双亲endl; coutttt 10. 求树中某节点最左孩子endl; coutttt 11. 求树中某节点右兄弟endl; coutttt 12. 插入一棵树endl; coutttt 13. 删除一棵树endl; coutttt 14. 先序遍历树endl; coutttt 15. 后序遍历树endl; coutttt 16. 层次遍历树endl; coutttt 17. 退出endl; coutt *endl; coutchoose; system(cls); /*运行前清屏*/ while(choose17); return choose; /*主函数*/int main() int i; CSTree T=NULL,T1,p; char e,e1; for(;) switch(menu()cas