c++ - 在树结构中搜索数据

Question

能否请您推荐一种有效(快速)的树状结构数据搜索算法，如下所示:

struct Node
{
    std::string value;

    Node* parent;
    std::vector<Node*> childs;
}

目标是找到 Node.value 与搜索模式匹配的所有节点。 谢谢

Answer 1

一个简单的前序遍历:

void match(Node * node, const std::string & value, std::vector<Node*> & result)
{
    if (node->value == value)
    {
        result.push_back(node);
    }
    for (Node * child : node->childs)
    {
        match(child, value, result);
    }
}

int main()
{
    Node * root = /* ... */
    std::string value = /* ... */;
    std::vector<Node*> matches;
    match(root, value, matches);
}

归纳为

template<typename Action>
void preorder(Node * node, Action action)
{
    action(node);
    for (Node * child : node->childs)
    {
        preorder(child, action);
    }
}

int main()
{
    Node * root = /* ... */
    std::string value = /* ... */;
    std::vector<Node*> matches;
    preorder(root, [&](Node * node){ if (node->value == value) { matches->push_back(node); } });
}