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

《数据结构-树的实现实验报告》由会员分享，可在线阅读，更多相关《数据结构-树的实现实验报告（25页珍藏版）》请在文档大全上搜索。

1、 数据结构设计性实验报告 题目：抽象数据类型-树学 院 计算机学院 专 业 网络工程 年级班别 2013级4班 学 号 学生姓名 指导教师 成 绩 2015年 6 月 6 日 抽象数据类型：树的实现1题目采用树的二叉链表（孩子指针-兄弟指针-双亲指针）存储表示，实现抽象数据类型树。ADT Tree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 若D仅含有一个数据元素，则R为空集，否则R=H，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2) 若D-rootNULL，则存在D-root的一个划分D1,D2,D3

2、, ,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的定义。操作结果：按

3、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

4、);初始条件：树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为中指结点的第棵子树。Dele

5、teChild(&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的结点，找到返回指向这个结点的指针，否则返回空指针。这个函数的作用是为了几个基本操作而服务

6、的。void LevelOrderTraverseTree(CSTree T,void (* visit)(TElemType);初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按层次次序对T的每一个结点调用函数visit()一次且至多一次。void PreOrderTraverseTree(CSTree T,void(*visit)(TElemType);初始条件：树T存在，visit是对结点操作的应用函数。操作函数：按先序次序（先根遍历）对T的每一个结点调用函数visit()一次且至多一次。函数的功能实现是递归实现的。void PostOrderTraverseTree(C

7、STree 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

8、(*visit)(CSTree);附加函数：用于显示树的所有内容。初始条件：树T存在；操作结果：将树T的所有结点显示出来。ADT Tree2存储结构定义树的二叉链表孩子-兄弟-双亲存储表示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,r

9、ear; LinkQueue;构造一个空队列int InitQueue (LinkQueue &Q) if(!(Q.front=Q.rear=new QNode) return ERROR; Q.front-next=NULL; return OK;销毁队列Qint 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.f

10、ront; p=Q.front-next; Q.front-next=NULL; while(p) q=p; p=p-next; delete q; return OK;若队列Q为空队列则返回TRUE，否则返回FALSEint 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) return ERROR; p-data=e; p-next

11、=NULL; Q.rear-next=p; Q.rear=p; return OK;若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERRORint 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;3算法设计/*操作结果: 构造空树T*/int InitTree(CSTree &T)T