AVL树删除操作后遍历结果异常的C程序问题求助

问题分析 #

你的AVL树程序插入功能正常，但删除操作后遍历结果不符合预期，核心原因是deleteNode函数中的平衡调整逻辑错误——处理右子树不平衡的两种情况（RR型、RL型）的判断条件被颠倒，导致删除后的树结构未按正确的AVL规则调整。

另外需要明确：你预期的中序遍历27 6 63 81是错误的，二叉搜索树的中序遍历必然是升序排列，正确的中序结果应为6 27 63 81，这和你的实际输出一致。

错误代码位置 #

在deleteNode函数的平衡调整部分，原代码错误地混淆了RR型和RL型的判断条件：

// 错误：将RR型条件写成了RL型处理逻辑
if(balance < -1 && getBalance(root->right) >= 0) {
    root->right = rightRotate(root->right);
    return leftRotate(root);
}

// 错误：将RL型条件写成了RR型处理逻辑
if(balance < -1 && getBalance(root->right) < 0)
    return leftRotate(root);

修正方案 #

AVL树删除后的右子树不平衡分为两种标准情况：

1. RR型：根节点平衡因子<-1，且右子节点平衡因子<=0（右子节点右重或平衡），直接左旋根节点。
2. RL型：根节点平衡因子<-1，且右子节点平衡因子>0（右子节点左重），先右旋右子节点，再左旋根节点。

修正后的平衡调整代码如下：

int balance = getBalance(root);

// LL型：左子节点左重或平衡，右旋根节点
if(balance > 1 && getBalance(root->left) >= 0)
    return rightRotate(root);

// LR型：左子节点右重，先左旋左子节点，再右旋根节点
if(balance > 1 && getBalance(root->left) < 0) {
    root->left = leftRotate(root->left);
    return rightRotate(root);
}

// RR型（修正后）：右子节点右重或平衡，左旋根节点
if(balance < -1 && getBalance(root->right) <= 0)
    return leftRotate(root);

// RL型（修正后）：右子节点左重，先右旋右子节点，再左旋根节点
if(balance < -1 && getBalance(root->right) > 0) {
    root->right = rightRotate(root->right);
    return leftRotate(root);
}

验证结果 #

修正后，按你的删除步骤（删除14、75、36、19、11），最终树结构会调整为以63为根的AVL树，遍历结果将符合你的预期：

• 前序遍历：63 6 27 81
• 中序遍历：6 27 63 81（正确升序）
• 后序遍历：27 6 81 63

完整修正后的deleteNode函数 #

struct Node* deleteNode(struct Node* 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)) {
            struct Node* temp = root->left ? root->left : root->right;

            if(temp == NULL){
                temp = root;
                root = NULL;
            } else 
                *root = *temp; 

            free(temp);
        } else{

            struct Node* temp = minValueNode(root->right);

            root->data = temp->data;

            root->right = deleteNode(root->right, temp->data);
            
        }
    }

    if(root == NULL)
        return root;

    root->height = 1 + max(height(root->left), height(root->right));

    int balance = getBalance(root);

    // LL型
    if(balance > 1 && getBalance(root->left) >= 0)
        return rightRotate(root);

    // LR型
    if(balance > 1 && getBalance(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // RR型（修正）
    if(balance < -1 && getBalance(root->right) <= 0)
        return leftRotate(root);

    // RL型（修正）
    if(balance < -1 && getBalance(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

内容的提问来源于stack exchange，提问作者CyberGhostZ