javascript - 数组递归排序

Question

我有一个像这样的数组:

var a = [
  {id: 1, pid: 0},
  {id: 2, pid: 1},
  {id: 3, pid: 1},
  {id: 4, pid: 2},
  {id: 5, pid: 2},
  {id: 6, pid: 3},
  {id: 7, pid: 3}
]

还有一个像这样的 map 对象:

var map = {
  "1": {id: 1, pid: 0},
  "2": {id: 2, pid: 1},
  "3": {id: 3, pid: 1},
  "4": {id: 4, pid: 2},
  "5": {id: 5, pid: 2},
  "6": {id: 6, pid: 3},
  "7": {id: 7, pid: 3}
}

我正在尝试对其进行排序以匹配此模式:

var result = [
  {"id": 1, "pid": 0},
    {"id": 2, "pid": 1},
      {"id": 4, "pid": 2},
      {"id": 5, "pid": 2},
    {"id": 3, "pid": 1},
      {"id": 6, "pid": 3},
      {"id": 7, "pid": 3}
]

正如你所看到的，这是一个嵌套的树结构。我想获取匹配 id 下的 pid 以及顶部最低的 id。

有什么方法可以仅使用一次迭代对这样的数组进行排序吗？ - 如果没有，很高兴看到一个关于如何解决它的示例。

到目前为止我只有:

a.sort(function(q, w) { return q.pid - w.pid; });

我正在考虑使用我的 map 通过 pid->id 找到我的 parent ，然后根据该键进行排序。也可以在我的对象上存储额外的属性。

Answer 1

假设有一个 pid 0 的根:

var children = {}
var root = null;
a.forEach(function(e) {
    children[e.id] = [];
});

a.forEach(function(e) {
    if (e.pid === 0) {
        root = e;
    }
    else {
        children[e.pid].push(e);
    }
});

var sorted = [];

function preorder(e) {
    sorted.push(e);
    if (children.hasOwnProperty(e.id)) {
        children[e.id].forEach(preorder);
    }
}
preorder(root);

结果:

[
  {"id":1,"pid":0},
    {"id":2,"pid":1},
    {"id":4,"pid":2},
      {"id":5,"pid":2},
    {"id":3,"pid":1},
      {"id":6,"pid":3},
      {"id":7,"pid":3}
]