首页 > algorithm > 树1(AVL树)

树1(AVL树)

  采用中序遍历二叉树,得到的也是一个有序的数列。
  完全按照伪码写出来后,就是不能运行,不知是自己加的遍历函数有问题还是插入实现上有问题。
  搞了半天,是没有解决一个问题,就是插入时,树里面的元素个数,如果没有的话,还得初始化一个树。
  14:10记录,下午时发现,原因是我插入时使用的是指针,结果呢?返回的时候,指针的值就变成了0,应该使用引用或双重指针,一个对结点的指针的引用,只有这样,才能改变树上的结点。现在出现的问题是这个树会自动的缩小,估计是昨天自己添的一个先左后右的平衡处理算法错了,才会导致现在的状况。
  15:20记录,其实挺喜欢VC6.0,强大的调试工具,断点分析的确能帮助新手很多忙。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#define LH 1
#define EH 0
#define RH -1
#define true 1
#define false 0
using namespace std;

typedef struct BSTNode
{
int data;
int bf; //结点的平衡因子
struct BSTNode *lchild,*rchild;//左右孩子
}BSTNode,*BSTree;

void R_Rotate(BSTree &p)//右旋
{
BSTree lc=p->lchild; //lc指向的*p的左子树根结点
p->lchild=lc->rchild; //lc的右子树挂接为*p的左子树
lc->rchild=p; //
p=lc; //p指向新的结点
}
void L_Rotate(BSTree &p)//左旋
{
BSTree rc=p->rchild;
p->rchild=rc->lchild;
rc->lchild=p;
p=rc;
}
//对以指针T所指结点为根的二叉树做左平衡旋转处理,结束时,指针T指向新的根结点
void leftBalance(BSTree &T)
{
BSTree lc =T->lchild,rd; //lc指向*T的左子树根结点
switch(lc->bf) //检查*T的左子树的平衡度,并作相应平衡处理
{
case LH: //新结点插入在*T的左孩子的左子树上,做单右旋处理
T->bf=lc->bf=EH;
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;
}//switch(rd->bf)
rd->bf=EH;
L_Rotate(T->lchild); //d对*T的左子树作为左平衡处理
R_Rotate(T); //对*T右旋处理
}//switch(lc->bf)
}
void rightBalance(BSTree &T)
{
BSTree rc =T->rchild,ld; //rc指向*T的右子树根结点
switch(rc->bf) //检查*T的右子树的平衡度,并作相应平衡处理
{
case RH: //新结点插入在*T的左孩子的右子树上,做单左旋处理
T->bf=rc->bf=EH;
L_Rotate(T);
break;
case LH: //新结点插入在*T的右子树的左子树上,要作双旋处理
ld = rc->lchild; //rd指向*T的右子树的左子树根上
switch(ld->bf) //修改*T以及右孩子的平衡因子
{
case LH:
T->bf=EH;
rc->bf=RH;
break;
case EH:
T->bf=rc->bf=EH;
break;
case RH:
T->bf=LH;
rc->bf=EH;
break;
}//switch(rd->bf)
ld->bf=EH;
R_Rotate(T->rchild); //d对*T的右子树作为右平衡处理
L_Rotate(T); //对*T左旋处理
}//switch(lc->bf)
}
/*如果在平衡的二叉排序树T中不存在和e有相同关键字的结点,则插入一个数据元素,为e的新结点,并返回1,否则返回0。如果因插入而使二叉排序树失去平衡,则作平衡旋转处理,变量taller反映T是否长高*/
int insertAVL(BSTree &T,int e,int taller)
{
if(T == NULL) /*插入新结点,树“长高”,置taller为true*/
{
T=(BSTree)malloc(sizeof(BSTNode));
T->data=e;
T->lchild=T->rchild=NULL;
T->bf=EH;
taller=true;
}
else
{
if(e == T->data) /*如果树中已经存在和e有相同关键字的结点,则返回不再插入*/
{
taller=false;
return 0;
}
if(e < T->data) /*如果小于,在*T的左子树进行搜索*/
{
if(!insertAVL(T->lchild,e,taller))/*未插入*/
return 0;
if(taller)/*以插入到*T的左子树且左子树长高*/
{
switch(T->bf)/*检查*T的平衡度*/
{
case LH:/*原本左子树比右子树高,需要作左平衡处理*/
leftBalance(T);
taller=false;
break;
case EH:/*原本一样高,现在左子树长高了*/
T->bf=LH;
taller=true;
break;
case RH:/*原本右子树高,现在一样高*/
T->bf=EH;
taller=false;
break;
}//switch(T->bf)
}
}
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;
}//switch(T->bf)
}
}
}
return 1;
}
void midTraverse(BSTree T)
{
if(T != NULL)
{
if(T->lchild != NULL)
midTraverse(T->lchild);
printf("%d ",T->data);
if(T->rchild != NULL)
midTraverse(T->rchild);
}
else
return;
}
int main(void)
{
int i,t,a[10]={83,19,65,47,86,29,82,94,12,55};
BSTree tree=NULL;
srand(time(0));
for(i=0;i<10;i++)
{
t=rand()%100;
printf("插入:%d\n",t);
insertAVL(tree,t,true);
midTraverse(tree);
printf("\n");
}
midTraverse(tree);
printf("\n");
return 0;
}
  1. Habib 9月 2nd, 2012 @ 07:37 | #1

    I feel satfiseid after reading that one.

评论提交中, 请稍候...

留言


可以使用的标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
Trackbacks & Pingbacks ( 0 )
  1. 还没有 trackbacks