c语言编写实现平衡二叉树的动态插入和调整过程,平衡二叉树的实现实例

红太狼 2022-10-15 05:59 75阅读 0赞

/\*

首先平衡二叉树是一个二叉排序树；

其基本思想是：

在构建二叉排序树的过程中，当每插入一个节点时，

先检查是否因为插入而破坏了树的平衡性，若是，

找出最小不平衡树，进行适应的旋转，使之成为新的平衡二叉树。

\*/

\#include

\#define LH 1

\#define EH 0

\#define RH -1

using namespace std;

typedef struct BTNode

int data;

int BF;//平衡因子(balance factor)

struct BTNode \*lchild,\*rchild;

\}BTNode,\*BTree;

void R\_Rotate(BTree \*p)//以p为根节点的二叉排序树进行右旋转

BTree L;

L=(\*p)->lchild;

(\*p)->lchild=L->rchild;

L->rchild=(\*p);

\*p=L;//p指向新的根节点

void L\_Rotate(BTree \*p)//以p为根节点的二叉排序树进行左旋转

BTree R;

R=(\*p)->rchild;

(\*p)->rchild=R->lchild;

R->lchild=(\*p);

\*p=R;

void LeftBalance(BTree \*T)

BTree L,Lr;

L=(\*T)->lchild;

switch(L->BF)

//检查T的左子树平衡度，并作相应的平衡处理

case LH://新节点插入在T的左孩子的左子树上，做单右旋处理

(\*T)->BF=L->BF=EH;

R\_Rotate(T);

break;

case RH://新插入节点在T的左孩子的右子树上，做双旋处理

Lr=L->rchild;

switch(Lr->BF)

case LH:

(\*T)->BF=RH;

L->BF=EH;

break;

case EH:

(\*T)->BF=L->BF=EH;

break;

case RH:

(\*T)->BF=EH;

L->BF=LH;

break;

Lr->BF=EH;

L\_Rotate(&(\*T)->lchild);

R\_Rotate(T);

void RightBalance(BTree \*T)

BTree R,Rl;

R=(\*T)->rchild;

switch(R->BF)

case RH://新节点插在T的右孩子的右子树上，要做单左旋处理

(\*T)->BF=R->BF=EH;

L\_Rotate(T);

break;

case LH://新节点插在T的右孩子的左子树上，要做双旋处理

Rl=R->lchild;

switch(Rl->BF)

case LH:

(\*T)->BF=EH;

R->BF=RH;

break;

case EH:

(\*T)->BF=R->BF=EH;

break;

case RH:

(\*T)->BF=LH;

R->BF=EH;

break;

Rl->BF=EH;

R\_Rotate(&(\*T)->rchild);

L\_Rotate(T);

bool InsertAVL(BTree \*T,int e,bool \*taller)//变量taller反应T长高与否

if(!\*T)

\*T=(BTree)malloc(sizeof(BTNode));

(\*T)->data=e;

(\*T)->lchild=(\*T)->rchild=NULL;

(\*T)->BF=EH;

\*taller=true;

else

if(e==(\*T)->data)//不插入

\*taller=false;

return false;

if(edata)

if(!InsertAVL(&(\*T)->lchild,e,taller))//未插入

return false;

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;

else

//应在T的右子树中搜寻

if(!InsertAVL(&(\*T)->rchild,e,taller))

return false;

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 true;

bool Find(BTree T,int key)

if(!T)

return false;

else if(T->data==key)

return true;

else if(T->data

return Find(T->rchild,key);

else

return Find(T->lchild,key);

void Output(BTree T)

if(T)

printf("%d",T->data);

if(T->lchild||T->rchild)

printf("(");

Output(T->lchild);

printf(",");

Output(T->rchild);

printf(")");

int main(int argc,char \*argv\[\])

int i;

int A\[\]=\{3,2,1,4,5,6,7,10,9,8\};

BTree T=NULL;

bool taller;

for(i=0;i

InsertAVL(&T,A\[i\],&taller);

Output(T);

printf("\\n");

if(Find(T,6))

printf("6 is find in the AVL tree!\\n");

else

printf("6 is not find in the AVL tree!\\n");

return 0;

c语言编写实现平衡二叉树的动态插入和调整过程,平衡二叉树的实现实例

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关平衡二叉树（AVL）的实现

相关平衡二叉搜索树的实现

相关树（二）平衡二叉树

相关树：平衡二叉树

相关 c语言编写实现平衡二叉树的动态插入和调整过程,平衡二叉树的实现实例

相关平衡二叉树的实现原理

相关 “二叉树的深度”和“平衡二叉树”

相关平衡二叉树（c++实现）续

相关平衡二叉树（c++）实现

相关平衡二叉树 (平衡查找树)