数据结构树的实现实验报告

数据结构设计性实验报告课程名称_________题目名称学生学院专业班级学号学生姓名指导教师2010年7月6日抽象数据类型：树的实现一．需求分析树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，直观来看，树是以分支关系定义的内部结构。树的结构在客观世界广泛存在，如人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得广泛应用，如在编译程序中，可用树来表示源程序的语法结构，又如在数据库系统中，树形结构也是信息的重要组织形式之一。二．实验目的对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。三．实验环境1、硬件：PC机2、软件：MicrosoftVisualC++6.0四．设计说明本程序采用树的二叉链表（孩子指针-兄弟指针-双亲指针）存储表示，以下是树的结构定义和基本操作：ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}≠NULL，则存在D-{root}的一个划分D1,D2,D3,…,Dm(m0)，对于任意j≠k(1≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di有root,xi∈H;(3)对应于D-{root}的划分，H-{root,xi,…,root,xm}有唯一的一个划分H1，H2,…,Hm(m0)，对任意j≠k(1≤j,k≤m)有Hj∩Hk=NULL，且对任意i(1≤i≤m),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);初始条件：树Ｔ存在，ｐ指向Ｔ中某个结点，1≤i≤p指结点的度＋１，非空树ｃ与Ｔ不相交。操作结果：插入c为Ｔ中ｐ指结点的第ｉ棵子树。DeleteChild(&T,&p,i);初始条件：树T存在，p指向T中某个结点，1≤i≤p指结点的度。操作结果：删除Ｔ中ｐ所指结点的第ｉ棵子树。TraverseTree(T,visit());初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。CSTreeSearch(CSTreeT,TElemTypecur_e);初始条件：树T存在，cur_e可能是树T中某一个结点的值。操作结果：在树T中查找值为cur_e的结点，找到返回指向这个结点的指针，否则返回空指针。这个函数的作用是为了几个基本操作而服务的。voidLevelOrderTraverseTree(CSTreeT,void(*visit)(TElemType));初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按层次次序对T的每一个结点调用函数visit()一次且至多一次。voidPreOrderTraverseTree(CSTreeT,void(*visit)(TElemType));初始条件：树T存在，visit是对结点操作的应用函数。操作函数：按先序次序（先根遍历）对T的每一个结点调用函数visit()一次且至多一次。函数的功能实现是递归实现的。voidPostOrderTraverseTree(CSTreeT,void(*visit)(TElemType));初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按后根遍历对T的每一个结点调用函数visit()一次且至多一次。函数的功能实现是递归实现的。voidvisit_print(CSTreep);初始条件：树T存在，visit_print是对结点操作的应用函数。操作函数：对T的每一个结点调用函数visit_print()一次且至多一次。与visit函数不一样的是，visit函数只是输出一个结点的值，而visit_print还输出其结点，第一个孩子，其右兄弟和双亲的值voidPrint(CSTreeT,void(*visit)(CSTree));附加函数：用于显示树的所有内容。初始条件：树T存在；操作结果：将树T的所有结点显示出来。}ADTTree五．数据处理树型数据存储样本：转化后树的二叉链表存储：RRRRRBRRRRERRRRHRRRRDRRRRCRRRRFRRRRGRRRRARRRRKRRRRRBCADEFGHHK以下为数据样本测试：操作：判断树书否为空？结果：不为空返回树T的深度？结果：4返回树T的根结点？结果：A返回树F结点的值？结果：F将树根节点重新赋值为W?结果：A—W求出结点A的双亲?结果：W求出结点A的第一个孩子结点?结果：D求出G的第一个兄弟结点?结果：H插入子树C至A中第2科子树？结果：XYZWBCADEFGHHKXYZ删除树结点为R的第三颗子树？结果：多种遍历方式遍历树前序遍历树：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程序测试过程：XYZBADEW选择1：选择14:选择15：选择16：选择4：选择5：选择6：选择7：选择8：选择9：选择10：选择11：选择12：选择13：选择14：选择15：选择16：选择2：六．程序清单解读/**************************抽象数据类型树-源码*********************************/#includeiostream#includeconio.husingnamespacestd;constintTRUE=1;constintFALSE=0;constintOK=1;constintERROR=0;constintOVERFLOW=1;constintMAX=30;constcharNIL='';/*****************树的二叉链表孩子-兄弟-双亲存储表示***************************/typedefstructCSnode{chardata;CSnode*firstchild,*nextsibling,*parent;/*最左孩子指针、下一个兄弟指针、双亲指针*/}CSNode,*CSTree;/********************树的辅助队列结构定义和操作******************************/typedefstructQNode{CSTreedata;QNode*next;}QNode,*QueuePtr;/*队列的单链式存储结构*/typedefstructLinkQueue{QueuePtrfront,rear;/*队头、队尾指针*/}LinkQueue;/*******************************队列定义**************************************//*构造一个空队列*/intInitQueue(LinkQueue&Q){if(!(Q.front=Q.rear=newQNode))exit(OVERFLOW);Q.front-next=NULL;returnOK;}/*销毁队列Q*/intDestroyQueue(LinkQueue&Q){while(Q.front){Q.rear=Q.front-next;deleteQ.front;Q.front=Q.rear;}returnOK;}/*将Q清为空队列*/intClearQueue(LinkQueue&Q){QueuePtrp,q;Q.rear=Q.front;p=Q.front-next;Q.front-next=NULL;while(p){q=p;p=p-next;deleteq;}returnOK;}/*若队列Q为空队列则返回TRUE，否则返回FALSE*/intQueueEmpty(LinkQueueQ){if(Q.front==Q.rear)returnTRUE;elsereturnFALSE;}/*插入元素e为Q的新的队尾元素*/intEnQueue(LinkQueue&Q,CSTreee){QueuePtrp;if(!(p=newQNode))exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnOK;}/*若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR*/intDeQueue(LinkQueue&Q,CSTree&e){QueuePtrp;if(Q.front==Q.rear)returnERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear==p)Q.rear=Q.front;deletep;returnOK;}/*****************************************************************************//***********************树的二叉链表孩子-兄弟-双亲存储定义*********************//*操作结果:构造空树T*/intInitTree(CSTree&T){T=NULL;returnOK;}/*初始条件:树T存在*//*操作结果:销毁树T*/voidDestroyTree(CSTree&T){if(T){if(T-firstchild)DestroyTree(T-firstchild);if(T-nextsibling)DestroyTree(T-nextsibling);deleteT;}}/*初始条件：树T存在*//*操作结果：按层次次序创建树T*/intCreateTree(CSTree&T){charc[MAX];CSTreep,p1,temp;LinkQueueq;InitQueue(q);cout请输入根节点，空格代表跟为空:;fflush(stdin)