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

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

您可以先按路径对对象数组进行排序，以使父对象始终位于排序数组中的子对象之前。例如：“ 4”将在“ 4.1”之前]

现在，您可以创建一个对象，其中键为路径。假设已在对象中插入“ 4”。

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

当我们处理'4.1'时，我们首先检查对象中是否存在'4'。如果是，则现在进入其子项（如果不存在键“ children”，则创建一个新的空对象）并检查是否存在“ 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));

Answer 2

的想法与Aadith相同，但来自迭代方法。我认为最有效的方法是使用链表结构，然后将其展平。

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'
  }
];

let newList = []
list.forEach((location) =>
{
  console.log('Handling location ',location);
  if(location.path.split('.').length==1)
  {
    location.children = [];
    newList.push(location);
  }
  else
  {
    newList.forEach(loc => {
      console.log('checking out: ',loc);
      let found = false;
      while(!found)
      {
        console.log(loc.path,'==',location.path.substring(0, location.path.lastIndexOf('.')));
        found = loc.path == location.path.substring(0, location.path.lastIndexOf('.'));
        if(!found)
        {
          for(let i=0;i<loc.children.length;i++)
          {
            let aloc = loc.children[i];
            found = aloc.path == location.path.substring(0, location.path.lastIndexOf('.'));
            if(found)
            {
              console.log('found it...', loc);
              location.children = [];
              aloc.children.push(location);
              break;
            }
          }
          console.log('new parent check: ', loc);
        }
        else
        {
          console.log('found it...', loc);
          location.children = [];
          loc.children.push(location);
        }
      }
    } );
  }
});

console.log(newList);

这是我快速又肮脏的解决方法