首页 文章

C实现中的多路树搜索算法

提问于
浏览 次
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将搜索树并返回指向特定节点的指针 . 我试图像上面那样递归地做，没有太多运气 . 实际上可以递归地构建这个算法还是我还需要使用堆栈？

c search tree multiway-tree

2 回答

  • 0

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

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

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

    回复于
  • 1

    实际上是否可以递归地构建此算法？

    是的，可以使用递归来完成此操作 .

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

    • if (id == p->_child[i]->_id)... 的第一部分是完全冗余的，因为它复制了递归调用将要执行的操作（并且无法检查子项是否为 NULL ） .

    • 当函数递归调用自身时，将忽略返回值 . 您需要弄清楚如何处理该返回值 .

    回复于

相关问题