AVL树C语言完整实现(3)

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("%d\t",root->key);
  InOrderTraverse(root->rchild);
 }
}

void PreOrderTraverse(BSTree root)
{
 if(NULL != root)
 {
  printf("%d\t",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);