Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3795878
  • 博文数量: 93
  • 博客积分: 3189
  • 博客等级: 中校
  • 技术积分: 4231
  • 用 户 组: 普通用户
  • 注册时间: 2009-02-02 13:29
个人简介

出没于杭州和青岛的程序猿一枚,对内核略懂一二

文章分类

全部博文(93)

文章存档

2016年(2)

2015年(3)

2014年(11)

2013年(29)

2012年(16)

2011年(5)

2010年(5)

2009年(22)

分类: C/C++

2009-03-19 14:55:38

这是转载的一个平衡二叉树的C语言实现,具体忘了从哪看到的了,感觉写的很好,贴出来大家一块看看。

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

typedef struct node node;

struct node
{
  node* parent;
  node* left;
  node* right;
  int balance; //左右子树高度之差

  int key;
};

extern void traverseAVL1(node* root); //中序遍历, 下面定义


extern void traverseAVL2(node* root); //前序遍历, 下面定义


int searchNode(int key, node* root, node** parent) //按key查找结点

{
  node* temp;
  assert(root != NULL);
  temp = root;
  *parent = root->parent;
  while (temp !=NULL)
  {
    if (temp->key == key)
      return 1;
    else
    {
       *parent = temp;
      if (temp->key > key)
        temp = temp->left;
      else
        temp = temp->right;
    }
  }
  return 0;
}

node* minNode(node* root) //树root的最小结点

{
  if (root == NULL)
    return NULL;
  while (root->left != NULL)
    root = root->left;
  return root;
}

node* maxNode(node* root) //树root的最大结点

{
  if (root == NULL)
    return NULL;
  while (root->right != NULL)
    root = root->right;
  return root;
}

node* preNode(node* target) //求前驱结点

{
  if (target == NULL)
    return NULL;
  if (target->left != NULL)
    return maxNode(target->left);
  else
    while ((target->parent!=NULL) && (target!=target->parent->right))
      target = target->parent;
  return target->parent;
}

node* nextNode(node* target) //求后继结点

{
  if (target == NULL)
    return NULL;
  if (target->right != NULL)
    return minNode(target->right);
  else
    while ((target->parent!=NULL) && (target!=target->parent->left))
      target = target->parent;
  return target->parent;
}

node* adjustAVL(node* root, node* parent, node* child)
{
  node *cur;
  assert((parent != NULL)&&(child != NULL));
  switch (parent->balance)
  {
  case 2:
    if (child->balance == -1)//LR型

    {
      cur = child->right;
      cur->parent = parent->parent;
      child->right = cur->left;
      if (cur->left != NULL)
        cur->left->parent = child;
      parent->left = cur->right;
      if (cur->right != NULL)
        cur->right->parent = parent;
      cur->left = child;
      child->parent = cur;
      cur->right = parent;
      if (parent->parent != NULL)
        if (parent->parent->left == parent)
          parent->parent->left = cur;
        else parent->parent->right = cur;
      else
        root = cur;
      parent->parent = cur;
      if (cur->balance == 0)
      {
        parent->balance = 0;
        child->balance = 0;
      }
      else if (cur->balance == -1)
      {
        parent->balance = 0;
        child->balance = 1;
      }
      else
      {
        parent->balance = -1;
        child->balance = 0;
      }
      cur->balance = 0;
    }
    else //LL型

    {
      child->parent = parent->parent;
      parent->left = child->right;
      if (child->right != NULL)
        child->right->parent = parent;
      child->right = parent;
      if (parent->parent != NULL)
        if (parent->parent->left == parent)
          parent->parent->left = child;
        else parent->parent->right = child;
      else
        root = child;
      parent->parent = child;
      if (child->balance == 1) //插入时

      {
        child->balance = 0;
        parent->balance = 0;
      }
      else //删除时

      {
        child->balance = -1;
        parent->balance = 1;
      }
    }
   break;
   
  case -2:
    if (child->balance == 1) //RL型

    {
      cur = child->left;
      cur->parent = parent->parent;
      child->left = cur->right;
      if (cur->right != NULL)
        cur->right->parent = child;
      parent->right = cur->left;
      if (cur->left != NULL)
        cur->left->parent = parent;
      cur->left = parent;
      cur->right = child;
      child->parent = cur;
      if (parent->parent != NULL)
        if (parent->parent->left == parent)
          parent->parent->left = cur;
        else parent->parent->right = cur;
      else
        root = cur;
      parent->parent = cur;
      if (cur->balance == 0)
      {
        parent->balance = 0;
        child->balance = 0;
      }
      else if (cur->balance == 1)
      {
        parent->balance = 0;
        child->balance = -1;
      }
      else
      {
        parent->balance = 1;
        child->balance = 0;
      }
      cur->balance = 0;
    }
    else //RR型

    {
      child->parent = parent->parent;
      parent->right = child->left;
      if (child->left != NULL)
        child->left->parent = parent;
      child->left = parent;
      if (parent->parent != NULL)
        if (parent->parent->left == parent)
          parent->parent->left = child;
        else parent->parent->right = child;
      else
        root = child;
      parent->parent = child;
      if (child->balance == -1) //插入时

      {
        child->balance = 0;
        parent->balance = 0;
      }
      else //删除时

      {
        child->balance = 1;
        parent->balance = -1;
      }
    }
    break;
  }
  return root;
}


node* insertNode(int key, node* root)
{
  node *parent, *cur, *child;
  assert (root != NULL);
  if (searchNode(key, root, &parent)) //结点已存在

    return root;
  else
  {
    cur = (node*)malloc(sizeof(node));
    cur->parent = parent;
    cur->key = key;
    cur->left = NULL;
    cur->right = NULL;
    cur->balance = 0;
    if (key<parent->key)
    {
      parent->left = cur;
      child = parent->left;
    }
    else
    {
      parent->right = cur;
      child = parent->right;
    }
    
    while ((parent != NULL)) //查找需要调整的最小子树

    {
      if (child == parent->left)
        if (parent->balance == -1)
        {
          parent->balance = 0;
          return root;
        }
        else if (parent->balance == 1)
        {
          parent->balance = 2;
          break;
        }
        else
        {
          parent->balance = 1;
          child = parent;
          parent = parent->parent;
        }
      else if (parent->balance == 1) //是右孩子,不会引起不平衡

      {
        parent->balance = 0;
        return root;
      }
      else if (parent->balance == -1) //是右孩子,并且引起parent的不平衡

      {
        parent->balance = -2;
        break;
      }
      else //是右孩子,并且可能引起parent的parent的不平衡

      {
        parent->balance = -1;
        child = parent;
        parent = parent->parent;
      }
    }
    
    if (parent == NULL)
      return root;
    return adjustAVL(root, parent, child);
  }
}


node* deleteNode(int key, node* root)
{
  node *dNode, *parent, *child;
  int temp;
  assert(root!=NULL);
  if (!searchNode(key, root, &parent))
    return root;
  else
  {
    if (parent == NULL)
      dNode = root;
    else if ((parent->left!=NULL)&&(parent->left->key==key))
      dNode = parent->left;
    else dNode = parent->right;

    child = dNode;
    while ((child->left!=NULL)||(child->right!=NULL)) //确定需要删除的结点

    {
      if (child->balance == 1)
        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->left)
        if (parent->balance == 1)
        {
          parent->balance = 0;
          child = parent;
          parent = parent->parent;
        }
        else if (parent->balance == -1)
        {
          parent->balance = -2;
          child = parent->right;
          break;
        }
        else
        {
          parent->balance = -1;
          break;
        }
      else if (parent->balance == -1)
      {
        parent->balance = 0;
        child = parent;
        parent = parent->parent;
      }
      else if (parent->balance == 1)
      {
        parent->balance = 2;
        child = parent->left;
        break;
      }
      else
      {
        parent->balance = 1;
        break;
      }
    }
    if (dNode->parent != NULL)
      if (dNode == dNode->parent->left)
        dNode->parent->left = NULL;
      else dNode->parent->right = NULL;
    free(dNode);
    if (root == dNode)
      root = NULL; //root被删除, 避免野指针

    dNode = NULL;
    if ((parent==NULL) || (parent->balance==1) || (parent->balance==-1))
      return root;
    return adjustAVL(root, parent, child);
  }
}

node* createAVL(int *data, int size)
{
  int i, j;
  node *root;
  if (size<1)
    return NULL;
  root = (node*)malloc(sizeof(node));
  root->parent = NULL;
  root->left = NULL;
  root->right = NULL;
  root->key = data[0];
  root->balance = 0;
  
  for(i=1;i<size;i++)
    root = insertNode(data[i], root);
  return root;
}

void destroyAVL(node* root)
{
  if (root != NULL)
  {
    destroyAVL(root->left);
    destroyAVL(root->right);
    free(root);
    root=NULL;
  }
  
}

void traverseAVL1(node* root) //中序遍历

{
  if (root != NULL)
  {
    traverseAVL1(root->left);
    printf("%d, %d\n", root->key, root->balance);
    traverseAVL1(root->right);
  }
}

void traverseAVL2(node* root) //先序遍历

{
  if (root != NULL)
  {
    printf("%d, %d\n", root->key, root->balance);
    traverseAVL2(root->left);
    traverseAVL2(root->right);
  }
}

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

  printf("++++++++++++++++++++++++++++\n");
  traverseAVL1(root);
  printf("\n");
  traverseAVL2(root);
  
  root = deleteNode(5, root);
  printf("++++++++++++++++++++++++++++\n");
  traverseAVL1(root);
  printf("\n");
  traverseAVL2(root);

  root = deleteNode(3, root);
  printf("++++++++++++++++++++++++++++\n");
  traverseAVL1(root);
  printf("\n");
  traverseAVL2(root);

  root = deleteNode(1, root);
  printf("++++++++++++++++++++++++++++\n");
  traverseAVL1(root);
  printf("\n");
  traverseAVL2(root);

  root = deleteNode(7, root);
  printf("++++++++++++++++++++++++++++\n");
  traverseAVL1(root);
  printf("\n");
  traverseAVL2(root);

  root = deleteNode(4, root);
  printf("++++++++++++++++++++++++++++\n");
  traverseAVL1(root);
  printf("\n");
  traverseAVL2(root);

  root = deleteNode(2, root);
  printf("++++++++++++++++++++++++++++\n");
  traverseAVL1(root);
  printf("\n");
  traverseAVL2(root);

  destroyAVL(root);
}

阅读(4345) | 评论(1) | 转发(2) |
0

上一篇:linux softirq机制

下一篇:进程切换

给主人留下些什么吧!~~

lujian198619862011-11-04 17:08:36

很好