二叉平衡树（AVL）-C语言

#include <stdio.h>
#include <stdlib.h>

#define max(a,b) (a>=b?a:b)
#define min(a,d) (a<b?a:b)
#define N     //数组长度

/* 二叉平衡树AVL */
typedef int Elemtype;
typedef struct AVLNode
{
    Elemtype data;
    struct AVLNode *lchild, *rchild;
    int height;
}AVLNode,*PNode;

//获取结点高度
int height(PNode p)
{
    return p == NULL ? - : p->height;
 } 

//单左旋转
PNode LeftRotate(PNode k2)
{
    PNode k1 = k2->lchild;
    k2->lchild = k1->rchild;
    k1->rchild = k2;
    k2->height = max(height(k2->lchild),height(k2->rchild)) + ;
    k1->height = max(height(k1->lchild),k2->height) + ;
    return k1;
 } 

//单右旋转
PNode RightRotate(PNode k2)
 {
    PNode k1 = k2->rchild;
    k2->rchild = k1->lchild;
    k1->lchild = k2;
    k2->height = max(height(k2->lchild),height(k2->rchild)) + ;
    k1->height = max(height(k1->lchild),k2->height) + ;
    return k1;
  } 

//右左旋转
PNode doubleLeftRotate(PNode k3)
{
    k3->lchild =RightRotate(k3->lchild);
      return LeftRotate(k3); 
} 
//左右旋转
PNode doubleRightRotate(PNode k3)
{
    k3->rchild =LeftRotate(k3->rchild);
      return RightRotate(k3); 
} 
//  AVL树插入结点
PNode insertAVL(PNode root,Elemtype data)
{
    if(root == NULL)
    {
        root = (PNode)malloc(sizeof(AVLNode));
        root->data = data;
        root->lchild = NULL;
        root->rchild = NULL;
        printf("%d 插入AVL树\n",data);
        return root;
    }   

    if(data < root->data)
    {
        root->lchild = insertAVL(root->lchild,data);
        if(height(root->lchild)-height(root->rchild) == )
        {
            if(data < root->lchild->data)
                root = LeftRotate(root);
            else
                root = doubleLeftRotate(root);
        }
    }
    else if(data > root->data)
    {
        root->rchild = insertAVL(root->rchild,data);
        if(height(root->rchild)-height(root->lchild) == )
            if(data > root->rchild->data)
                root = RightRotate(root);
            else
                root = doubleRightRotate(root);
    }
    else
        printf("%d 已在树中\n");

    root->height = max(height(root->lchild),height(root->rchild)) + ;
    return root;
} 

//中序遍历打印AVL树
void print(PNode root)
{
    if(root!=NULL)
    {
        print(root->lchild);
        printf("%d ",root->data);
        print(root->rchild);
    }
}

int main(int argc, char *argv[]) {
    PNode root = NULL;
    int data[N] = {1,2,3,4,1,6,7};
    int i;
    for(i =0;i<N;i++)
        root = insertAVL(root,data[i]);
    print(root);
    return 0;
}