AVL树代码报错Declaration is incompatible with void如何解决？

核心报错原因 #

declaration is incompatible with void报错的直接诱因是：你声明函数返回值为void类型，但函数内部存在带具体返回值的return语句，二者类型冲突。

所有问题汇总 #

• 函数返回值与return语句不匹配：rightRotate、leftRotate、insert三个函数均声明为void返回，但内部均返回了AvlNode*类型的指针，和声明冲突。
• 成员函数const修饰错误：三个函数都会修改AVL树的节点结构，不应该加const修饰，const成员函数不允许修改类的成员状态。
• 变量类型定义缺失：leftRotate函数中AvlNode x2 = y->left;漏写指针标记*，正确写法为AvlNode *x2 = y->left;。
• 未定义变量引用：insert函数中使用的node、key均未在作用域内定义，应该使用传入的参数做逻辑判断。
• 函数调用与语法错误：insert递归调用时参数顺序和定义不符，且语句末尾缺少分号。
• 高度更新逻辑错误：leftRotate中高度更新顺序错误，应该先更新原根节点的高度，再更新新根节点的高度，当前代码的高度计算引用对象也存在混淆。

修复后代码示例 #

// 右旋函数，返回旋转后的新根节点
template <typename Comparable>
typename AvlTree<Comparable>::AvlNode* AvlTree<Comparable>::rightRotate(AvlNode *y)
{
    AvlNode *x = y->left;
    AvlNode *x2 = x->right;

    x->right = y;
    y->left = x2;

    // 先更新原根y的高度，再更新新根x的高度
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

// 左旋函数，返回旋转后的新根节点
template <typename Comparable>
typename AvlTree<Comparable>::AvlNode* AvlTree<Comparable>::leftRotate(AvlNode *x)
{
    AvlNode* y = x->right;
    AvlNode *x2 = y->left;

    y->left = x;
    x->right = x2;

    // 先更新原根x的高度，再更新新根y的高度
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

// 插入函数，返回插入后的新根节点
template <typename Comparable>
typename AvlTree<Comparable>::AvlNode* AvlTree<Comparable>::insert(const Comparable &val, AvlNode *t)
{
    if(t == nullptr){
        // 此处newNode需要你自己实现返回新节点的逻辑
        return newNode(val);
    }

    if(val < t->key){
        t->left = insert(val, t->left);
    } else if (val > t->key) {
        t->right = insert(val, t->right);
    } else {
        // 重复值不插入，直接返回
        return t;
    }

    // 后续可自行补充高度更新、平衡因子判断、旋转逻辑
    return t;
}

如果你要保留指针引用参数的写法，不需要返回值，直接删掉return语句，通过引用修改指向的节点即可，同样可以解决类型不匹配的报错。

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