Эффективный алгоритм для поиска дерева и возврата подмножества дерева, включая результаты

Question

У меня есть дерево, в котором у каждого узла есть имя. Я хочу выполнить поиск по именам узлов и вернуть подмножество дерева, которое содержит только найденные узлы и их родителей.

Кто-нибудь знает эффективный алгоритм для этой проблемы? Я много искал, но нашел только алгоритмы, которые возвращают только узел, но не узел со всеми его родителями.

---

Вот пример. Я хочу найти "CAT", и дерево выглядит так:

• CAT
  • собака
    • fi sh
  • хомяк
• хомяк
  • CAT
  • собака
    • Fi sh
• собака
  • рыба
    • кошка
    • хомяк
  • единорог

---

Результат должен выглядеть следующим образом:

• CAT
• хомяк
  • CAT
• собака
  • рыба
    • CAT

Answer 1

Пожалуйста, извините, если вы не можете прочитать код на С ++.

Во-первых, мы определяем класс Узел

class Node{
    string Name;
    vector<Node*>sons;
};

Теперь мы делаем глубину -поиск:

Node* dfs(Node*root){
    Node* result = nullptr;
    for(auto son:root->sons){
        auto subTree = dfs(son);
        if(subTree != nullptr){
            if(result == nullptr){
                result = new Node();
                result->Name = root->Name;
            }
            result->sons.push_back(subTree);
        }
    }
    return result;
}