如何从节点树中查找路径

Question

考虑一个类似于下面的数据结构：

[
    { name: 'Link1', url: 'link1', },
    { name: 'Link2', url: 'link2', },
    {
        name: 'Link3', url: 'link3',
        submenu: [
            { name: 'Link4', url: 'link4', },
            { name: 'Link5', url: 'link5', },
        ]
    },
    { name: 'Link6', url: 'link6', },
    {
        name: 'Link6', url: 'link6',
        submenu: [
            { name: 'Link7', url: 'link7', },
            {
                name: 'Link8', url: 'link8',
                submenu: [
                    { name: 'Link9', url: 'link9', },
                    { name: 'Link10', url: 'link10', },
                ]
            },
        ]
    },
    { name: 'Link11', url: 'link11', },
    { name: 'Link12', url: 'link12', },
]

我用递归试过的函数如下

function findObject(obj, element) {
    for (const item of obj) {
        if (item.url === element) {
            return [item];
        }
        if (item.submenu) {
            const array = findObject(item.submenu, element);
            if (array) {
                return array;
            }
        }

    }
}
let output = findObject(data, 'link10')
console.log(output);

我得到一个输出：[{name: 'Link10', url: 'link10'}]

我想得到如下输出：

[{ name: 'Link1', url: 'link1', }, { name: 'Link6', url: 'link6' }, { name: 'Link8', url: 'link8' }, { name: 'Link10', url: 'link10', }]

如果我按如下方式调用该函数：

let output = findObject(data, 'link11')
console.log(output);

return 的结果应该是 [{name: 'Link11', url: 'link11',}]

我也尝试了以下方法并使用数组方法，但没有成功：

function findObject(obj, element) {
    for (const item of obj) {
        if (item.url === element) {
            return [item];
        }
        // if (item.submenu){
        //     const array = findObject(item.submenu, element);
        //     if(array){
        //         return array;
        //     }
        // }
        const array = findObject(item.submenu, element);
        if (array) {
            return [item, ...array];
        }
    }
}

其中 ($_$w, obj) 的结果不可迭代。如果有人能解释一下，我哪里出错了，以及如何解决这个问题，我将不胜感激。

Answer 1

我很高兴，至少你试着自己解决了你的问题！

这是个很有趣的问题。因为它是一种寻路情况。

假设我们需要找到正确的路径，现在每当我们找到任何路径时，我们都会在笔记本上记下该路径。

现在有2条路，我们选择第1条路，我发现这是错误的路，所以我们尝试了第2条路，依此类推...

如果我们找到任何正确的路径，我们需要停止寻找新路径并通过查看笔记本，我们可以找到正确的路径...

我解释的很烂，让我们看看代码，

const data = [{ name: 'Link1', url: 'link1', }, { name: 'Link2', url: 'link2', }, { name: 'Link3', url: 'link3', submenu: [{ name: 'Link4', url: 'link4', }, { name: 'Link5', url: 'link5', },] }, { name: 'Link6', url: 'link6', }, { name: 'Link6', url: 'link6', submenu: [{ name: 'Link7', url: 'link7', }, { name: 'Link8', url: 'link8', submenu: [{ name: 'Link9', url: 'link9', }, { name: 'Link10', url: 'link10', },] },] }, { name: 'Link11', url: 'link11', }, { name: 'Link12', url: 'link12', },]

function createTree(data, element) {
    const nodes = { item: null, child: null }
    for (const { name, submenu, url } of data) {
        if (url == element) {
            nodes.item = { name, url }
            break
        }
        if (submenu) {
            const result = createTree(submenu, element);
            if (result.item) {
                nodes.item = { name, url }
                nodes.child = result;
                break
            }
        }
    }
    return nodes;
}
function findObject(data, element) {
    let result = [], tree = createTree(data, element);

    while (tree) {
        result.push(tree.item)
        tree = tree.child;
    }
    if (result.length > 1) result.unshift(data[0]);

    return result;
}
console.log('link2', findObject(data, 'link2'));
console.log('link5', findObject(data, 'link5'));
console.log('link10', findObject(data, 'link10'));
console.log('link99', findObject(data, 'link99'));

Answer 2

我不确定我是否遗漏了一些关于这里要求的东西，但看起来你和我很接近：

const data = [{"name":"Link1","url":"link1"},{"name":"Link2","url":"link2"},{"name":"Link3","url":"link3","submenu":[{"name":"Link4","url":"link4"},{"name":"Link5","url":"link5"}]},{"name":"Link6","url":"link6"},{"name":"Link6","url":"link6","submenu":[{"name":"Link7","url":"link7"},{"name":"Link8","url":"link8","submenu":[{"name":"Link9","url":"link9"},{"name":"Link10","url":"link10"}]}]},{"name":"Link11","url":"link11"},{"name":"Link12","url":"link12"}];

const trim_item = ({ name, url }) => ({ name, url });

function findObject(obj, element) {
  for (const item of obj) {
    if (item.url === element) {
      return [item];
    }
    if (item.submenu){
      const array = findObject(item.submenu, element);
      if(array){
        return [trim_item(item), ...array];
      }
    }
  }
  
  return null;
}

console.log('link2', findObject(data, 'link2'));
console.log('link5', findObject(data, 'link5'));
console.log('link10', findObject(data, 'link10'));
console.log('link99', findObject(data, 'link99'));

如何从节点树中查找路径

How to find path from tree of nodes

javascript

tree

recursion

nodes