二叉平衡排序树课程设计.doc

《数据结构》课程设计

《数据结构》课程设计报告

设计题目：______二叉平衡排序树_________
姓 名：______宗小林_______
学 号：__ 210908046____
专 业：_ 计算机科学与技术_____
院 系：_计算机科学与技术学院___
班 级：__ 0902___________
指导教师：___ 王江涛___________

2011年 6 月 10 日

摘要：树形结构是以分支关系定义的层次结构，它是一种重要的非线性结构。树形结构在客观世界里普遍存在。而平衡二叉树因其特性：1、左右子树都是平衡二叉树。2、左子树和右子树的深度之差的绝对值不超过1.然而在二叉查找树中不论是插入还是删除，都需要在在二叉树上进行查找，查找的效率取决于二叉树的形态，二叉树越匀态，树的层次越少，平均查找深度越小，该树的查找效率就越高；构造一棵形态均匀的二叉查找树与结点插入的顺序有关，而结点插入的顺序往往不是随着人的而定的、、、、、、由此便引发了平衡二叉树

关键词：二叉树、平衡二叉树、查找

Abstract： Tree shape structure with the level structure that the sub - branch relates to definition, It is a kind of nonlinear structure. The tree shape structure is universal to exist in the objective world. But two fork the equilibrium tree is because of its characteristic:1. The or so son tree is all equilibrium two fork treeses.2. The bad absolute value anti of the depth of left son tree and right son tree over 1. However check to seek in two forks tree amid in spite of plug into or delete, all requirement in all aspects two the fork treetop progress check to seek, Check the efficiency for seeking to be decided by the appearance of two fork trees,
Two fork tree more even state, the level of tree is more little, check to seek depth on the average more small, the checking of tree seeks an efficiency more high.
Two forks that construct an appearance blance check to seek a tree to have something to do with node plugging into of sequence, But the node plug into of sequence usually be not along with person of but settle of……From here and then kindled equilibrium two fork treeses.

Keywords： binary tree banlanced binary tree search

目 录
1 问题描述 4
2 需求分析 4
3 概要设计 4
4 数据结构设计 5
5 算法设计 5
6 程序测试与实现 18
7 调试分析 19
8 遇到的问题及解决办法 20
9 心得体会 20

1 问题描述
创建二叉平衡排序树
要求：
1、 输入数据的数量不得低于15个
2、 建立二叉平衡排序树（要求包括LL型LR型RR型RL型四种调整方式）
3、完成任意数据的查找（要求给出查找执行的次数）。
2 需求分析
1． 迷本程序的功能包括二叉平衡树的创建、新结点的插入和删除、中序和先序（数据的查找）遍历二叉树。
2． 程序运行后显现提示信息，等候用户输入1---5以进入相应的操作功能。
3． 用户输入数据完毕，程序将输出运行结果。
4． 测试数据应为不少于15个整形数据。
3 概要设计
1． 总体使用的头文件：
#include<stdlib.h>
#include<iostream.h> //cout函数要使用
#include<iomanip> //setw要使用
2.常量定义：
#define LH 1 //左高
#define EH 0 //等高
#define RH -1 //右高
#define TRUE 1
#define FALSE 0
3.全局变量定义：
int taller=0; //taller反映T长高与否
int shorter=0; //shorter反映T变矮与否
4.几个关键函数：
(1)void Midorder(BSTree T) //树的中序遍历递归算法，一并输出平衡因子和左右结点的值，无返回值类型；
(2)BSTree R_Rotate(BSTree p) //以p为根的二叉排序树作右旋处理，处理之p指向新的树根节点即旋转处理之前的左子树根节点；
(3) BSTree L_Rotate(BSTree p) //以p为根的二叉排序树作左旋处理，处理之p指向新的树根节点即旋转处理之前的右子树根节点；
(4) BSTree LeftBalance(BSTree T) //对以指针T所指结点为根的二叉树作做左平衡旋转处理，本算法结束时指针T指向新的根节点；
(5) BSTree RightBalance(BSTree T) //对以指针T所指结点为根的二叉树作做右平衡旋转处理，本算法结束时指针T指向新的根节点；
(6) BSTree InsertAVL(BSTree T,int e) //向平衡树中插入一个节点，返回插入后的新根节点；
(7) BSTree LeftBalancel(BSTree p) //删除节点时对以指针T所指节点为根的二叉树作左平衡旋转处理，本算法结束时指针T指向新的根节点；
(8) BSTree RightBalancel(BSTree p) /删除节点时对以指针T所指节点为根的二叉树作右平衡旋转处理，本算法结束时指针T指向新的根节点；
(9) BSTree Delete(BSTree q, BSTree r) //对节点进行删除处理，本算法结束时q指针指向新的根节点。
（10）BSTree DeleteAVL(BSTree p, BSTree e) //找到要删除的节点，调用删除函数对其进行删除，本算法结束时指针p指向新的根结点
（11）BSTree CreatNode(int nodeValue) //建立关键字值为nodeValue的新结点，返回根节点
4 数据结构设计
1． 数据结构定义
//根据平衡二叉树的特点可以定义平衡二叉树的存储结构
//二叉排序树的类型定义
Typedef struct BSTNode
{
int data; //结点值
int bf; //结点的平衡因子
struct BSTNode *lchild,*rchild; //分别指向左右孩子的指针
} BSTNode,* BSTree; //同时声明一个BSTNode和一个指针类型的BSTree
5 算法设计
5.1 算法分析
如何去构造一棵平衡二叉树呢？下面来看一个具体的例子，假设表中关键子序列为（1，2,3,9,5）。空树和一个结点（1）的树显然都是平衡的二叉树。插入2之后仍是平衡的，只是根结点的平衡因子BF由0变为-1；继续插入3之后，由于结点1的BF由-1变为-2，出现了不平衡现象。这就好比一根扁担出现了一根轻一根重的现象。如将扁担的支撑点由结点1改为结点2，扁担的两头就平衡了。因此，可以对树做一个左逆时针“旋转”的操作，令结点2为根，而结点1作为它的左孩子，这样，结点1和2的平衡因子都为0，而且仍然保持二叉查找树的特性。继续插入9和5之后，由于结点3的BF由-1变成-2，出现了新的不平衡因子，需进行调整。但此时由于结点5插在结点9的左子树上，因此不能还像上次那样做简单的调整。对于以结点3为根的子树来说，既要保持二叉查找树的特性又要保持平衡，所以必须以5作为根结点而使3成为它的左子树的根，9成为它的右子树的根。这就好比对树做了；两次“旋转”操作-----先向右顺时针旋转，后向左逆时针旋转，使二叉树由不平衡变为平衡。总之，在构造一棵平衡二叉树或在平衡二叉树上插入一个结点时，可能造成二叉树失衡，这时就要对失衡的二叉树进行平衡化处理。平衡处理的方法有4种：LL、RR、LR、RL
5.2 算法实现
#include<stdlib.h>
#include<iostream.h> //cout函数要使用
#include<iomanip.h>
#define LH 1 //左高
#define EH 0 //等高
#define RH -1 //右高
#define TRUE 1
#define FALSE 0
int taller=0; //taller反映T长高与否
int shorter=0; //shorter反映T变矮与否
Typedef struct BSTNode
{
int data; //结点值
int bf; //结点的平衡因子
struct BSTNode *lchild,*rchild; //分别指向左右孩子的指针
} BSTNode,*BSTree; //同时声明一个BSTNode和一个指针类型的BSTree
//建立新结点
BSTree CreatNode(int nodeValue)
{
BSTree node;
node=(BSTree)malloc(sizeof(BSTree));
node->data=nodeValue;
node->bf=0;
node->lchild=NULL;
node->rchild=NULL;
return node;
}
//新建二叉树函数
BSTree BuildTree(BSTree r)
{
//如果传入根结点不为空，则数以构建过，退出函数
if(r!=NULL)
{
cout<<"二叉平衡树已建立";
return NULL;
}
//根节点为空则开始创建
cout<<"请输入节点值，输入零则结束"<<endl;
int nodeValue;
cin>>nodeValue;
while(nodeValue)//插入任何小于0的数值
{
BSTree node=CreatNode(nodeValue);
//如果根为空，则将此节点设置为根结点，否则将此节点作为非根节点插入
if(r==NULL)
r=node;
else
r=InsertAVL(r.nodeValue);
cin>>nodeValue;//获取用户输入的新值
}
return r;
}
void MidOrder(BSTree T) //树的中序遍历递归算法，一并输出平衡因子和左右结点的值，无返回值类型；
{
//中序遍历的特点是当二叉树为空时则空操作，否则
//1，中序遍历左子树
//2,访问根结点
//3,中序遍历右子树
if(T->lchild) MidOrder(T->lchild);
if(T->data)
{
//以适当的形式格式化输出各个节点及其附加信息可以方便用户重构二叉树
cout<<setw(4)<<T->data<<setw(6)<<T->bf;
if(T->lchild) cout<<setw(8)<< T->lchild->data; else cout<<setw(8)<<"-";
if(T->rchild) cout<< setw(8)<< T->rchild->data; else cout<<setw(8)<<"-";
cout<<endl;
}
if(T->rchild)) MidOrder(T->rchild));
}
void RootOrder(BSTree T) //树的先序遍历递归算法，一并输出平衡因子和左右结点的值，无返回值类型；
{
//先序遍历的特点是当二叉树为空时则空操作，否则
//1，访问根结点
//2,先序遍历左子树
//3,先序遍历右子树
if(T->data)
{
cout<<setw(4)<<T->data<<setw(6)<<T->bf;
if(T->lchild) cout<<setw(8)<< T->lchild->data; else cout<<setw(8)<<"-";
if(T->rchild) cout<< setw(8)<< T->rchild->data; else cout<<setw(8)<<"-";
cout<<endl;
}
if(T->lchild)) RootOrder(T->lchild));
if(T->rchild)) RootOrder(T->rchild));
}
BSTree R_Rotate(BSTree p) //以p为根的二叉排序树作右旋处理，处理之p指向新的树根节点即旋转处理之前的左子树根节点；
{
BSTNode *lc; //声明BSTNode *为临时变量
lc=p->lchild; //rc指向*p的左子树的根结点
p->lchild=lc->rchild; //rc的左子树挂接为p的右子树
lc->rchild=p;
p=lc; //p指向新的根节点返回新的根节点
return p; //返回新的根节点
}
BSTree L_Rotate(BSTree p) //以p为根的二叉排序树作左旋处理，处理之p指向新的树根节点即旋转处理之前的右子树根节点；
{
BSTNode *rc; //声明BSTNode *为临时变量
rc=p->rchild; //rc指向*p的右子树的根结点
p->rchild=rc->lchild; //rc的左子树挂接为*p的右子树
lc->rchild=p;
p=rc; //p指向新的根节点返回新的根节点
return p; //返回新的根节点
}
BSTree LeftBalance(BSTree T) //对以指针T所指结点为根的二叉树作做左平衡旋转处理，本算法结束时指针T指向新的根节点；
{
BSTNode *lc,*rd;
lc=T->lchild; //lc指向*T的左子树根结点
switch(lc->bf) //检查*T的左子树平衡度，并作相应的平衡处理
{
case LH: //新结点插入在*T的左孩子的左子树上，要做单右旋处理
T->bf=lc->bf=EH;
T=R_Rotate(T);
break;
case RH: //新结点插入在*T的左孩子的右子树上，要做双旋处理
rd=lc->rchild; //rd指向*T的左孩子的右子树根
switch(rd->bf) //修改*T及其左孩子的平衡因子
{
case LH:
T->bf=RH;
lc->bf=EH;
break;
case EH:
T->bf=lc->bf=EH;
break;
case RH:
T->bf=EH;
lc->bf=LH;
break
}
rd->bf=EH;
T->lchild=L_Rotate(T->lchild);//对*T的左孩子做左旋平衡处理
T=R_Rotate(T); //对*T做右旋处理
}
returnT;
}
BSTree RightBalance(BSTreeT) //T所指结点为根的二叉树作做右平衡旋转处理，本算法结束时指针T指向新的根节点；
{
BSTree rc,ld;
rc=T->rchild; //rc指向*T的右子树根结点
switch(rc->bf) //检查*T的右子树平衡度，并作相应的平衡处理
{
case RH: //新结点插入在*T的右孩子的右子树上，要做单右旋处理
T->bf=rc->bf=EH;
T=L_Rotate(T);
break;
case LH: //新结点插入在*T的右孩子的左子树上，要做双旋处理
ld=rc->lchild; //rd指向*T的右孩子的左子树根
switch(ld->bf) //修改*T及其右孩子的平衡因子
{
case LH:
T->bf=LH;
rc->bf=EH;
break;
case EH:
T->bf=rc->bf=EH;
break;
case RH:
T->bf=EH;
rc->bf=RH;
break;
}
ld->bf=EH;
T->rchild=R_Rotate(T->rchild);//对*T的右孩子做右旋平衡处理
T=L_Rotate(T); //对*T做左旋处理
}
returnT;
}
bool search(BTreeNode<T> *p,T elem,int& count)
{
if(p==NULL)
return(false);
else if(p->data==elem)
{
count++;
return(true);
}
else if(p->data>elem)
{
count++;
return(search(p->lchild,elem,count));
}
else
{
count++;
return(search(p->rchild,elem,count));
}
}
template<class T>
bool search(T elem,int& count)
{
return(search(root,elem,count));
}
template <class T>
void BSTree<T>::prnt(BTreeNode<T> *p, int l)
{ if (p!=NULL )
{ prnt(p->rchild,l+1);
for (int i=0;i<6*(l-1);i++)cout<<" ";
cout<<"..."<<p->data<<endl;
prnt(p->lchild,l+1);
}
}
//若在平衡的二叉树T中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点，并返回插入后所建成的平衡二叉排序树，否则返回NULL。若因插入而使二叉树失去平衡，则做平衡旋转处理，布尔变量taller反映T长高与否。
BSTree InsertAVL(BSTree T,int e) //向平衡树中插入一个节点，返回插入后的新根节点；
{
BSTree p;
//插入新结点，树长高置taller为TRUE
if(!T)
{
T=(BSTree)malloc(sizeof(BSTNode));
T->data=e;
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;
}
}
}
}
else
{ //继续进行再*T的右子数中搜索
p=InsertAVL(T->rchild,e);
if(p)
{
T->rchild=p;
if(taller)
{
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;

}
}
}
}
}
return T;
}
BSTree LeftBalancel(BSTree p) //删除节点时对以指针T所指节点为根的二叉树作左平衡旋转处理，本算法结束时指针T指向新的根节点
{
BSTree p1,p2;
//左子树比右子树高
if(p->bf==1)
{
p->bf=0;
shorter=1;
}
else
if(p->bf==0)
{
p->bf=-1;
shorter=0;
}
else
{
pl=p->rchild;
if(pl->bf==0)
{
p->rchild=pl->lchild;
pl->lchild=p;
pl->bf=1;
p->bf=-1;
p=pl;
shorter=0;
}
else
{
if(pl->bf==-1)
{
p->rchild=pl->lchild;
pl->lchild=p;
pl->bf=0;
p->bf=0;
p=pl;
shorter=1;
}
else
{
p2=pl->lclild;
p1->lchild=p2->rchild;
p2->rchild=p1;
p->rchild=p2->lchild;
p2->lchild=p;
if(p2->bf==0)
{
p->bf=0;
pl->bf=0;
}
else
if(p2->bf==-1)
{
p->bf=1;
pl->bf=0;
}
else
{
p->bf=0;
pl->bf=1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
return p;
}
BSTree RightBalancel(BSTree p) //删除节点时对以指针T所指节点为根的二叉树作右平衡旋转处理，本算法结束时指针T指向新的根节点
{
BSTree p1,p2;
//左子树比右子树高
if(p->bf==-1)
{
p->bf=0;
shorter=1;
}
else
if(p->bf==0)
{
p->bf=1;
shorter=0;
}
else
{
pl=p->lchild;
if(pl->bf==0)
{
p->lchild=pl->rchild;
pl->rchild=p;
pl->bf=-1;
p->bf=1;
p=pl;
shorter=0;
}
else

if(pl->bf==1)
{
p->lchild=pl->rchild;
pl->rchild=p;
pl->bf=0;
p->bf=0;
p=pl;
shorter=1;
}
else
{
p2=pl->rclild;
p1->rchild=p2->lchild;
p2->rchild=p1;
p->lchild=p2->rchild;
p2->rchild=p;
if(p2->bf==0)
{
p->bf=0;
pl->bf=0;
}
else
if(p2->bf==1)
{
p->bf=-1;
pl->bf=0;
}
else
{
p->bf=0;
pl->bf=1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
return p;
}
//对结点进行删除处理
BSTree Delete(BSTree q, BSTree r)
{
if(r->rchild==NULL) //根结点的右子树为空则将左子树提高并标记树变矮了
{
q->data=r->data;
q=r;
r=r->lchild;
free(q);
shorter=1;
}
else //继续递归并删除
{
r->rchild=Delete(q,r->rchild);
}
return r;
}
//找到要删除的的结点并调用删除函数对其进行删除
BSTree DeleteAVL(BSTree p, int e)
{
BSTree q; //抛弃空删除
if(p==NULL) return NULL;
else
if(e<p->data) //欲删除小于当前节点的值则继续本左子树上搜索
{
p->lchild=DeleteAVL(p->lchild,e);
if(shorter==1) p=RightBalancel(p);
return p;
}
else
if(e>p->data) //欲删除大于当前节点的值则继续本右子树上搜索
{
p->rchild=DeleteAVL(p->rchild,e);
if(shorter==1) p=RightBalancel(p);
return p;
}
else
{//找到了
q=p;//将p存储到临时变量Q中
if(p->rchild==NULL)
{
p=p->lchild;
free(q);
shorter=1;
}
else
if(p->lchild==NULL)
{
p=p->rchild;
free(q);
shorter=1;
}
else
{
//将删除后的子树得到的新的子树的根节点赋值给q左子树
q->lchild=Delete(q,q->lchild);
//如果树高到变矮了则要执行删除后的左平衡处理
if（shorter==1） q=LeftBalancel(q);
p=q;
}
}
return p;
}
5.3 算法流程图

定义一个结点结构

创建结点

插入结点

创建一棵二叉树
删除结点

进行调整（四种类型）

二叉树是否平衡

6 程序测试与实现
main
BuildTree
InsertAVL
DeleteAVL
MidOrder
RootOrder

6.1 主程序：
void main()
{
int a[15]={26,17,38,19,11,15,12,10,20,14,25,24,30,32,3};
int s;
int count=0;
BSTree<int> mytree(a,15);
int h=mytree.dep();
int n;
n=pow(2, h)-1;
BTreeNode<int> *b[50];
cout<<"输入的序列："<<endl;
for(int i=0;i<15;i++)
cout<<setw(3)<<a[i];
cout<<endl;
cout<<"创建的二叉平衡树"<<endl;
mytree.Miderorder(b,n);
mytree.Vprnt(b,n,h);
cout<<" 请输入要查找的数据"<<endl;
cin>>s;
if(mytree.search(s,count))
cout<<"查找成功,共进行了"<<count<<"次查找"<<endl;
else
cout<<"查找不成功"<<endl;
}
测试结果

图6-1测试结果
7 调试分析
1．链表中的结点变量是通过指针变量来访问的。因为在C语言中是用P—>来表示P所指的变量，又由于结点类型是一个结构类型，因此可用P—> data和P—>next分别表示结点的数据域变量和指针域变量。指针变量的值要么为空(NULL)，不指向任何结点；要么其值为非空，即它的值是一个结点的存储地址。注意，当P为空值时，则它不指向任何结点，此时不能通过P 来访问结点，否则会引起程序错误。
2．算法的时空分析：
(1)对于本程序的结构类型，其操作运算主要有插入新结点,左右调整和删除树。以上各操作运算的平均时间复杂度为O(n)，其主要时间是耗费在查找操作上。
8 遇到的问题及解决办法
1、程序过于复杂-------用指针解决，将程序分解成多个子程序以降低难度；
2、二叉树的四种不平衡现象的调整困难--------概括性的进行左调整和右调整；
3、将树层次遍历并放入数组的函数要注意左右子树的前驱和后继结点。
9 心得体会
想起