在对象数组中找到具有特定键的对象的路径

Question

假设我有如下字典数组。如何使用 id: 121 找到对象的路径。我正在尝试在 javascript 中执行此操作，但我对此一无所获。我需要一种算法或其他东西来获得实现此目标的想法。

我期待的结果是 [{id:1, name:"foo"}, {id: 12, name:"shoo"}, {id: 121, name:"jhj"}]

[
    {
        "id": 1,
        "name": "foo",
        "submenus": [
            {
                "id": 11,
                "name": "bar",
                "submenus": [
                    {
                        "id": 111,
                        "name": "abc"
                    }
                ]
            },
            {
                "id": 12,
                "name": "shoo",
                "submenus": [
                    {
                        "id": 121,
                        "name": "jhj"
                    }
                ]
            }
        ]
    },
    {
        "id": 2,
        "name": "kjk"
    }
]

这是我为它写的代码。此代码适用于 VueJS。

getBreadcrumbs(menuItems, id, breadcrumpsArray) {
    for (var i = 0; i < menuItems.length; i++) {
      if (menuItems[i].id == id) {
        breadcrumpsArray.push({
          id: menuItems[i].id,
          name: menuItems[i].text
        })
        return breadcrumpsArray
      } else {
        if (menuItems[i].submenus !== 'undefined') {
          if (menuItems[i].submenus.length > 0) {
            console.log('shoo')
            this.getBreadcrumbs(menuItems[i].submenus, id, breadcrumpsArray)
          }
        }
      }
    }
  }

这显示错误说：

Error in render: "TypeError: menuItems[i].submenus is undefined"

Answer 1

您可以定义一个递归函数 findPath() 来实现您的要求。请参阅以下代码段中记录的注释：

const data=[{"id":1,"name":"foo","submenus":[{"id":11,"name":"bar","submenus":[{"id":111,"name":"abc"}]},{"id":12,"name":"shoo","submenus":[{"id":121,"name":"jhj"}]}]},{"id":2,"name":"kjk"}];

/* Define a recursive function that finds the item path from root
of the data set, to the first child found with matching id */
const findPath = (items, id) => {
    
    /* Iterate the items of this level */
    for(const item of items) {

        if(item.id === id) {
            /* If id matches id, return tail of resulting array that 
            will be our path result */
            return [item]
        }
        else if(Array.isArray(item.submenus)) {
            /* If submenus sub array present, search the items of the
            submenu recursivly for a nested child with matching id */
            const result = findPath(item.submenus, id)
            if(Array.isArray(result)) {
                /* If recursive call returns an array result, this means
                a nested child with id was found, so prefix this item to
                the results array */
                return [item].concat(result)
            }
        }
    }
}

/* Map id and name of each item in found path to result array */
const result = findPath(data, 121).map(({ id, name }) => ({ id, name }));

console.log( result );

另请注意，在您当前的代码中，这是您检查菜单项上是否存在 submenus sub-array 的方式中的一个小错误。

应用以下更改应该会导致您看到的错误：

getBreadcrumbs(menuItems, id, breadcrumpsArray) {
    for (var i = 0; i < menuItems.length; i++) {
        if (menuItems[i].id == id) {

            breadcrumpsArray.push({
                id: menuItems[i].id,
                name: menuItems[i].text
            });

        } else {

            /* Add "typeof" here to determine if submenus if undefined in this way */
            if (typeof menuItems[i].submenus !== 'undefined') {
                if (menuItems[i].submenus.length > 0) {
                    this.getBreadcrumbs(menuItems[i].submenus, id, breadcrumpsArray)
                }
            }
        }
    }

    /* Move this here */
    return breadcrumpsArray;
}

有关此 typeof 运算符的更多信息，see this documentation

Answer 2

您可以找到该路径，如果找到，则将该节点的对象放入结果集中。

function findPath(array, target) {
    var path;
    return array.some(({ id, name, submenus = [] }) => {
            if (id === target) return path = [{ id, name }];
            var temp = findPath(submenus, target);
            if (temp.length) return path = [{ id, name }, ...temp];
        })
        ? path
        : [];
}

var array = [{ id: 1, name: "foo", submenus: [{ id: 11, name: "bar", submenus: [{ id: 111, name: "abc" }] }, { id: 12, name: "shoo", submenus: [{ id: 121, name: "jhj" }] }] }, { id: 2, name: "kjk" }];;

console.log(findPath(array, 121))

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 3

我终于找到了一种方法，这是我的算法步骤：

首先，DFS (Depth First Search) 您的树，直到您找到具有您正在寻找的 id 的节点
找到后推到breadscrumpArray和return breadscrumpArray
每次搜索 submenu 元素时，我们都会知道我们要查找的节点是否是该元素的子节点，就好像它不是子节点一样，[=函数 getBreadcrumbs 的 36=] 将是 false

希望对你有所帮助，有什么问题可以在评论里告诉我，干杯！

function getBreadcrumbs(menuItems, id, breadcrumpsArray) {
    for (var i = 0; i < menuItems.length; i++) {
        if (menuItems[i].id == id) {
            // Found the node, push it and return the breadcrumpsArray
            breadcrumpsArray.push({
                id: menuItems[i].id,
                name: menuItems[i].name
            });
            return breadcrumpsArray;
        } else {
            if (typeof menuItems[i].submenus !== 'undefined') {
                if (menuItems[i].submenus.length > 0) {
                    if (getBreadcrumbs(menuItems[i].submenus, id, breadcrumpsArray)) {
                        // Unshift to push the node to the front of the array
                        breadcrumpsArray.unshift({
                            id: menuItems[i].id,
                            name: menuItems[i].name
                        });
                        return breadcrumpsArray;
                    }
                }
            } else {
                // The node we are looking for is not in this path of the tree
                return false;
            }
        }
    }
}

在对象数组中找到具有特定键的对象的路径

Find the path of an object in which there is a key with a speicific in a array of objects

javascript

algorithm

vue.js