C语言AVL树节点添加递归函数触发段错误问题求助

问题描述 #

作业要求实现一棵AVL树，支持以广度优先方式输出节点值，后续需要构建包含10000个节点的树。但当前AVLnodeAdd递归函数存在逻辑问题，每次运行都会触发段错误。尝试过修改终止条件（比如判断current->val = 0、(current->left == NULL) && (current->right == NULL)等），但都没能解决问题，需要实现正确的空节点查找与插入逻辑。

现有代码 #

avl.c

/* add newValue to subtree of current node */
struct AVLnode * AVLnodeAdd(struct  AVLnode * current, TYPE newValue)
{
    if ((current == 0)) {
        struct AVLnode *newNode = (struct AVLnode *)malloc(sizeof(struct AVLnode));
        newNode->val = newValue;
        setHeight(newNode);
        return newNode;
    }
    else {
        current->left = AVLnodeAdd(current->left, newValue);
        current->right = AVLnodeAdd(current->right, newValue);
    }
    return _balance(current);
}

avl.h

struct AVLnode {
    TYPE         val;
    struct AVLnode *left;
    struct AVLnode *right;
    int height;
};


struct AVLTree {
    struct AVLnode *root;
    int          cnt;
};

问题根源 #

原函数的核心错误在于：每次递归都会同时对左、右子树调用插入函数。这会导致无限递归——只要当前节点不为空，就会不断向左右子树插入新节点，递归深度指数级增长，最终耗尽栈空间触发段错误。AVL树的插入逻辑应该是根据节点值的大小，选择左或右其中一条路径递归查找空位置，而非同时遍历左右。

修复后的代码 #

/* add newValue to subtree of current node */
struct AVLnode * AVLnodeAdd(struct  AVLnode * current, TYPE newValue)
{
    // 找到空节点，创建新节点返回
    if (current == NULL) {
        struct AVLnode *newNode = (struct AVLnode *)malloc(sizeof(struct AVLnode));
        newNode->val = newValue;
        newNode->left = NULL;  // 必须初始化左右子节点为NULL
        newNode->right = NULL;
        setHeight(newNode);
        return newNode;
    }

    // 根据值的大小选择插入左或右子树
    if (newValue < current->val) {
        current->left = AVLnodeAdd(current->left, newValue);
    } else if (newValue > current->val) {
        current->right = AVLnodeAdd(current->right, newValue);
    } else {
        // 若值已存在，无需插入（根据需求调整，这里假设不允许重复值）
        return current;
    }

    // 更新当前节点高度，然后平衡
    setHeight(current);
    return _balance(current);
}

关键修改点 #

1. 插入路径选择：通过比较newValue和current->val，决定插入左子树还是右子树，避免同时递归左右导致无限调用。
2. 初始化新节点：明确设置新节点的left和right为NULL，防止后续递归时访问野指针。
3. 重复值处理：增加重复值判断，避免重复插入（可根据实际需求调整逻辑）。
4. 高度更新时机：插入后先更新当前节点的高度，再执行平衡操作，保证平衡逻辑基于最新高度。

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