AVL树代码,C代码库,德仔网

代码语言
代码分类
【C】 AVL树
作者:steady / 发布于2011/1/17/ 632
#include <iostream>
#include <string>
#include <fstream>
using namespace std;</div>
<div>const int LH = 1;
const int EH = 0;
const int RH = -1;</div>
<div>typedef struct BSTNode
{
string* data;
int bf;//balance factor
struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;</div>
<div>//右旋处理,处理后p指向新的树根结点,即原先树根的左子树的跟结点
void R_Rotate(BSTree &p);
//左旋处理,处理后p指向新的树根结点,即原先树根的右子树的跟结点
void L_Rotate(BSTree &p);
//对以指针T所指结点为根的二叉树做左平衡处理
void LeftBalance(BSTree &T);
//对以指针T所指结点为根的二叉树做右平衡处理
void RightBalance(BSTree &T);</div>
<div>//右旋处理,处理后p指向新的树根结点,即原先树根的左子树的跟结点
void R_Rotate(BSTree &p)
{
BSTree lc = p->lchild;//lc指向*p的左子树的根结点
p->lchild = lc->rchild;//lc的右子树挂接为*p的左子树
lc->rchild = p;//*p挂接为lc的右子树
p = lc;//p指向新的根结点
}
<div>//左旋处理,处理后p指向新的树根结点,即原先树根的右子树的跟结点
void L_Rotate(BSTree &p)
{
BSTree rc = p->rchild;
p->rchild = rc->lchild;
rc->lchild = p;
p = rc;
}
<div>/**
*若在平衡二叉排序树中不存在和e有相同关键字的结点,则插入一个数据元素为e的新结点,
*并返回1,否则返回0
*若因插入而使二叉排序树失去平衡,则做平衡选择处理,taller反应T是否变高
**/
int InsertAVL(BSTree &T, string e, bool &taller)
{
//空树
if(!T)
{
T = (BSTree)malloc(sizeof(BSTNode));
T->data = new string(e);
T->lchild = T->rchild = NULL;
T->bf = EH;
taller = true;
}
else
{
//树中已经存在和e有相同关键字的结点,不插入
if(e == *(T->data))
{
taller = false;
return 0;
}
//在*T的左子树中搜索
if(e < *(T->data))
{
//已经存在
if(!InsertAVL(T->lchild, e, taller))
{
return 0;
}
//插入并且*T的左子树长高
if(taller)
{
switch(T->bf)
{
//原本左子树就比右子树高
case LH:
LeftBalance(T);
taller = false;
break;
//原本左右子树等高
case EH:
T->bf = LH;
taller = true;
break;
//原本右子树比左子树高
case RH:
T->bf = EH;
taller = false;
break;
}//switch
}//if
}//if
else
{
if(!InsertAVL(T->rchild, e, taller))
{
return 0;
}
if(taller)
{
switch(T->bf)
{
case LH:
T->bf = EH;
taller = false;
break;
case EH:
T->bf = RH;
taller = true;
break;
case RH:
RightBalance(T);
taller = false;
break;
}
}
}
}
return 1;
}
<div></div>
<div>//对以指针T所指结点为根的二叉树做左平衡处理
void LeftBalance(BSTree &T)
{
BSTree lc = T->lchild;
switch(lc->bf)
{
case LH://新结点插入在*T的左孩子的左子树上,做LL旋转
T->bf = lc->bf = EH;
R_Rotate(T);
break;
case RH://新结点插入在*T的左孩子的右子树上,做LR旋转
BSTree rd = lc->rchild;
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;
L_Rotate(T->lchild);
R_Rotate(T);
}
}
<div></div>
<div>//对以指针T所指结点为根的二叉树做右平衡处理
void RightBalance(BSTree &T)
{
BSTree rc = T->rchild;
switch(rc->bf)
{
case RH:
T->bf = rc->bf = EH;
L_Rotate(T);
break;
case LH://新结点插入在*T的右子树的左孩子上,做RL旋转
BSTree rd = rc->lchild;
switch(rd->bf)
{
case RH:
T->bf = LH;
rc->bf = EH;
break;
case EH:
T->bf = rc->bf = EH;
break;
case LH:
T->bf = EH;
rc->bf = RH;
break;
}
rd->bf = EH;
R_Rotate(T->rchild);
L_Rotate(T);
}
}
<div>
void InitBSTree(BSTree &T)
{
T = NULL;</div>
<div>cout<<"输入文件名:"<<endl;
string fileName;
cin>>fileName;

fstream file(fileName.c_str());

string word;
bool taller = false;
while(file>>word, !file.eof())
{
InsertAVL(T, word, taller);
taller = false;
}
<div>file.close();
return ;
}
<div>
void DestroyBSTree(BSTree &T)
{
if(T)
{
if(T->lchild)
DestroyBSTree(T->lchild);
if(T->rchild)
DestroyBSTree(T->rchild);
delete T->data;
free(T);
T = NULL;
}
}
<div>
BSTree SearchBST(BSTree T, string e)
{
if(!T || e == *(T->data))
return T;
else if(e < *(T->lchild->data))
return SearchBST(T->lchild, e);
else
return SearchBST(T->rchild, e);
}
<div></div>
<div>void InorderTraverse(BSTree T)
{
if(T)
{
InorderTraverse(T->lchild);
cout<<*(T->data)<<endl;
InorderTraverse(T->rchild);
}
}
<div>
void main()
{
BSTree T;
InitBSTree(T);
InorderTraverse(T);
DestroyBSTree(T);
return ;
}
试试其它关键字
　AVL树　
同语言下
可能有用的
steady贡献的其它代码(2)
.AVL树
.IDA*算法