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

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

我不认为递归是解决问题的方法，因为对于每个属性值（从中生成对象），在生成的结构中它可能恰好位于一个位置。在遍历属性时，将最后一个外部数组保存在外部变量中，您可以 .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) .find 到属性查找的 O(1) 的操作。

Answer 2

另一种方法，将对象作为散列 table 并为每个子数组设置结果集。

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 3

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

const omitting = (prop) => ({[prop]: p, ...rest}) => rest

const group = (fn) => (xs) => Object .values (xs .reduce 
  ((a, x, _, __, k = fn (x)) => ((a [k] = a [k] || []), (a [k] .push (x)), a), 
  {}
))

const labelGroup = ([label, ...labels]) => (xs) => 
  label == undefined
    ? xs
    : group (x => x [label]) (xs) .map (ys => ({
        label: ys [0] [label], 
        children: labelGroup (labels) (
          ys .map (omitting (label)) .filter (x => Object .keys (x) .length)
        )
      }))

const divisions = [{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 labels = ['continent_name', 'country_name', 'city_name', 'subdivision_1_name']

console .log (
  labelGroup (labels) (divisions)
)

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

我们从两个辅助函数开始：

omitting returns 省略指定键的对象副本。
group 接受一个 key-generation 函数，returns 一个接受值和组数组的函数它们分成子数组，每个子数组映射到一个键。

主函数 labelGroup 获取要分组的标签列表和 returns 获取值数组的函数，并递归地将这些分组到共享标签的组中，映射结果通过提取公共标签，从每个标签中省略当前键，并返回将 labelGroup 应用于它们的递归结果以及剩余的键。当没有要提取的标签时，递归达到最低点。

唯一棘手的一点是递归应用程序之前的 filter 调用。我们用它来删除完全空的对象。当您对对象中的每个标签进行分组时，这会为您提供所需的结果，如此处所做的那样，但也允许您对较小的标签列表进行分组。所以如果你只通过 'continent_name' 和 'countryName'，你会得到这样的结果：

    {
        "label": "Asia",
        "children": [
            {
                "label": "Iran",
                "children": [
                    {
                        "subdivision_1_name": "Chaharmahal and Bakhtiari Province",
                        "city_name": "Lir Abi"
                    },
                    {
                        "subdivision_1_name": "West Azerbaijan Province",
                        "city_name": "Post"
                    }
                ]
            }
        ]
    },
    /* ... */
}

我认为这是一种相当灵活的技术。我们可以通过允许我们对复合键或 select 显示在每个级别的多个字段进行分组来使其更加灵活，并且我们可以使字段 label 和 children 可配置。但那是另一天。

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

Turning flat array of objects into nested tree (location data)

javascript

tree

recursion

flatten