平衡二叉排序树C语言代码

平衡二叉排序树的C语言代码如下所示：

#include <stdio.h>
#include <stdlib.h>
typedef int DataType; /*平衡二叉排序树的类型定义*/

typedef struct node {
    DataType data;
    int bf; //结点的平衡因子
    struct node* lchild, * rchild;
} AVLNode, * AVLTree;

//左旋函数
void L_Rotate(AVLTree* T) {
    AVLNode* p = (*T)->rchild;
    (*T)->rchild = p->lchild;
    p->lchild = (*T);
    (*T)->bf = p->bf = 0;
    (*T) = p;
}

//右旋函数
void R_Rotate(AVLTree* T) {
    AVLNode* p = (*T)->lchild;
    (*T)->lchild = p->rchild;
    p->rchild = (*T);    (*T)->bf = p->bf = 0;
    (*T) = p;
}

//左平衡旋转处理
void LeftBalance(AVLTree* T) {
    AVLNode* p = (*T)->lchild;
    switch (p->bf) {
    case 1:
        R_Rotate(&(*T));
        break;
    case -1:
        L_Rotate(&(p));
        (*T)->lchild = p;
        R_Rotate(&(*T));
        break;
    }
}

//右平衡旋转处理
void RightBalance(AVLTree* T) {
    AVLNode* p = (*T)->rchild;
    switch (p->bf) {
    case -1:
        L_Rotate(&(*T));
        break;
    case 1:
        R_Rotate(&(p));
        (*T)->rchild = p;
        L_Rotate(&(*T));
        break;
    }
}

//插入结点
int InsertAVL(AVLTree* T, DataType x) {
    if (!(*T)) {
        (*T) = (AVLNode*)malloc(sizeof(AVLNode));
        (*T)->data = x;
        (*T)->bf = 0;
        (*T)->lchild = (*T)->rchild = NULL;
        return 1;
    }
    else {
        if (x == (*T)->data) {
            return 0;
        }
        else if (x < (*T)->data) {
            if (!InsertAVL(&((*T)->lchild), x)) {
                return 0;
            }
            switch ((*T)->bf) {
            case 1:
                LeftBalance(&(*T));
                return 0;
            case 0:
                (*T)->bf = 1;
                return 1;
            case -1:
                (*T)->bf = 0;
                return 0;
            }
        }
        else {
            if (!InsertAVL(&((*T)->rchild), x)) {
                return 0;
            }
            switch ((*T)->bf) {
            case -1:
                RightBalance(&(*T));
                return 0;
            case 0:
                (*T)->bf = -1;
                return 1;
            case 1:
                (*T)->bf = 0;
                return 0;
            }
        }
    }
}

//中序遍历
void InOrder(AVLTree T) {
    if (T) {
        InOrder(T->lchild);
        printf("%d ", T->data);
        InOrder(T->rchild);
    }
}

int main() {
    AVLTree T = NULL;
    int a[] = { 3,2,1,4,5,6,7,10,9,8 };
    int n = sizeof(a) / sizeof(int);
    for (int i = 0; i < n; i++) {
        InsertAVL(&T, a[i]);
    }
    InOrder(T);
    return 0;
}

以上代码实现了平衡二叉排序树的插入和中序遍历操作。