数据结构——平衡二叉树的判定

数据结构——平衡二叉树的判定

数据结构课程设计

——平衡二元树的判定

系 别

专 业 班级学号

姓 名

指导教师

成 绩

2011 年 7 月 14 日

数据结构——平衡二叉树的判定

平衡二元树的判定

一、 需求分析

1. 平衡二叉树（Balanced Binary Tree）又被称为AVL树（区别于AVL算法），且具有以下性质：它是一棵空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。给定一个二元树的先序遍历或后序遍历结果，判定其是否为平衡二元树。

2. 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入中非法字符）和运算结果显示在其后。

二、 概要设计

1. ADT DynamicSearchTable{

数据结构D：D是具有相同特性的数据元素的集合。各个数据元素含有类型相同，可惟一标识数据元素的关键字。

数据关系R：数据元素同属一个集合。

基本操作P：

InitDSTable(&DT);

操作结果：构造一个空的动态查找表DT。

DestroyDSTable(&DT);

初试条件：动态查找表DT存在。

操作结果: 销毁动态查找表DT。

SearchDSTable(DT,key);

初试条件：动态查找表DT存在，key为和关键字类型相同的给定值。

操作结果: 若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或表中的位置，否则为“空”。

InsertDSTable(&DT,e);

初试条件：动态查找表DT存在，e为待插入的数据元素。

操作结果: 若DT中不存在其关键字等于e. key的数据元素，则插入e到DT。 DeleteDSTable(&DT,key);

初试条件：动态查找表DT存在，key为和关键字类型相同的给定值。 操作结果: 若DT中存在其关键字等于key的数据元素，则删除之。 TraverseDSTable(DT,Visit());

初试条件：动态查找表DT存在，Visit()是结点操作的应用函数。 操作结果: 按某种次序对DT的每个结点调用函数Visit()一次且至多 一次。一但Visit()失败，则操作失败。

}ADT DynamicSearchTable

2. 程序模块

2

数据结构——平衡二叉树的判定

本程序只有两个模块，调用关系简单本程序只有两个模块，调用关系简单：主程序模块和平衡二叉树的模块。即：

Void main(){

Do{

接受命令（根据提示输入终点城市和起点城市的序号）；

处理命令；

}while(“命令”=“退出”)；

}

3. 设计原理框图

数据结构——平衡二叉树的判定

三、 详细设计

1. 根据题目要求和查找的基本特点，其结点类型

typedef struct BSTnode{

int data;

int bf;

struct BSTnode *lchild,*rchild;

}BSTnode,*bstree;

#define LH +1

#define EH 0

#define RH -1

/*对平衡二叉树的操作

bstree InsertAVL(bstree &T, int e)；

////////在平衡二叉树中插入结点。

int FindAVL(bstree p,int e)；

////////查找平衡二叉树中是否有结点e。

bstree DeleteAVL(bstree &T,int e)

////////删除平衡平衡二叉树的结点e，并保持平衡二叉树的性质。

int Preordertraverse(bstree T)

////////按先序遍历平衡二叉树。

/------------------------************平衡二叉树的操作的详细算法

bstree InsertAVL(bstree &T, int e)

{

bstree p;

//插入新结点，树长高置taller为TRUE

if(!T) {

T=(bstree)malloc(sizeof(BSTnode));

T->data=e;

4

数据结构——平衡二叉树的判定

T->lchild=T->rchild=NULL;

T->bf=EH;

taller=TRUE;

}

else {

//树中存在和e有相同关键字的结点则不再插入

if(e==T->data){

taller=FALSE;

return NULL;

}

//值小于则继续在树的左子树中搜索

if(e < T->data){

//插入到左子树且左子树长高

p=InsertAVL(T->lchild,e);

if(p){

T->lchild=p;

if(taller) {

switch(T->bf){ //检查*T的平衡度

case LH: //原本左子树比右子树高，需要做左平衡处理

T=LeftBalance(T);

taller=FALSE;

break;

case EH: //原本左子树和右子树同高，现因左子树争高而使树增高

T->bf=LH;

taller=TRUE;

break;

case RH: //原本右子树比左子树高，现在左右子树等高

T->bf=EH;

taller=FALSE;

break;

}///////switch(T->bf)

}///////if(taller)

}/////if(p)

}///////if(e < T->data)

//继续在*T的右子树中搜索

else{

//插入到右子树且使右子树长高

p=InsertAVL(T->rchild,e);

if (p){

T->rchild=p;

if(taller) {

5

数据结构——平衡二叉树的判定

switch(T->bf){ //检查*T的平衡度

case LH: //原本左子树比右子树高，现在左右子树等高

T->bf=EH;

taller=FALSE;

break;

case EH: //原本左子树和右子树同高，现因右子树增高而使树增高

T->bf=RH;

taller=TRUE;

break;

case RH: //原本右子树比左子树高，需要做右平衡处理

T=RightBalance(T);

taller=FALSE;

break;

}//////switch(T->bf)

}/////if(taller)

}/////if (p)

}//////if(e > T->data)

}///////else< …… 此处隐藏：5490字，全部文档内容请下载后查看。喜欢就下载吧 ……