0

另一个递归问题，对不起，我无法理解这一点。我试图返回一个节点指针，其 id 与提供的 id 匹配。我想我正在正确地遍历树。有什么想法我在这里出错了吗？

//h
Node* findNode(const QString &id, Node *node=NULL)

//cpp
Node* Tree::findNode(const QString &id, Node *node)
{
    if (node == NULL)
        node = root;

    for(int i = 0, end = node ? node->childCount() : -1; i < end ; i++)
    {
        QString nodeId = node->child(i)->id();

        if (nodeId == id)
        {
            return node;
        }
        else
        {
            return findNode(id, node->child(i));
        }
    }
}

感谢您的关注

4

4 回答 4

4

在 中else，仅在找到某些内容时才返回递归调用的值。否则，你永远过不去i=0

于 2013-07-27T09:02:12.760 回答
3

我很确定你需要类似的东西：

 ...
 else
 {
     Node *temp = findNode(id, node->child(i));
     if (temp) return temp;
 }

事实上，它在到达循环结束之前就返回了。

此外，您需要在函数结束时返回NULL（或者更好的是）：nullptr

// At the end
return NULL;
于 2013-07-27T09:02:36.627 回答
1 
else return findNode(id, node->child(i));`

这将导致仅遍历第一个子树（子树）。

我宁愿写这样的东西，以便按顺序遍历所有子树，直到找到东西。如果没有找到，返回nullptr：

Node *find(Node *tree, string id)
{
    if (tree->id == id)
        return tree;

    Node *ptr = nullptr;
    for (int i = 0; i < tree->childCount; i++)
        if ((ptr = find(node->children[i], id)) != nullptr)
            return ptr;

    return nullptr;
}
于 2013-07-27T09:03:53.077 回答
0

您似乎只进行深度优先搜索，并返回最左侧叶节点的结果。

在 findNode(id, node->child(i)); 你永远不会检查这是否返回 NULL。

如果子节点的返回值不是 NULL（您实际上找到了一些东西），则仅从那里返回，否则，继续循环（现在，您只查看第一个元素）。

然后，在循环之后，如果没有找到任何东西（还没有返回），则返回 NULL。

于 2013-07-27T09:06:25.097 回答