2 
typedef struct dt {
    .....;
} Data;

typedef struct nd {
    int id;
    Data *data;
    struct tm *_parent;
    struct tm *_child[7];
} Node; 


Node* findNode(int id, Node *tree) {
    Node *p = tree;
    if (id == p->_id)
        return p;
    for (int i = 0; i < 7; i++) {
        if (id == p->_child[i]->_id) {
            p = p->_child[i];
            break;
        } else if(p->_child[i] != NULL) {
            findNode(id, p->_child[i]);
        }
    }

    return p;
}

我有一个多路树，每个节点都包含 0-7 个子节点。可以不按特定顺序添加和删除子项。我正在尝试构建一个搜索算法，给定一个 id 将搜索树并返回一个指向特定节点的指针。我已经尝试像上面那样递归地做它，但没有太多运气。实际上可以递归地构建这个算法还是我还需要使用堆栈？

4

2 回答 2

1

实际上可以递归地构建这个算法吗？

是的，可以使用递归来做到这一点。

你在正确的轨道上。该代码只需要几个修复：

  1. 的第一部分if (id == p->_child[i]->_id)...是完全多余的，因为它复制了递归调用无论如何都会做的事情（并且无法检查孩子是否是NULL）。
  2. 当函数递归调用自身时，返回值被忽略。您需要弄清楚如何处理该返回值。
于 2012-11-23T14:11:28.083 回答
0

您的最终条件存在一些问题。如果循环没有找到id，则必须通过返回值可以检测到。在这种情况下将其设为 NULL 是明智的。这可以通过进行两个更改来完成：而不是设置 p 并执行 break，而是直接返回它（这样 for 循环只会在找不到 id 时完成），并将最后的 return p 更改为 return NULL。

然后在进行递归调用时，需要检查返回值。如果为 NULL，则继续。否则退回。

前面的答案是正确的，也可以更好地删除对子 ID 的检查，特别是因为它需要（但不）检查 NULL。

于 2012-11-23T14:12:48.647 回答