• 如果您觉得本站非常有看点，那么赶紧使用Ctrl+D 收藏吧

# 数据结构与算法 ：AVL平衡二叉树C语言实现

2周前 (11-19) 8次浏览

C语言实现AVL平衡二叉树

##### 1结构体
``````//这里定义一个取较大值的MAX宏
#define MAX(a,b) ((a)>(b)?(a):(b))

typedef struct AVLTreeNode {
int data; //数据域
int height; //数据域
struct AVLTreeNode *left; //左子结点
struct AVLTreeNode *right; //右子结点
} AVLTreeNode;
``````
##### 2.1右单旋
``````/**
* 右单旋
*          8                  4
*       4     12           2     8
*    2    6         =>  1      6   12
* 1
*/
AVLTreeNode *right_rotation(AVLTreeNode *root)
{
struct AVLTreeNode *new_root;
new_root         = root->left;
root->left       = new_root->right;
new_root->right  = root;
//旋转完重新计算高度
root->height     = MAX(Height(root->left) + 1, Height(root->right));
new_root->height = MAX(Height(new_root->left) + 1, Height(new_root->right));
return new_root;
}``````
##### 2.2左单旋
``````/**
* 左单旋
*          8                         12
*       4     12                  8     50
*           9    50      =>    4    9      70
*                   70
*/
AVLTreeNode *left_rotation(AVLTreeNode *root)
{
struct AVLTreeNode *new_root;
new_root         = root->right;
root->right      = new_root->left;
new_root->left   = root;
//旋转完重新计算高度
root->height     = MAX(Height(root->right) + 1, Height(root->left));
new_root->height = MAX(Height(new_root->right) + 1, Height(new_root->left));
return new_root;
}``````
##### 2.3左右旋
``````/**
* 左右旋 先对root->left左旋 再对root右旋
*           8                         8                     6
*       4      12                  6     12             4       8
*    2     6            =>      4              =>    2     5       12
*        5                   2    5
*/
AVLTreeNode *left_right_rotation(AVLTreeNode *root){
root->left = left_rotation(root->left);
return right_rotation(root);
}``````
##### 2.3右左旋
``````/**
* 右左旋 先对root->right右旋 再对root左旋
*           8                         8                       10
*       4      12                  4     10                8     12
*           10    14      =>           9    12       =>  4   9       14
*         9                                    14
*/
AVLTreeNode *right_left_rotation(AVLTreeNode *root){
root->right = right_rotation(root->right);
return left_rotation(root);
}``````
##### 3 自平衡
``````AVLTreeNode *rebalance(AVLTreeNode *root, int data)
{
if (Height(root->right) - Height(root->left) == 2)
{
if (data > root->right->data)//左单旋的情况
{
printf("left_rotation n");
root = left_rotation(root);
}else{
printf("right_left_rotation n");//右左旋的情况
root = right_left_rotation(root);
}
}
if (Height(root->left) - Height(root->right) == 2)
{
if (data < root->left->data)//右单旋的情况
{
printf("right_rotation n");
root = right_rotation(root);
}else{
printf("left_right_rotation n");//左右旋的情况
root = left_right_rotation(root);
}
}
return root;
}``````
##### 4 插入
``````AVLTreeNode *insert(AVLTreeNode *root, int data)
{
if (NULL == root)
{
struct AVLTreeNode *node;
node = (struct AVLTreeNode *)malloc(sizeof(struct AVLTreeNode));
if (node == NULL)
{
printf("malloc error n");
return NULL;
}
node->data  = data;
node->right = NULL;
node->left  = NULL;
return node;
}

if (data >= root->data)
{
root->right  = insert(root->right, data);
root->height = MAX(Height(root->left), Height(root->right) + 1);//相比于二叉搜索树多了高度判断
}else{
root->left   = insert(root->left, data);
root->height = MAX(Height(root->left) + 1, Height(root->right));
}
root = rebalance(root, data);
return root;
}``````
##### 5.1 查找最大/小节点
``````AVLTreeNode *FindMin(AVLTreeNode *root)
{
if (NULL == root)
{
return NULL;
}
if (root->left == NULL)
{
return root;
}else{
return FindMin(root->left);
}
}
AVLTreeNode *FindMax(AVLTreeNode *root)
{
if (NULL == root)
{
return NULL;
}
if (root->right == NULL)
{
return root;
}else{
return FindMax(root->right);
}
}``````
##### 5.2删除
``````AVLTreeNode *Delete(AVLTreeNode *root, int target)
{
if (NULL == root)
{
return NULL;
}
if (target > root->data)
{
root->right = Delete(root->right, target);
if (Height(root->left) - Height(root->right) == 2)
{
AVLTreeNode *l =  root->left;
if (Height(l->right) > Height(l->left))
root = left_right_rotation(root);
else
root = left_rotation(root);
}
}else if(target < root->data){
root->left  = Delete(root->left, target);
if (Height(root->right) - Height(root->left) == 2)
{
AVLTreeNode *r =  root->right;
if (Height(r->left) > Height(r->right))
root = left_right_rotation(root);
else
root = right_rotation(root);
}
}else{
//相等的情况
if (root->left && root->right)
{
if (Height(root->left) > Height(root->right))
{
//左子树比右子树高
AVLTreeNode *max = FindMax(root->left);
root->data = max->data;
root->left = Delete(root->left, max->data);
}else{
AVLTreeNode *min = FindMin(root->right);
root->data = min->data;
root->right = Delete(root->right, min->data);
}
}else{
struct AVLTreeNode *tmp;
tmp = root;
if (root->left == NULL)
{
root = root->right;
}else if(root->right == NULL){
root = root->left;
}else{
root = NULL;//删除自身
}
}
}
return root;
}``````

``````int main()
{
struct AVLTreeNode *node;
node = NULL;
node = insert(node, 8);
node = insert(node, 4);
node = insert(node, 12);
node = insert(node, 10);
node = insert(node, 14);
node = insert(node, 9);
printf("***前序***:  n");
preOrderTraverse(node);
node = Delete(node, 10);
printf("***前序***:  n");
preOrderTraverse(node);
}``````