数据结构c语言版平衡二叉树

平衡二叉树是一种特殊的二叉搜索树，它的任意节点左子树和右子树的高度差不超过1。下面是一个使用C语言实现的平衡二叉树的例子：

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

// 定义二叉树的结构体
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    int height;
} Node;

// 计算节点的高度
int getHeight(Node* node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

// 更新节点的高度
void updateHeight(Node* node) {
    int leftHeight = getHeight(node->left);
    int rightHeight = getHeight(node->right);
    node->height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// 计算节点的平衡因子
int getBalanceFactor(Node* node) {
    return getHeight(node->left) - getHeight(node->right);
}

// 左旋转操作
Node* leftRotate(Node* node) {
    Node* temp = node->right;
    node->right = temp->left;
    temp->left = node;
    updateHeight(node);
    updateHeight(temp);
    return temp;
}

// 右旋转操作
Node* rightRotate(Node* node) {
    Node* temp = node->left;
    node->left = temp->right;
    temp->right = node;
    updateHeight(node);
    updateHeight(temp);
    return temp;
}

// 插入节点
Node* insertNode(Node* node, int data) {
    if (node == NULL) {
        node = (Node*)malloc(sizeof(Node));
        node->data = data;
        node->left = NULL;
        node->right = NULL;
        node->height = 1;
        return node;
    }
    if (data < node->data) {
        node->left = insertNode(node->left, data);
    } else if (data > node->data) {
        node->right = insertNode(node->right, data);
    }
    updateHeight(node);
    int balanceFactor = getBalanceFactor(node);
    if (balanceFactor > 1 && data < node->left->data) {
        // LL情况，进行右旋转
        return rightRotate(node);
    }
    if (balanceFactor < -1 && data > node->right->data) {
        // RR情况，进行左旋转
        return leftRotate(node);
    }
    if (balanceFactor > 1 && data > node->left->data) {
        // LR情况，先左旋转再右旋转
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    if (balanceFactor < -1 && data < node->right->data) {
        // RL情况，先右旋转再左旋转
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}

// 输出平衡二叉树
void printAVLTree(Node* node) {
    if (node == NULL) {
        return;
    }
    printf("%d ", node->data);
    printAVLTree(node->left);
    printAVLTree(node->right);
}

int main() {
    Node* root = NULL;

    root = insertNode(root, 10);
    root = insertNode(root, 20);
    root = insertNode(root, 30);
    root = insertNode(root, 40);
    root = insertNode(root, 50);
    root = insertNode(root, 25);

    printf("平衡二叉树的前序遍历结果为：");
    printAVLTree(root);

    return 0;
}

以上代码是一个平衡二叉树的C语言实现，主要包括计算节点高度、更新节点高度、计算平衡因子、左旋转、右旋转以及插入节点等操作。在使用时，可以通过调用`insertNode`函数插入节点，并通过`printAVLTree`函数输出平衡二叉树的前序遍历结果。