数据结构课程设计AVL树实现及其分析实验报告

AVL树的判断,查找,查入,删除,

算 法 与 数 据 结 构

课 程 设 计 报 告

题 目: AVLree的实现及分析 班 级: 12计算机1 学 号: 1200303132 姓 名: 熊成毅

成 绩: 2013年 12月31

日

AVL树的判断,查找,查入,删除,

一、AVLree的实现及分析

AVL 树是平衡的二元查找树。一株平衡的二元查找树就是指对其每一个节点，其左子树和右子树的高度只差不超过1.

编写程序实现AVL树的判别；并实现AVL树的ADT，包括其上的基本操作；节点的加入和删除。BSt和AVL的差别就在平衡性上，所以AVL的操作关键要考虑如何在保持二元查找树定义条件下对二元树进行平衡化。

（1） 编写AVL树的判别程序，并判别一个人元查找数是否为AVL树。二元查找树用其先序遍历结果表示，如：5,2,1,3,7,8.

（2） 实现AVL树的ADT，包括其上的基本操作：节点的加入和删除，另外包括将一般二元查找树转变为AVL树的操作。

二、设计思想（宋体，三号加粗）

任意给定一组数据，设计一个算法，建立一棵平衡二叉树，对它进行查找、插入、删除等操作。平衡二叉树ADT结构如下：

typedef struct{ Status key; }ElemType;

typedef struct BSTNode{ ElemType data; Status bf;

struct BSTNode *lchild,*rchild; }BSTNode,*BSTree;

给出一组数据，通过

InsertAVL(BSTree &T, ElemType e, Status &taller)插入算法，构建平衡二叉树，若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。

在此算法中，利用到递归算法和

LeftBalance(BSTree &T)左平衡处理，RightBalance(BSTree &T)右平衡处理。进而实现构建平衡二叉树，使其左子树和右子树的高度之差不超过1.

LeftBalance(BSTree &T）对以指针T所指结点为根的二叉树作左平衡旋转处理。本算法结束时，指针T指向新的根结点。

RightBalance(BSTree &T)// 对以指针T所指结点为根的二叉树作右平衡旋转处理。本算法结束时，指针T指向新的根结点。

R_Rotate(BSTree &p) 对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点

L_Rotate(BSTree &p) 对以p↑为根的二叉排序树作左旋处理，处理之后p指向新的树

AVL树的判断,查找,查入,删除,

根结点，即旋转处理之前的右子树的根结点

存在一个平衡二叉树，通过DeleteBST(BSTree &T, Status key)和Delete(BSTree &p)实现删除节点操作；

Delete(BSTree &p)从二叉排序树中删除结点p，并重接它的左或右子树。

DeleteBST(BSTree &T, Status key)若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点p，并返回TRUE；否则返回FALSE。

存在一个平衡二叉树，通过SearchBST(BSTree T, Status key, BSTree f, BSTree &p)实现查找节点操作；

SearchBST(BSTree T, Status key, BSTree f, BSTree &p)在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p指向查找路径上访问的最后一个结点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL。

存在一个二元排序树或二元查找树通过Balance(BSTree T)算法判断是否为AVL树， Balance(BSTree T)递归判断是不是平衡二叉树。

三、软件结构图及流程图（宋体，三号加粗）

主函数流程图：

AVL树的判断,查找,查入,删除,

构建AVL

查找函数流程图：

AVL树的判断,查找,查入,删除,

删除函数流程图：

四、测试（宋体，三号加粗）

创建AVL树，输入一组数据：

AVL树的判断,查找,查入,删除,

按先序遍历输出：

删除节点7；先序遍历结果：

插入数据6后的先序遍历结果：然后退出子目录操作。

AVL树的判断,查找,查入,删除,

输入一组数据创建BST树，

判断创建的BST是否为AVL树：

创建的BST树不是AVL树，将BST转换为AVL树

AVL树的判断,查找,查入,删除,

五、源程序（宋体，三号加粗）

函数头代码

#include "iostream.h" #include <stdio.h> #include <malloc.h>

#define MAXNODE 100 #define TRUE 1 #define FALSE 0 #define OVERFLOW 1 #define LH +1 #define EH 0 #define RH -1

typedef int Status; typedef char TElemType;

typedef struct {

Status key;

}ElemType;

typedef struct BSTNode { ElemType data; Status bf;

struct BSTNode *lchild,*rchild;

}BSTNode,*BSTree;

Status SearchBST(BSTree T, Status key, BSTree f, BSTree &p) {

// 算法9.5(b)

// 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，

// 若查找成功，则指针p指向该数据元素结点，并返回TRUE，

// 否则指针p指向查找路径上访问的最后一个结点并返回FALSE，

// 指针f指向T的双亲，其初始调用值为NULL

if (!T) { p = f; return FALSE; } // 查找不成功

else if (key==T->data.key) { p = T; return TRUE; } // 查找成功

else if (key<T->data.key)

return SearchBST(T->lchild, key, T, p); // 在左子树中继续查找 else

return SearchBST(T->rchild, key, T, p); // 在右子树中继续查找 } // SearchBST

Status InsertBST(BSTree &T, ElemType e) { // 算法9.6 // 当二叉排序树T中不存在关键字等于e.key的数据元素时，

// 插入e并返回TRUE，否则返回FALSE BSTree p,s;

if (!SearchBST(T, e.key, NULL, p)) { // 查找不成功

s = (BSTree)malloc(sizeof(BSTNode));

s->data = e; s->lchild = s->rchild = NULL; if (!p) T = s; // 插入 s 为新的根结点 else if (e.key<p->data.key) p->lchild=s; // 插入s为左孩子

else p->rchild = s; // 插入 s 为右孩子

return TRUE;

} else return FALSE; // 树中已有关键字相同的结点，不再插入 } // Insert BST

Status CreateBST(BSTree &T)//将输入的一组数据，创建为二叉排序树 { Status num; ElemType e;

cout<<"请输入二叉排序树结点数:"<<endl; cin>>num; while(num!=0) {

cout<<"请输入结点值:"<<endl;

cin>>e.key;

InsertBST(T,e);//按二叉排序树插入方法；

AVL树的判断,查找,查入,删除,

num--; }

return 0;

}

Status …… 此处隐藏：9644字，全部文档内容请下载后查看。喜欢就下载吧 ……