-3

首先，我对 C 或 C++ 并不陌生。但是，我目前正在 Mac Yosemite 上使用 C++。我只是想编写一个递归函数来返回两个节点的共同祖先，它们由它们的键（数据）变量标识。逻辑很简单，遍历树，直到两个节点都在同一个分支中，这些节点发散的节点就是共同的祖先。带着这个想法，我想出了以下代码：

Node * commonAncestor(Node *n, int left_elem, int right_elem)
{
    if (n == NULL || n->key()==left_elem || n->key() == right_elem){return NULL;}
    if (left_elem < n->key() && right_elem > n->key()) {return n;}
    if (left_elem > n->key() || right_elem < n->key()) {
        cout<<"\n...Consider changing the order of the elements"<<endl;
    }
    if (left_elem < n->key() && right_elem < n->key()) {
        commonAncestor(n->Left(), left_elem, right_elem);
    }
    if (left_elem > n->key() && right_elem > n->key()) {
        commonAncestor(n->Right(), left_elem, right_elem);
    }
}

我应该工作，我做过类似的程序。但是，该程序无法编译。我收到编译器错误"control may reach end of non-void function" 这很奇怪，因为我有返回语句。另外，为了避免这个错误，我尝试在最后添加一个 return 语句，它只返回根节点。我很困惑......我应该对 XCode 设置做些什么吗？我的逻辑错了吗？

4

3 回答 3

1

那是因为您忘记返回递归调用返回的值。并且还在末尾添加一个 return NULL，因为编译器不一定知道函数的末尾是不可达的。

Node * commonAncestor(Node *n, int left_elem, int right_elem)
{
    if (n == NULL || n->key()==left_elem || n->key() == right_elem){return NULL;}
    if (left_elem < n->key() && right_elem > n->key()) {return n;}
    if (left_elem > n->key() || right_elem < n->key()) {
        cout<<"\n...Consider changing the order of the elements"<<endl;
        return NULL;
    }
    if (left_elem < n->key() && right_elem < n->key()) {
        return commonAncestor(n->Left(), left_elem, right_elem);
    }
    if (left_elem > n->key() && right_elem > n->key()) {
        return commonAncestor(n->Right(), left_elem, right_elem);
    }

    return NULL;
}
于 2015-01-21T02:50:10.227 回答
0

这是因为返回总是在 IF 语句中，所以它们不能被调用......所以如果它确实进入任何 IF （使用 NULL 或你想要的值），解决方案也应该在函数的末尾调用 return。

于 2015-01-21T02:49:59.820 回答
0

除非确定无论如何都会返回某些内容，否则编译器将不会高兴（即使您的 if 处理了所有可能的情况。最后，您认为您的代码永远不会到达，只需抛出 areturn NULL;它将是快乐的。

另外，我可能是错的，但我相信您还想在最后两个 if 中返回递归调用 commonAncestor 的结果。

于 2015-01-21T02:51:29.827 回答