将平面对象数组转换为嵌套树（位置数据）

Question

你好，所以我想将给定的平面对象数组（loc.dataset）转换为具有重复键的树状结构。

注意：我的实际输入数据约为 140K 个对象元素，具有完全相同的 4 个键，如下所示。

输入示例：

[
   {
      "continent_name":"Asia",
      "country_name":"Iran",
      "subdivision_1_name":"Chaharmahal and Bakhtiari Province",
      "city_name":"Lir Abi"
   },
   {
      "continent_name":"Europe",
      "country_name":"Cyprus",
      "subdivision_1_name":"Ammochostos",
      "city_name":"Protaras"
   },
   {
      "continent_name":"Asia",
      "country_name":"Iran",
      "subdivision_1_name":"West
Azerbaijan Province",
      "city_name":"Post"
   },
   {
      "continent_name":"Africa",
      "country_name":"Somalia",
      "subdivision_1_name":"Bakool",
      "city_name":"Oddur"
   }
]

输出示例：

[
        {
           label: "Asia",
           children: [
               {
                   label: 'Iran',
                   children: [
                       {
                           label: 'Chaharmahal and Bakhtiari Province',
                           children: [
                               {
                                  label: 'Lir Abi',
                                  children: []
                               }
                           ]
                       },
                       {
                          label: 'West Azerbaijan Province',
                          children: [
                              {
                                 label: 'Post',
                                 children: []
                              }
                          ]
                       }
                   ]
               }
           ]
        },
        {
          label: "Africa",
          children: [
              {
                  label: 'Somalia',
                  children: [
                      {
                          label: 'Bakool',
                          children: [
                              {
                                  label: 'Oddur',
                                  children: []
                              }
                          ]
                      }
                  ]
              }
          ]
        },
        {
          label: "Europe",
          children: [
              {
                  label: 'Cyprus',
                  children: [
                      {
                          label: 'Ammochostos',
                          children: [
                              {
                                  label: 'Protaras',
                                  children: []
                              }
                          ]
                      }
                  ]
              }
          ]
        }
    ]

这是我试图使用的代码：

    const returnTree = []
    function unflatten(data, property, returnArr) {
        for (let i = 0; i < data.length; i++) {
            const currObj = data[i];
            const currContinent = data[i][property]
            let continentIdx = returnArr.findIndex(obj => obj.label === currContinent)
            if (continentIdx === -1) {
                continentIdx = returnArr.length
                returnArr.push({
                    'label': currContinent,
                    'children': [currObj]
                })
            } else {
                returnArr[continentIdx].children.push(currObj)
            }
            // exceeed max call stack if I continue even one more level in
            unflatten(returnArr[continentIdx].children, 'country_name', returnTree)
        }
        console.log(returnArr)
        return returnArr
    }
    unflatten(inputData, 'continent_name', returnTree)

我遇到的问题是我使用这种递归方法超出了最大调用堆栈，我想知道是否有更好的方法来处理这个问题，也许是迭代？

任何帮助将不胜感激！谢谢你！

Answer 1

另一种方法是使用对象作为哈希表和每个子数组的结果集。

const
    data = [{ continent_name: "Asia", country_name: "Iran", subdivision_1_name: "Chaharmahal and Bakhtiari Province", city_name: "Lir Abi" }, { continent_name: "Europe", country_name: "Cyprus", subdivision_1_name: "Ammochostos", city_name: "Protaras" }, { continent_name: "Asia", country_name: "Iran", subdivision_1_name: "West Azerbaijan Province", city_name: "Post" }, { continent_name: "Africa", country_name: "Somalia", subdivision_1_name: "Bakool", city_name: "Oddur" }],
    keys = ["continent_name", "country_name", "subdivision_1_name", "city_name"],
    result = data
        .reduce((r, o) => {
            keys.reduce(function (q, k) {
                const label = o[k];
                if (!q[label]) q._.push({ label, children: (q[label] = { _: [] })._ });
                return q[label];
            }, r);
            return r;
        }, { _: [] })
        ._;

console.log(result);

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

Answer 2

我不认为递归是一种可行的方法，因为对于每个属性值（用于生成对象），生成的结构中都存在一个位置。迭代属性时，将最后一个外部数组保留在外部变量中，然后您可以 .find 来查看是否已插入匹配的对象 - 如果尚未插入，则创建一个。

const input=[{continent_name:"Asia",country_name:"Iran",subdivision_1_name:"Chaharmahal and Bakhtiari Province",city_name:"Lir Abi"},{continent_name:"Europe",country_name:"Cyprus",subdivision_1_name:"Ammochostos",city_name:"Protaras"},{continent_name:"Asia",country_name:"Iran",subdivision_1_name:"West Azerbaijan Province",city_name:"Post"},{continent_name:"Africa",country_name:"Somalia",subdivision_1_name:"Bakool",city_name:"Oddur"}];

const output = [];
for (const obj of input) {
  let nestedArr = output;
  for (const [key, value] of Object.entries(obj)) {
    const existingInnerObj = nestedArr.find(({ label }) => label === value);
    if (existingInnerObj) {
      nestedArr = existingInnerObj.children;
    } else {
      const newObj = { label: value, children: [] };
      nestedArr.push(newObj);
      nestedArr = newObj.children;
    }
  }
}
console.log(output);

您可以通过将创建的对象保存在地图或按标签索引的对象中，或者首先在对象中创建它们，然后将它们转换为数组来降低复杂性（这将使 O(n)< /code> 将 .find 操作转化为属性查找的 O(1)）。

Answer 3

此版本配置了您想要嵌套的键列表，并且它与每个键一起重复。它的递归仅在结果树的级别上。如果存在递归深度问题，那么还有许多更重要的问题需要处理。