平衡二叉树C语言代码的操作演示

好的，下面我将为您演示平衡二叉树的C语言代码，包括插入、查找、删除操作。

首先，我们定义一个平衡二叉树节点的结构体：

typedef struct AVLNode {
    int data;
    struct AVLNode *left;
    struct AVLNode *right;
    int height;
} AVLNode;

其中，data 存储节点的值，left 和 right 分别指向左右子树，height 存储节点的高度。

接下来，我们定义一些操作函数。首先是插入操作：

AVLNode* insertNode(AVLNode *root, int data) {
    if (root == NULL) {
        // 创建一个新节点
        AVLNode *newNode = (AVLNode*)malloc(sizeof(AVLNode));
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        newNode->height = 0;
        return newNode;
    }
    
    if (data < root->data) {
        // 插入到左子树
        root->left = insertNode(root->left, data);
    } else {
        // 插入到右子树
        root->right = insertNode(root->right, data);
    }
    
    // 更新节点高度
    root->height = 1 + max(getHeight(root->left), getHeight(root->right));
    
    // 检查是否需要平衡
    int balance = getBalance(root);
    if (balance > 1 && data < root->left->data) {
        // 左-左情况，进行右旋转
        return rightRotate(root);
    }
    if (balance > 1 && data > root->left->data) {
        // 左-右情况，进行左旋转后再右旋转
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    if (balance < -1 && data > root->right->data) {
        // 右-右情况，进行左旋转
        return leftRotate(root);
    }
    if (balance < -1 && data < root->right->data) {
        // 右-左情况，进行右旋转后再左旋转
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    
    return root;
}

insertNode 函数用于插入一个新节点。如果根节点为空，则直接创建一个新节点；否则，根据节点值的大小，插入到左子树或右子树中。然后，更新节点高度，检查是否需要进行平衡调整。如果发现不平衡，根据四种情况进行旋转操作，使树重新平衡。

接下来是查找操作：

AVLNode* searchNode(AVLNode *root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    
    if (data < root->data) {
        // 在左子树中查找
        return searchNode(root->left, data);
    } else {
        // 在右子树中查找
        return searchNode(root->right, data);
    }
}

searchNode 函数用于查找一个节点。如果根节点为空或者节点值等于要查找的值，则返回根节点。否则，根据节点值的大小，在左子树或右子树中递归查找。

最后是删除操作：

AVLNode* deleteNode(AVLNode *root, int data) {
    if (root == NULL) {
        return root;
    }
    
    if (data < root->data) {
        // 在左子树中删除
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        // 在右子树中删除
        root->right = deleteNode(root->right, data);
    } else {
        // 找到要删除的节点
        if (root->left == NULL || root->right == NULL) {
            // 只有一个子树或没有子树
            AVLNode *temp = root->left ? root->left : root->right;
            if (temp == NULL) {
                // 没有子树
                temp = root;
                root = NULL;
            } else {
                // 只有一个子树
                *root = *temp;
            }
            free(temp);
        } else {
            // 有两个子树，找到后继节点
            AVLNode *temp = getSuccessor(root->right);
            root->data = temp->data;
            root->right = deleteNode(root->right, temp->data);
        }
    }
    
    if (root == NULL) {
        return root;
    }
    
    // 更新节点高度
    root->height = 1 + max(getHeight(root->left), getHeight(root->right));
    
    // 检查是否需要平衡
    int balance = getBalance(root);
    if (balance > 1 && getBalance(root->left) >= 0) {
        // 左-左情况，进行右旋转
        return rightRotate(root);
    }
    if (balance > 1 && getBalance(root->left) < 0) {
        // 左-右情况，进行左旋转后再右旋转
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    if (balance < -1 && getBalance(root->right) <= 0) {
        // 右-右情况，进行左旋转
        return leftRotate(root);
    }
    if (balance < -1 && getBalance(root->right) > 0) {
        // 右-左情况，进行右旋转后再左旋转
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    
    return root;
}

deleteNode 函数用于删除一个节点。首先，根据节点值的大小，在左子树或右子树中递归查找要删除的节点。如果找到了要删除的节点，则分三种情况进行处理：如果节点只有一个子树或没有子树，则直接删除该节点；如果节点有两个子树，则找到它的后继节点，将后继节点的值复制到要删除的节点上，然后再删除后继节点。

删除后，更新节点高度，检查是否需要进行平衡调整。如果发现不平衡，根据四种情况进行旋转操作，使树重新平衡。

至此，我们就完成了平衡二叉树的C语言代码演示。希望对您有所帮助！