AVL树C语言完整实现

#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;
}