Javascript алгоритм поиска дерева, который возвращает подмножество дерева, которое содержит найденный термин и его родителей

Question

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

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

Вот пример. когда пользователь вводит поисковый запрос, пример «Слон» и дерево выглядит следующим образом:

• Слон
  • Хомяк
    • Fi sh
  • Утка
• Хомяк
  • собака
    • Fi sh
  • Слон
    • Fi sh
• Собака
  • Fi sh
    • Единорог
      • Слон
    • Слон
    • Хомяк
  • Единорог
• Слон
  • Хомяк
    • Fi sh
    • Слон
    • Слон
  • Слон

---

Хотел бы вывести результат поиска в древовидном формате с детьми, как это:

• Слон
• Хомяк
  • Слон
• Собака
  • Fi sh
    • Единорог
      • Слон
    • Слон
• Слон
  • Хомяк
    • Слон
    • Слон
  • Слон

Дано:

this.tree =[
 {childs: Array(2), id: 2, name: "Elephant",  …}
 {childs: Array(2), id: 3, name: "Hamster", ...}
 {childs: Array(2), id: 3, name: "Dog", ...}
 {childs: Array(2), id: 3, name: "Elephant", ...}
]

Дано

//  animal target name
target = 'Elephant',

//  tree data structure
tree = [
    { name: 'Elephant', childs: [
        { name: 'Duck' },
        { name: 'Hamster', childs: [
            { name: 'Fish' }
        ]}
    ]},
    { name: 'Hamster', childs: [
        { name: 'Elephant', childs: [
            { name: 'Fish' }
        ]},
        { name: 'Dog', childs: [
            { name: 'Fish' }
        ]}
    ]},
    { name: 'Dog', childs: [
        { name: 'Unicorn' },
        { name: 'Fish', childs: [
            { name: 'Hamster' },
            { name: 'Unicorn', childs: [
                { name: 'Elephant' }
            ]},
        ]}
    ]},
    { name: 'Elephant', childs: [
        { name: 'Duck' },
        { name: 'Hamster', childs: [
            { name: 'Elephant' },
            { name: 'Fish' },
        ]}
    ]}
],

Попытка изменить дерево из решения Нева (результат вывода в исходном формате объекта дерева, установить свойство для display = false, чтобы скрыть узел, продолжить поиск другого узла на том же уровне, даже если найден соответствующий узел). Это похоже на DFS, однако я все еще трачу много времени, чтобы разобраться в возврате. Окончательный результат - вернуть дерево, которое содержит только совпадающий результат и его родителя / предка.

searchHelper(term, children, showParent) {
    let found;
    if (showParent == null || showParent == undefined) {
        showParent = false;
    }
    children.forEach(child => {
        if (found = this.search(term, child)){
            console.log('found--------------------------------');
            child.display = true;
        } else {
            console.log('not foond-----------------------------------------')
            child.display = false;
        }
        showParent = showParent || found;
    })
    return showParent;
}

search(term, parent) {
    let ans, showParent, found, { name, children } = parent;

    if (children.length) {
        showParent = this.searchHelper(term, children, showParent);
    }
    return name.toLowerCase().indexOf(term.toLowerCase()) != -1;
}

this.search("Elephant", this.tree);

Answer 1

Я думаю, это то, что вы ищете:

search = node => {
    let found, { name, childs = [] } = node;

    if (childs.length)
        for (let child of node.childs)
            if (found = search(child))
                return [name].concat(found);

    return name === target && [name];
}

И вот мое полное решение:

const
    // Your animal target name
    target = 'Elephant',

    // Your tree data structure
    tree = [
        { name: 'Elephant', childs: [
            { name: 'Duck' },
            { name: 'Hamster', childs: [
                { name: 'Fish' }
            ]}
        ]},
        { name: 'Hamster', childs: [
            { name: 'Elephant', childs: [
                { name: 'Fish' }
            ]},
            { name: 'Dog', childs: [
                { name: 'Fish' }
            ]}
        ]},
        { name: 'Dog', childs: [
            { name: 'Unicorn' },
            { name: 'Fish', childs: [
                { name: 'Hamster' },
                { name: 'Unicorn', childs: [
                    { name: 'Elephant' }
                ]},
            ]}
        ]},
        { name: 'Elephant', childs: [
            { name: 'Duck' },
            { name: 'Hamster', childs: [
                { name: 'Elephant' },
                { name: 'Fish' },
            ]}
        ]}
    ],

    // The recursive tree search function. Her exit point is
    // a child who matches the target. He returns the path to
    // target - if found - as an array. Otherwise, false
    search = node => {
        let found, { name, childs = [] } = node;

        if (childs.length)
            for (let child of node.childs)
                if (found = search(child))
                    return [name].concat(found);

        return name === target && [name];
    },

    // The result, as a set of arrays. We filter out the
    // branches that do not contain the result
    result = tree.map(search).filter(Boolean);

    // The result as a formatted string for easy viewing
    formattedResult = result.map((path, index) => `${index + 1}: ${path.join(' > ')}`).join('\n');

console.log(formattedResult);