抽象类型实现-二叉树-实验报告.doc

文档介绍：抽象类型实现-二叉树-实验报告一、设计任务、要求及所用软件环境或工具设计任务:选用顺序存储结构和二叉链表存储结构实现抽象数据类型二叉树的基本操作编译环境:VC++、抽象数据类型定义二叉树抽象类型定义如下ADTBinaryTree{基本对象D:D是具有相同特性的数据元素的集合。数据关系R:若D,φ,则R,φ,称BinaryTree为空二叉树;若D?φ,则R,{H},H是如下二元关系:(1)在D中存在惟一的称为根的数据元素root,它在关系H下无前驱;(2)若D-{root}?φ,则存在D-{root}={D1,Dr},且D1?Dr,φ;(3)若D1?φ,则D1中存在惟一的元素x1,<root,x1>?H,且存在D1上的关系H1H;,若Dr?φ,则Dr中存在惟一的元素xr,<root,xr>?H,且存在D1上的关系Hr,H;H,{,root,xl,,,root,xr,,Hl,Hr};(4)(Dl,{Hl})是一棵符合本定义的二叉树,称为根的左子树,(Dr,{Hr})是一棵符合本定义的二叉树,称为根的右子树。基本操作P:InitBiTree(&T);操作结果:构造空二叉树T。DestroyBiTree(&T);初始条件:二叉树T存在操作结果:销毁二叉树TCreateBiTree(&T,definition);初始条件:definition给出二叉树T的定义操作结果:按definition构造二叉树TClearBiTree(&T);初始条件:二叉树T存在操作结果:将二叉树T清为空树BiTreeEmpty(T);初始条件:二叉树T存在操作结果:若T为空二叉树,则返回TRUE,否则返回FALSEBiTreeDepth(T);初始条件:二叉树T存在操作结果:返回T的深度Root(T);初始条件:二叉树T存在操作结果:返回T的根Value(T,e);初始条件:二叉树T存在,e是T中某个结点操作结果:返回e的值Assign(T,&e,value);初始条件:二叉树T存在,:结点e赋值为valueParent(T,e);初始条件:二叉树T存在,e是T中某个结点操作结果:若e是T的非根节点,则返回它的双亲,否则返回“空”LeftChild(T,e);初始条件:二叉树T存在,e是T中某个结点操作结果:返回e的左孩子。若e无左孩子,则返回“空”RightChild(T,e);初始条件:二叉树T存在,e是T中某个结点操作结果:返回e的右孩子。若e无右孩子,则返回“空”LeftSibling(T,e);初始条件:二叉树T存在,e是T中某个结点操作结果:返回e的左兄弟。若e是T的左孩子或无左兄弟,则返回“空”RightSibling(T,e);初始条件:二叉树T存在,e是T中某个结点操作结果:返回e的右兄弟。若e是T的右孩子或无右兄弟,则返回“空”InsertChild(T,p,LR,c);初始条件:二叉树T存在,p指向T中某个结点,LR为0或1,非空二叉树c与T不相交且右子树为空。操作结果:根据LR为0或1,插入c为T中p所指向结点的左或右子树。p所指结点的原有左或右子树则成为c的右子树DeleteChild(T,p,LR);初始条件:二叉树T存在,p指向T中某个结点,:根据LR为0或1,删除T中P所指结点的左或右子树PreOrderTraverse(T,Visit());初始条件:二叉树T存在,Visit是对结点操作的应用函数操作结果:先序遍历T,对每个结点调用函数Visit一次且仅一次。一旦visit()失败,则操作失败。InOrderTraverse(T,Visit());初始条件:二叉树T存在,Visit是对结点操作的应用函数操作结果:中序遍历T,对每个结点调用函数Visit一次且仅一次。一旦visit()失败,则操作失败PostOrderTraverse(T,Visit());初始条件:二叉树T存在,Visit是对结点操作的应用函数操作结果:后序遍历T,对每个结点调用函数Visit一次且仅一次。一旦visit()失败,则操作失败LevelOrderTraverse(T,Visit());初始条件:二叉树T存在,Visit是对结点操作的应用函数操作结果:层次遍历T,对每个结点调用函数Visit一次且仅一次。一旦visit()失败,则操作失败}、//**************************Includes*****************************#include""#include"conio.