资源描述：
《数据结构-树的实现实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、数据结构设计性实验报告课程名称_________题目名称学生学院专业班级学号学生姓名指导教师2010年7月6日抽象数据类型：树的实现一．需求分析树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，直观来看，树是以分支关系定义的内部结构。树的结构在客观世界广泛存在，如人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得广泛应用，如在编译程序中，可用树来表示源程序的语法结构，又如在数据库系统中，树形结构也是信息的重要组织形式之一。二．实验目的对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部
2、基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。三．实验环境1、硬件：PC机2、软件：MicrosoftVisualC++6.0四．设计说明本程序采用树的二叉链表（孩子指针-兄弟指针-双亲指针）存储表示，以下是树的结构定义和基本操作：ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}≠NULL，则存
3、在D-{root}的一个划分D1,D2,D3,…,Dm(m>0)，对于任意j≠k(1≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di有∈H;(3)对应于D-{root}的划分，H-{,…,}有唯一的一个划分H1，H2,…,Hm(m>0)，对任意j≠k(1≤j,k≤m)有Hj∩Hk=NULL，且对任意i(1≤i≤m),Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。基本操作P：InitTree(&T);操作结果：构造空树T。DestroyTre
4、e(&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中某个结点。操作结果
5、：返回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有右
6、兄弟，则返回它的右兄弟，否则返回“空”。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()失败，则操作失败。CSTre
7、eSearch(CSTreeT,TElemTypecur_e);初始条件：树T存在，cur_e可能是树T中某一个结点的值。操作结果：在树T中查找值为cur_e的结点，找到返回指向这个结点的指针，否则返回空指针。这个函数的作用是为了几个基本操作而服务的。voidLevelOrderTraverseTree(CSTreeT,void(*visit)(TElemType));初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按层次次序对T的每一个结点调用函数visit()一次且至多一次。void
