Javascript树搜索算法，该算法返回包含所找到的术语及其父代的树的子集 [英] Javascript tree search algorithm which return subset of the tree which contains the found term and its parents

问题描述

我有一个树选择，其中每个节点都有一个名称.我想搜索节点名称并返回只包含找到的节点及其父节点的树的子集.

I have a tree selection in which every node has a name. I want to search through the node names and return a subset of the tree which only contains the found nodes and its parents.

没有人知道JavaScript中针对此问题的有效算法，该算法会将节点及其所有父级返回.

Does anybody know an efficient algorithm in JavaScript for this problem which return the node with all of its parents.

这里是一个例子.当用户键入搜索词(例如大象")时，树将如下所示:

Here is an example. when user type a search term, example "Elephant" and the tree looks like this:

• 大象
  • 仓鼠
    • 鱼
    • Elephant
      • Hamster
        • Fish
        • 狗
          • 鱼
          • dog
            • Fish
            • 鱼
            • 鱼
              • 独角兽
                • 大象
                • Fish
                  • Unicorn
                    • Elephant
                    • 仓鼠
                      • 鱼
                      • 大象
                      • 大象
                      • Hamster
                        • Fish
                        • Elephant
                        • Elephant

                        想以树形格式输出搜索结果，像这样子级:

                        Would like to output the search result in tree format with children like this:

                        • 大象
                        • 仓鼠
                          • 大象
                          • Elephant
                          • Hamster
                            • Elephant
                            • 鱼
                              • 独角兽
                                • 大象
                                • Fish
                                  • Unicorn
                                    • Elephant
                                    • 仓鼠
                                      • 大象
                                      • 大象
                                      • Hamster
                                        • Elephant
                                        • Elephant

                                        给出:

                                        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' },
                                                ]}
                                            ]}
                                        ],
                                        

                                        尝试从Nave的解决方案中修改树(以原始树对象格式输出结果，将属性设置为display = false以隐藏该节点，即使找到匹配的节点，也继续搜索同一级别的另一个节点). 这看起来像是DFS，但是仍然需要花费大量时间来计算回溯.最终结果是返回仅包含匹配结果及其父/祖先的树.

                                        Attempt to modify the tree from Nave's solution (output result in original tree object format, set property to display = false to hide the node, keep on searching the other node in the same level even if found matching node). This seems like a DFS, however am still taking lots of time to figure the backtracking. Final result is to return the tree which contains only the matching result and its parent/ancestor.

                                        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);
                                        

                                        推荐答案

                                        我想这就是您要寻找的:

                                        I guess that's what you're looking for:

                                        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];
                                        }
                                        

                                        这是我的完整解决方案:

                                        And here is my full solution:

                                        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);

                                        这篇关于Javascript树搜索算法，该算法返回包含所找到的术语及其父代的树的子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！