AVL树C语言完整达成

发布时间：2021-11-20 16:44:53 所属栏目：教程来源：互联网

导读：采用非递归方式，效率较好，经过常规测试。 #include stdio.h #include string.h #include stdlib.h #include errno.h #include assert.h typedef enum { EH = 0, LH = 1, RH = -1 }bh_t; typedef enum { FALSE = 0, TRUE = 1 }bool_t; typedef int ElemType

采用非递归方式，效率较好，经过常规测试。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
#include <assert.h>

typedef enum
{
EH = 0,
LH = 1,
RH = -1
}bh_t;

typedef enum
{
FALSE = 0,
TRUE = 1
}bool_t;

typedef int ElemType;

typedef struct BSTNode
{
ElemType key;
int bf;
struct BSTNode *lchild,*rchild,*parent;
}BSTNode,*BSTree;

bool_t searchAVL(BSTree root,ElemType key, BSTNode **parent)
{
BSTNode *tmp = NULL;
assert(root != NULL);
*parent = root->parent;
tmp = root;
while(NULL != tmp)
{
  if(tmp->key == key)
  {
   return TRUE;
  }

  *parent = tmp;
  if(tmp->key > key)
  {
   tmp = tmp->lchild;
  }
  else
  {
   tmp = tmp->rchild;
  }
}
return FALSE;
}

/* get the minimum node*/
BSTNode* minNode(BSTNode* root)
{
if (root == NULL)
{
  return NULL;
}
while (root->lchild != NULL)
{
  root = root->lchild;
}
return root;
}

/* get the maximum node*/
BSTNode* maxNode(BSTNode* root)
{
if (root == NULL)
{
  return NULL;
}
while (root->rchild != NULL)
{
  root = root->rchild;
}
return root;
}

/* get the previous node*/
BSTNode* preNode(BSTNode* target)
{
if (target == NULL)
{
  return NULL;
}
if (target->lchild != NULL)
{
  return maxNode(target->lchild);
}
while ((target->parent!=NULL) && (target!=target->parent->rchild))
{
  target = target->parent;
}
return target->parent;
}

/* get the next node*/
BSTNode* nextNode(BSTNode* target)
{
if (target == NULL)
{
  return NULL;
}
if (target->rchild != NULL)
{
  return minNode(target->rchild);
}
while ((target->parent!=NULL) && (target!=target->parent->lchild))
{
  target = target->parent;
}
return target->parent;
}

BSTNode* leftbalance(BSTNode* root, BSTNode* parent, BSTNode* child)
{
BSTNode *cur;
assert((parent != NULL)&&(child != NULL));
/* LR */
if (child->bf == RH)
{
  cur = child->rchild;
  cur->parent = parent->parent;
  child->rchild = cur->lchild;
  if (cur->lchild != NULL)
  {
   cur->lchild->parent = child;
  }
  parent->lchild = cur->rchild;
  if (cur->rchild != NULL)
  {
   cur->rchild->parent = parent;
  }
  cur->lchild = child;
  cur->rchild = parent;
  child->parent = cur;

  if (parent->parent != NULL)
  {
   if (parent->parent->lchild == parent)
   {
    parent->parent->lchild = cur;
   }
   else
   {
    parent->parent->rchild = cur;
   }
  }
  else
  {
   root = cur;
  }
  parent->parent = cur;
  if (cur->bf == EH)
  {
   parent->bf = EH;
   child->bf = EH;
  }
  else if (cur->bf == RH)
  {
   parent->bf = EH;
   child->bf = LH;
  }
  else
  {
   parent->bf = RH;
   child->bf = EH;
  }
  cur->bf = EH;
}
/* LL */
else
{
  child->parent = parent->parent;
  parent->lchild = child->rchild;
  if (child->rchild != NULL)
  {
   child->rchild->parent = parent;
  }
  child->rchild = parent;
  if (parent->parent != NULL)
  {
   if (parent->parent->lchild == parent)
   {
    parent->parent->lchild = child;
   }
   else
   {
    parent->parent->rchild = child;
   }
  }
  else
  {
   root = child;
  }
  parent->parent = child;
  /* when insert */
  if (child->bf == LH)
  {
   child->bf = EH;
   parent->bf = EH;
  }
  /* when delete*/
  else
  {
   child->bf = RH;
   parent->bf = LH;
  }
}
return root;
}

BSTNode* rightbalance(BSTNode* root, BSTNode* parent, BSTNode* child)
{
BSTNode *cur;
assert((parent != NULL)&&(child != NULL));
/* RL */
if (child->bf == LH)
{
  cur = child->lchild;
  cur->parent = parent->parent;
  child->lchild = cur->rchild;
  if (cur->rchild != NULL)
  {
   cur->rchild->parent = child;
  }
  parent->rchild = cur->lchild;
  if (cur->lchild != NULL)
  {
   cur->lchild->parent = parent;
  }
  cur->lchild = parent;
  cur->rchild = child;
  child->parent = cur;
  if (parent->parent != NULL)
  {
   if (parent->parent->lchild == parent)
   {
    parent->parent->lchild = cur;
   }
   else
   {
    parent->parent->rchild = cur;
   }
  }
  else
  {
   root = cur;
  }
  parent->parent = cur;
  if (cur->bf == EH)
  {
   parent->bf = EH;
   child->bf = EH;
  }
  else if (cur->bf == LH)
  {
   parent->bf = EH;
   child->bf = RH;
  }
  else
  {
   parent->bf = LH;
   child->bf = EH;
  }
  cur->bf = EH;
}
/* RR */
else
{
  child->parent = parent->parent;
  parent->rchild = child->lchild;
  if (child->lchild != NULL)
   child->lchild->parent = parent;
  child->lchild = parent;
  if (parent->parent != NULL)
  {
   if (parent->parent->lchild == parent)
   {
    parent->parent->lchild = child;
   }
   else
   {
    parent->parent->rchild = child;
   }
  }
  else
  {
   root = child;
  }
  parent->parent = child;
  /* when insert */
  if (child->bf == RH)
  {
   child->bf = EH;
   parent->bf = EH;
  }
  /* when delete*/
  else
  {
   child->bf = LH;
   parent->bf = RH;
  }
}
return root;
}

BSTNode* insertNode(ElemType key, BSTNode* root)
{
BSTNode *parent = NULL, *cur = NULL, *child = NULL;
assert (root != NULL);
/* node exists*/
if (searchAVL(root,key,&parent))
{
  return root;
}
cur = (BSTNode*)malloc(sizeof(BSTNode));
cur->parent = parent;
cur->key = key;
cur->lchild = NULL;
cur->rchild = NULL;
cur->bf = EH;
if (key<parent->key)
{
  parent->lchild = cur;
  child = parent->lchild;
}
else
{
  parent->rchild = cur;
  child = parent->rchild;
}
/*get the minimax tree needed to be adjusted*/
while ((parent != NULL))
{
  if (child == parent->lchild)
  {
   if (parent->bf == RH)
   {
    parent->bf = EH;
    return root;
   }
   else if (parent->bf == EH)
   {
    root = leftbalance(root, parent, child);
    break;
   }
   else
   {
    parent->bf = LH;
    child = parent;
    parent = parent->parent;
   }
  }
  else
  {
   if (parent->bf == LH) //是右孩子，不会引起不平衡
   {
    parent->bf = EH;
    return root;
   }
   else if (parent->bf == RH) //是右孩子，并且引起parent的不平衡

   {
    root = rightbalance(root, parent, child);
    break;
   }
   else //是右孩子，并且可能引起parent的parent的不平衡
   {
    parent->bf = RH;
    child = parent;
    parent = parent->parent;
   }
  }
}

return root;
}

BSTNode* deleteNode(ElemType key, BSTNode* root)
{
BSTNode *dNode=NULL, *parent=NULL, *child = NULL;
ElemType temp;
assert(root!=NULL);
if (!searchAVL(root,key,&parent))
{
  return root;
}

if (parent == NULL)
{
  dNode = root;
}
else if ((parent->lchild!=NULL)&&(parent->lchild->key==key))
{
  dNode = parent->lchild;
}
else
{
  dNode = parent->rchild;
}

child = dNode;
while ((child->lchild!=NULL)||(child->rchild!=NULL)) //确定需要删除的结点
{
  if (child->bf == LH)
  {
   child = preNode(dNode);
  }
  else
  {
   child = nextNode(dNode);
  }
  temp = child->key;
  child->key = dNode->key;
  dNode->key = temp;
  dNode = child;
}

child = dNode;
parent = dNode->parent;

while ((parent != NULL)) //查找需要调整的最小子树
{
  if (child == parent->lchild)
  {
   if (parent->bf == LH)
   {
    parent->bf = EH;
    child = parent;
    parent = parent->parent;
   }
   else if (parent->bf == RH)
   {
    child = parent->rchild;
    root = rightbalance(root, parent, child);
    break;
   }
   else
   {
    parent->bf = RH;
    break;
   }
  }
  else
  {
   if (parent->bf == RH)
   {
    parent->bf = EH;
    child = parent;
    parent = parent->parent;
   }
   else if (parent->bf == LH)
   {

    child = parent->lchild;
    root = leftbalance(root, parent, child);
    break;
   }
   else
   {
    parent->bf = LH;
    break;
   }
  }
}
if (dNode->parent != NULL)
{
  if (dNode == dNode->parent->lchild)
  {
   dNode->parent->lchild = NULL;
  }
  else
  {
   dNode->parent->rchild = NULL;
  }
}
free(dNode);
dNode = NULL;
if (root == dNode)
{
  root = NULL; //root被删除, 避免野指针
}
return root;
}

BSTNode* createAVL(int *data, int size)
{
int i, j;
BSTNode *root;
if (size<1)
{
  return NULL;
}
root = (BSTNode*)malloc(sizeof(BSTNode));
root->parent = NULL;
root->lchild = NULL;
root->rchild = NULL;
root->key = data[0];
root->bf = 0;

for(i=1;i<size;i++)
  root = insertNode(data[i], root);
return root;
}

void destroyAVL(BSTNode* root)
{
if (root != NULL)
{
  destroyAVL(root->lchild);
  destroyAVL(root->rchild);
  free(root);
  root=NULL;
}

}

void InOrderTraverse(BSTree root)
{
if(NULL != root)
{
  InOrderTraverse(root->lchild);
  printf("%dt",root->key);
  InOrderTraverse(root->rchild);
}
}

void PreOrderTraverse(BSTree root)
{
if(NULL != root)
{
  printf("%dt",root->key);
  PreOrderTraverse(root->lchild);
  PreOrderTraverse(root->rchild);
}
}

int main(int argc, char *argv[])
{
int data[] = {1, 5, 7, 4, 3, 2, 11, 9, 10,100};
BSTNode* root;
root = createAVL(data, sizeof(data)/sizeof(data[0]));

printf("n++++++++++++++++++++++++++++n");
InOrderTraverse(root);
printf("n");
PreOrderTraverse(root);

root = deleteNode(5, root);
printf("n++++++++delete 5++++++++++n");
InOrderTraverse(root);
printf("n");
PreOrderTraverse(root);

root = deleteNode(3, root);
printf("n++++++++delete 3++++++++++n");
InOrderTraverse(root);
printf("n");
PreOrderTraverse(root);

root = deleteNode(1, root);
printf("n++++++++delete 1++++++++++n");
InOrderTraverse(root);
printf("n");
PreOrderTraverse(root);

root = deleteNode(7, root);
printf("n++++++++delete 7++++++++++n");
InOrderTraverse(root);
printf("n");
PreOrderTraverse(root);

root = deleteNode(4, root);
printf("n++++++++delete 4++++++++++n");
InOrderTraverse(root);
printf("n");
PreOrderTraverse(root);

root = deleteNode(2, root);
printf("n++++++++delete 2++++++++++n");
InOrderTraverse(root);
printf("n");
PreOrderTraverse(root);
printf("n");

destroyAVL(root);
}

（编辑：东莞站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

电脑公司 xp 纯净版系	电脑按哪个键是转换拼
液晶电视为什么无法替	扩展器扩展后为什么不