如何在C语言中用无返回值函数实现AVL树旋转后的子树根更新

必须遵循给定的void函数签名实现C语言AVL树，核心问题是：子树旋转后原节点不再是子树根，但旋转、平衡等函数均为void类型无法返回新根，导致调用者无法感知子树根的变化，进而破坏树结构。

相关代码细节 #

插入函数及递归辅助函数 #

/* 递归遍历树、创建节点、更新高度和平衡的辅助函数 */
Node* insertRecursive(Tree* tree, Node* root, Node* parent, int value) {
    
    /* 若子节点不存在则创建节点 */
    if(!root) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        [...]
        return newNode;
    }
    
    /* 递归遍历、更新高度、平衡处理 */
    [...]

    balance(tree, root);
    
    return root;
}

void insertValue(Tree *tree, int value) {
    tree->root = insertRecursive(tree, tree->root, NULL, value);
}

平衡函数 #

void balance(Tree* tree, Node* node) {

    /* 调用getHeight计算子树高度 */
    [...]

    /* 通过条件判断确定旋转方式 */
    [...]
    
    /* 旋转调用处存在问题：旋转后"node"应变为子树新根，类似有返回值时的node = rotateLeft(tree, node) */
    rotateLeft(tree, node);
}

左旋转函数实现 #

void rotateLeft(Tree* tree, Node* x) {
    Node *y = x->right;
    x->right = y->left;
    y->left = x;
    
    if(y->left)
        y->left->parent = x;
    
    y->parent = x->parent;
    
    if(tree->root == x) {
        tree->root = y;
    } else if(x == x->parent->left)
        x->parent->left = y;
    else x->parent->right = y;
    y->left = x;
    x->parent = y;
    
    x->height = 1 + max(getHeight(x->left), getHeight(x->right));
    y->height = 1 + max(getHeight(y->left), getHeight(y->right));
}

给定的函数签名 #

void leftRotate(Tree* tree, Node* x);
void rightRotate(Tree* tree, Node* y);
void balance(Tree* tree, Node* node);
void insertValue(Tree *tree, int value)

给定的结构体 #

struct Node {
    struct Node* left;
    struct Node* right;
    struct Node* parent;
    int value;
    int height;
};

struct Tree {
    struct Node* root;
    int numberOfNodes;
};

已尝试的无效方案 #

• 尝试传递指针的指针修改原始指针（如leftRotate(tree, &node)），编译报错
• 使用leftRotate(tree, &(*node))，编译通过但未解决问题
• 尝试临时变量Node tmp = node，旋转后赋值*node = *tmp，导致其他指针指向栈中临时变量，无效
• 旋转后将node指向其父节点node = node->parent，仅部分场景有效，无法确定是否发生旋转
• 使用临时Tree结构体，无法更新父节点，无效

解决方案 #

核心思路：利用旋转函数已经正确维护的父节点指针和树的根节点指针，在递归辅助函数中获取旋转后的子树根节点，而非依赖传入的原节点指针。

修改insertRecursive函数，在调用balance后，通过父节点或树的根节点获取当前子树的新根：

Node* insertRecursive(Tree* tree, Node* root, Node* parent, int value) {
    
    if(!root) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->left = NULL;
        newNode->right = NULL;
        newNode->parent = parent;
        newNode->value = value;
        newNode->height = 1;
        tree->numberOfNodes++;
        return newNode;
    }
    
    if (value < root->value) {
        root->left = insertRecursive(tree, root->left, root, value);
    } else if (value > root->value) {
        root->right = insertRecursive(tree, root->right, root, value);
    } else {
        // 重复值不插入
        return root;
    }
    
    // 更新当前节点高度
    root->height = 1 + max(getHeight(root->left), getHeight(root->right));
    
    balance(tree, root);
    
    // 获取旋转后的子树根节点
    Node* newRoot;
    if (parent == NULL) {
        // 当前处理的是整棵树的根，直接取tree的根
        newRoot = tree->root;
    } else if (parent->left == root) {
        // 原root是父节点的左孩子，旋转后父节点的左孩子已更新为新根
        newRoot = parent->left;
    } else {
        // 原root是父节点的右孩子，旋转后父节点的右孩子已更新为新根
        newRoot = parent->right;
    }
    
    return newRoot;
}

原理说明：

• 旋转函数rotateLeft/rotateRight已经正确修改了父节点的left/right指针（或树的root指针），保证了树结构的正确性
• 递归辅助函数通过父节点或树的根节点，直接读取已经更新后的子树根节点，返回给上层递归，避免了原节点指针失效的问题

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