平衡二叉树的构造c语言,数据结构之---C语言实现平衡二叉树（AVL树）

平衡二叉树是一种特殊的二叉树，它的左右子树的高度差不超过1。AVL树是一种自平衡的二叉搜索树，它的高度始终保持在O(log n)。

下面是C语言实现平衡二叉树（AVL树）的代码：

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

/* 定义平衡二叉树节点结构体 */
struct AVLNode {
    int data;                   // 存储的数据
    int height;                 // 节点高度
    struct AVLNode *leftChild;  // 左子树
    struct AVLNode *rightChild; // 右子树
};

/* 获取节点高度 */
int getHeight(struct AVLNode *node) {
    if (node == NULL) {
        return -1;
    } else {
        return node->height;
    }
}

/* 获取节点平衡因子 */
int getBalanceFactor(struct AVLNode *node) {
    if (node == NULL) {
        return 0;
    } else {
        return getHeight(node->leftChild) - getHeight(node->rightChild);
    }
}

/* 更新节点高度 */
void updateHeight(struct AVLNode *node) {
    node->height = 1 + (getHeight(node->leftChild) > getHeight(node->rightChild) ? getHeight(node->leftChild) : getHeight(node->rightChild));
}

/* 右旋操作 */
struct AVLNode *rotateRight(struct AVLNode *node) {
    struct AVLNode *newRoot = node->leftChild;
    node->leftChild = newRoot->rightChild;
    newRoot->rightChild = node;
    updateHeight(node);
    updateHeight(newRoot);
    return newRoot;
}

/* 左旋操作 */
struct AVLNode *rotateLeft(struct AVLNode *node) {
    struct AVLNode *newRoot = node->rightChild;
    node->rightChild = newRoot->leftChild;
    newRoot->leftChild = node;
    updateHeight(node);
    updateHeight(newRoot);
    return newRoot;
}

/* 插入操作 */
struct AVLNode *insert(struct AVLNode *root, int data) {
    if (root == NULL) {
        root = (struct AVLNode *) malloc(sizeof(struct AVLNode));
        root->data = data;
        root->height = 0;
        root->leftChild = NULL;
        root->rightChild = NULL;
    } else if (data < root->data) {
        root->leftChild = insert(root->leftChild, data);
        if (getHeight(root->leftChild) - getHeight(root->rightChild) == 2) {
            if (data < root->leftChild->data) {
                root = rotateRight(root);
            } else {
                root->leftChild = rotateLeft(root->leftChild);
                root = rotateRight(root);
            }
        }
    } else if (data > root->data) {
        root->rightChild = insert(root->rightChild, data);
        if (getHeight(root->rightChild) - getHeight(root->leftChild) == 2) {
            if (data > root->rightChild->data) {
                root = rotateLeft(root);
            } else {
                root->rightChild = rotateRight(root->rightChild);
                root = rotateLeft(root);
            }
        }
    }
    updateHeight(root);
    return root;
}

/* 中序遍历 */
void inOrderTraversal(struct AVLNode *root) {
    if (root != NULL) {
        inOrderTraversal(root->leftChild);
        printf("%d ", root->data);
        inOrderTraversal(root->rightChild);
    }
}

int main() {
    struct AVLNode *root = NULL;
    int data[] = {5, 2, 8, 1, 3, 6, 9};
    int len = sizeof(data) / sizeof(data[0]);
    int i;
    for (i = 0; i < len; i++) {
        root = insert(root, data[i]);
    }
    inOrderTraversal(root);
    return 0;
}

以上代码实现了平衡二叉树的插入和中序遍历操作。在插入操作中，根据插入节点的值和当前节点的值的大小关系，不断递归向左或向右子树进行插入操作，并在递归返回时更新节点高度和进行平衡操作。在平衡操作中，根据节点的平衡因子进行旋转操作，使树重新平衡。在中序遍历操作中，按照左子树、根节点、右子树的顺序遍历树中的节点，输出节点的值。