从平面阵列创建嵌套阵列-数据结构

Question

我需要创建一个嵌套数组，使用路径作为子节点的参考。例如：4.1是4岁的孩子，4.1.1是4.1岁的孩子，4.2是4岁的孩子...我有一个平面数组，里面有所有的数据和路径。如何创建嵌套数组的最佳方法，其中子数组根据其路径嵌套到其父数组。

输入：

const list = [
  {
    location: 1,
    path: '4'
  },
  {
    location: 2,
    path: '4.1'
  },  
  {
    location: 3,
    path: '4.1.1'
  },  
  {
    location: 4,
    path: '4.1.2'
  },  
  {
    location: 5,
    path: '4.2'
  },  
  {
    location: 6,
    path: '4.2.1'
  },
  {
    location: 7,
    path: '4.3'
  },
  {
    location: 8,
    path: '4.3.1'
  }
];

输出：

const  list = [
  {
    location: 1,
    path: '4',
        children: [
            {
            location: 2,
            path: '4.1',
            children: [
                {
                    location: 3,
                    path: '4.1.1'
                },  
                {
                    location: 4,
                    path: '4.1.2'
                },  
            ]
        },  
            {
                location: 5,
                path: '4.2',
                children: [
                    {
                        location: 6,
                        path: '4.2.1'
                    },
                ]
            },  
            {
                location: 7,
                path: '4.3',
                children: [
                    {
                        location: 8,
                        path: '4.3.1'
                    }
                ]
            },
        ]
  },
];

最好的方法是递归的。对这个算法有什么建议吗？

Answer 1

一种方法是使用中间索引将路径映射到对象，然后通过在索引中查找每个节点及其父节点，将列表折叠成一个结构。如果没有父对象，则将其添加到根对象。最后，我们返回根对象的子对象。下面是一些代码：

const restructure = (list) => {
  const index = list .reduce(
    (a, {path, ...rest}) => ({...a, [path]: {path, ...rest}}), 
    {}
  )
  
  return list .reduce((root, {path}) => {
    const node = index [path]
    const parent = index [path .split('.') .slice(0, -1) .join('.')] || root
    parent.children = [...(parent.children || []), node]
    return root
  }, {children: []}) .children
}

const list = [{location: 1, path: '4'}, {location: 2, path: '4.1' }, {location: 3, path: '4.1.1'}, {location: 4, path: '4.1.2'}, {location: 5, path: '4.2'}, {location: 6, path: '4.2.1'}, {location: 7, path: '4.3'}, {location: 8, path: '4.3.1'}]

console.log (restructure (list))

css prettyprint-override">.as-console-wrapper {min-height: 100% !important; top: 0}

Answer 2

我很好奇斯科特的链接答案是否能够不经修改就解决这个问题。是的！

import { tree } from './Tree'
import { bind } from './Func'

const parent = (path = "") =>
  bind
    ( (pos = path.lastIndexOf(".")) =>
        pos === -1
          ? null
          : path.substr(0, pos)
    )

const myTree =
  tree                          // <- make tree
    ( list                      // <- array of nodes
    , node => parent(node.path) // <- foreign key
    , (node, children) =>       // <- node reconstructor
        ({ ...node, children: children(node.path) }) // <- primary key
    )

console.log(JSON.stringify(myTree, null, 2))

[
  {
    "location": 1,
    "path": "4",
    "children": [
      {
        "location": 2,
        "path": "4.1",
        "children": [
          {
            "location": 3,
            "path": "4.1.1",
            "children": []
          },
          {
            "location": 4,
            "path": "4.1.2",
            "children": []
          }
        ]
      },
      {
        "location": 5,
        "path": "4.2",
        "children": [
          {
            "location": 6,
            "path": "4.2.1",
            "children": []
          }
        ]
      },
      {
        "location": 7,
        "path": "4.3",
        "children": [
          {
            "location": 8,
            "path": "4.3.1",
            "children": []
          }
        ]
      }
    ]
  }
]

Tree模块在这篇文章中共享，这里有一个关于提供bind的Func模块的窥视-

// Func.js
const identity = x => x

const bind = (f, ...args) =>
  f(...args)

const raise = (msg = "") => // functional throw
  { throw Error(msg) }

// ...

export { identity, bind, raise, ... }

展开下面的代码片段，在浏览器中验证结果-

// Func.js
const bind = (f, ...args) =>
  f(...args)
  
// Index.js
const empty = _ =>
  new Map

const update = (r, k, t) =>
  r.set(k, t(r.get(k)))

const append = (r, k, v) =>
  update(r, k, (all = []) => [...all, v])

const index = (all = [], indexer) =>
  all.reduce
      ( (r, v) => append(r, indexer(v), v)
      , empty()
      )
      
// Tree.js
// import { index } from './Index'
function tree (all, indexer, maker, root = null)
{ const cache =
    index(all, indexer)

  const many = (all = []) =>
    all.map(x => one(x))
    
  const one = (single) =>
    maker(single, next => many(cache.get(next)))

  return many(cache.get(root))
}

// Main.js
// import { tree } from './Tree'
// import { bind } from './Func'

const parent = (path = "") =>
  bind
    ( (pos = path.lastIndexOf(".")) =>
        pos === -1
          ? null
          : path.substr(0, pos)
    )

const list =
  [{location:1,path:'4'},{location:2,path:'4.1'},{location:3,path:'4.1.1'},{location:4,path:'4.1.2'},{location:5,path:'4.2'},{location:6,path:'4.2.1'},{location:7,path:'4.3'},{location:8,path:'4.3.1'}]

const myTree =
  tree
    ( list                      // <- array of nodes
    , node => parent(node.path) // <- foreign key
    , (node, children) =>       // <- node reconstructor
        ({ ...node, children: children(node.path) }) // <- primary key
    )

console.log(JSON.stringify(myTree, null, 2))

Answer 3

首先可以按路径对对象数组进行排序，这样父对象在排序后的数组中总是在其子对象之前。例如：“4”将在“4.1”之前

现在，您可以创建一个对象，其中关键点是路径。假设“4”已经插入到我们的对象中。

obj = {
  '4': {
    "location": 1,
    "path": "4",    
  }
}

当我们处理'4.1'时，我们首先检查对象中是否存在'4'。如果是，我们现在进入它的子对象（如果键“子对象”不存在，我们将创建一个新的空对象），并检查“4.1”是否存在。如果没有，我们插入“4.1”

obj = {
  '4': {
    "location": 1,
    "path": "4",
    "children": {
      "4.1": {
        "location": 2,
        "path": "4.1"
      }
    }
  }
}

我们对列表中的每个元素重复这个过程。最后，我们只需要递归地将这个对象转换成一个对象数组。

最终代码：

list.sort(function(a, b) {
  return a.path - b.path;
})

let obj = {}

list.forEach(x => {
  let cur = obj;
  for (let i = 0; i < x.path.length; i += 2) {
    console.log(x.path.substring(0, i + 1))
    if (x.path.substring(0, i + 1) in cur) {
      cur = cur[x.path.substring(0, i + 1)]
      if (!('children' in cur)) {
        cur['children'] = {}
      }
      cur = cur['children']
    } else {
      break;
    }
  }
  cur[x.path] = x;
})

function recurse (obj) {
  let res = [];
  Object.keys(obj).forEach((key) => {
    if (obj[key]['children'] !== null && typeof obj[key]['children'] === 'object') {
      obj[key]['children'] = recurse(obj[key]['children'])
    }
    res.push(obj[key])
  })
  return res;
}

console.log(recurse(obj));