从平面结构和反转中创建嵌套 object 结构？

Question

我有一个平面阵列。像这样：

const inputArray = [
  {
    path: '1',
    id: '1'
  },
  {
    path: '2',
    id: '2'
  },
  {
    path: '3',
    id: '3'
  },
  {
    path: '3.4',
    id: '4'
  },
  {
    path: '3.5',
    id: '5'
  },
  {
    path: '3.4.6',
    id: '6'
  },
  {
    path: '3.4.7',
    id: '7'
  },
  {
    path: '8',
    id: '8'
  },
]

其中 path 是 id 元素的唯一路径。例如，path: '3.5' 表示此 object 对于 object 和 id: '3' 是 child。而 path: '3.4.6' 是 child 对于 path: '3.4'。我想将它们收集到嵌套结构中。所以结果应该是这样的。

const result = [
  {
    path: '1',
    id: '1',
    children: []
  },
  {
    path: '2',
    id: '2',
    children: []
  },
  {
    path: '3',
    id: '3',
    children: [
      {
        path: '3.4',
        id: '4',
        children: [
           {
            path: '3.4.6',
            id: '6',
            children: []
          },
          {
            path: '3.4.7',
            id: '7',
            children: []
          },
        ]
      },
      {
        path: '3.5',
        id: '5',
        children: []
      },
    ]
  },
  {
    path: '8',
    id: '8',
    children: []
  },
]

而且我还需要第二种算法将它们从嵌套结构转换回平面结构。可以给个广告建议吗？

更新：数据未排序。 Here 是我的尝试，但是代码太多，在某些情况下会失败。我觉得应该有更好的方法来做这个。

Answer 1

您可以使用对象作为未排序数据的辅助结构并构建树。

要获得平面数组，您可以迭代树并使用递归函数连接平面子项。

function getTree(array) {
    var o = {};
    array.forEach(({ id, path }) => {
        var parents = path.split('.'),
            parent = parents[parents.length - 2];

        Object.assign(o[id] = o[id] || {}, { id, path });
        o[parent] = o[parent] || {};
        o[parent].children = o[parent].children || [];
        o[parent].children.push(o[id]);
    });
    return o.undefined.children;
}

function getFlat(array = []) {
    return array.reduce((r, { id, path, children }) =>
        r.concat({ id, path }, getFlat(children)), []);
}

var input = [{ path: '1', id: '1' }, { path: '2', id: '2' }, { path: '3', id: '3' }, { path: '3.4', id: '4' }, { path: '3.5', id: '5' }, { path: '3.4.6', id: '6' }, { path: '3.4.7', id: '7' }, { path: '8', id: '8' }],
    tree = getTree(input),
    flat = getFlat(tree);

console.log(tree);
console.log(flat);

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

不保留的解决方案path。

function getTree(array) {
    var o = {};
    array.forEach(({ id, path }) => {
        var parents = path.split('.'),
            parent = parents[parents.length - 2];

        Object.assign(o[id] = o[id] || {}, { id });
        o[parent] = o[parent] || {};
        o[parent].children = o[parent].children || [];
        o[parent].children.push(o[id]);
    });
    return o.undefined.children;
}

function getFlat(array = [], path = []) {
    return array.reduce((r, { id, children }) => {
        var p = path.concat(id);
        return r.concat({ id, path: p.join('.') }, getFlat(children, p));
    }, []);
}

var input = [{ path: '1', id: '1' }, { path: '2', id: '2' }, { path: '3', id: '3' }, { path: '3.4', id: '4' }, { path: '3.5', id: '5' }, { path: '3.4.6', id: '6' }, { path: '3.4.7', id: '7' }, { path: '8', id: '8' }],
    tree = getTree(input),
    flat = getFlat(tree);

console.log(tree);
console.log(flat);

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

Answer 2

使用Array.reduce, Array.findIndex, Array.push and Array.shift

转换为树

假设input array是按路径排序的，否则不会对inputArray.sort((a,b) => a.path - b.path);
减少数组形成树
通过拆分路径并从中创建数字数组来创建层次结构数组
创建一个需要 3 个输入的函数 addChildren
- a -> Parent object (array) 其中 object 将被插入
- c -> object 需要插入
- t -> 需要插入的object的层级数组
函数采用 t 的第一个值，如果它在层次结构中是最后一个，则这意味着 a 是 object 的有效占位符。因此，把它推到那里。如果还有剩余值，则找到通过匹配 id 来自数组的占位符。现在，再次调用 a 函数将成为 匹配的 object 的 children 数组， c 保持不变，t 将是剩余的层次结构数组。

const inputArray = [{path:'1',id:'1'},{path:'2',id:'2'},{path:'3',id:'3'},{path:'3.4',id:'4'},{path:'3.5',id:'5'},{path:'3.4.6',id:'6'},{path:'3.4.7',id:'7'},{path:'8',id:'8'}];

const result = inputArray.reduce((a,c) => {
  let t = c.path.split(".").map(Number);
  addChildren(a,c,t);
  return a;
}, []);

function addChildren(a, c, t) {
  let val = t.shift();
  if(!t.length) {
    a.push({...c, children : []});
  } else {
    var i = a.findIndex(({id}) => Number(id) === val);
    addChildren(a[i].children, c, t);
  }
}
console.log(result);

展平树

创建一个接受 2 个输入的函数
- a -> 输入数组（children 的数组）
- r -> 结果数组
函数遍历输入数组并将 objects 压入结果数组并检查任何 children，如果是，则调用该函数对于 children 以及

var inputArray = [{path:'1',id:'1',children:[]},{path:'2',id:'2',children:[]},{path:'3',id:'3',children:[{path:'3.4',id:'4',children:[{path:'3.4.6',id:'6',children:[]},{path:'3.4.7',id:'7',children:[]},]},{path:'3.5',id:'5',children:[]},]},{path:'8',id:'8',children:[]},];

function flattenArray(a, r) {
  a.forEach(({children, ...rest}) => {
    r.push(rest);
    if(children) flattenArray(children, r)
  });
}
var result = [];
flattenArray(inputArray, result);
console.log(result);

Answer 3

如果你想要更多的通用性，你可以从输入创建树结构，然后用它做任何你想做的事（即以你想要的某种格式输出，添加查找某些项目的方法等）

const inputArray = [
    {
        path: '1',
        id: '1'
    },
    {
        path: '2',
        id: '2'
    },
    {
        path: '3',
        id: '3'
    },
    {
        path: '3.4',
        id: '4'
    },
    {
        path: '3.5',
        id: '5'
    },
    {
        path: '3.4.6',
        id: '6'
    },
    {
        path: '3.4.7',
        id: '7'
    },
    {
        path: '8',
        id: '8'
    },
];

class Tree {
    constructor() {
        this.root = {};
    }

    addNewNode(path, node) {
        const pathArr = path.split('.');
        let currentNode = this.root;
        pathArr.forEach(item => {
            if (!currentNode[item]) {
                currentNode[item] = {};
            }
            currentNode = currentNode[item];
        });
        currentNode.data = node;
    }
}

const tree = new Tree();
inputArray.forEach(val => tree.addNewNode(val.path, val));
console.log(tree);

输出是树的输出，而不是您包含的确切输出 - 这取决于您如何处理它。

从平面结构和反转中创建嵌套 object 结构？

Make nested object structure from flat structure and reverse?

javascript

arrays

algorithm

tree

flatten