数据结构设计性实验报告 课程名称_____ ____ 题目名称 学生学院 专业班级 学 号 学生姓名 指导教师 2010 年 7 月 6 日 抽象数据类型：树的实现 一．需求分析 树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，直观来看，树是以分支关系定义的内部结构。树的结构在客观世界广泛存在，如人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得广泛应用，如在编译程序中，可用树来表示源程序的语法结构，又如在数据库系统中，树形结构也是信息的重要组织形式之一。 二．实验目的 对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。 进而达到熟练地运用本课程中的基础知识及技术的目的。 三．实验环境 1、 硬件：PC 机 2、 软件：Microsoft Visual C++ 6.0 四．设计说明 本程序采用树的二叉链表（孩子指针-兄弟指针-双亲指针）存储表示，以下是树的结构定义和基本操作： ADT Tree{ 数据对象D： D 是具有相同特性的数据元素的集合。 数据关系R： 若 D 为空集，则称为空树； 若 D 仅含有一个数据元素，则R 为空集，否则R={H}， H 是如下二元关系： (1) 在 D 中存在唯一的称为根的数据元素root，它在关系H 下无前驱； (2) 若 D-{root} ≠ NULL，则存在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。 DestroyTree(&T); 初始条件：树T 存在。 操作结果：销毁树T。 CreateTree(&T,definition); 初始条件：definition 给出树T 的定义。 操作结果：按definition 构造树T。 ClearTree(&T); 初始条件：树T 存在。 操作结果：将树T 清为空树。 TreeEmpty (T); 初始条件：树T 存在。 操作结果：若T 为空树，则返回TRUE，否则返回FALSE...
