C语言AVL树通过左旋转转主干链时左旋转函数异常如何解决

现有左旋转函数的问题 #

• 旋转逻辑不完整：标准左旋操作需要将左孩子的右指针固定指向当前父节点，你的代码仅在左孩子无右子节点时才做该赋值，左孩子存在右子节点时直接断链，结构完全错误。
• 没有返回旋转后的新根节点：左旋后原父节点会变成左孩子的右子节点，子树的根会发生变化，你的函数返回void，无法将新的根向上传递，更无法更新整棵树的根节点。
• 递归顺序错误：你没有先递归处理左子树的所有左节点，直接旋转会导致左子树内部的左节点残留，无法形成完整的主干链。
• 根节点未更新：主函数调用left_rotate时直接传原根，旋转后原根已经不是整棵树的根，tree->root指针没有修改，会导致树结构丢失、打印异常。

修改方案 #

你要实现的是将BST转换为仅存在右子节点的递增右主干链，按如下修改即可：

1. 修改左旋转函数，支持返回新根，补全旋转逻辑 #

NODE left_rotate(NODE parent) {
    // 空节点或无左子节点，无需旋转，直接返回当前节点作为根
    if (parent == NULL || parent->left == NULL) {
        return parent;
    }
    // 先递归处理左子树，把左子树先全部转成右链
    NODE left_child = left_rotate(parent->left);
    // 执行标准左旋
    parent->left = left_child->right;
    left_child->right = parent;
    // 返回旋转后的新根（原左孩子）
    return left_child;
}

2. 修改主函数调用逻辑，更新树的根节点 #

把主函数中left_rotate(tree1->root);替换为：

tree1->root = left_rotate(tree1->root);

修改后运行打印，即可看到输出为从大到小缩进的递增右链，所有节点仅存在右子节点，符合主干链需求。

内容的提问来源于stack exchange，提问作者Koray Can Yılmaz