1

我有一个这样的数组：

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

还有一个像这样的地图对象：

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

如您所见，这是一个嵌套的树结构。我想pid在匹配和顶部id最低。id

有没有办法只使用一次迭代对这样的数组进行排序？- 如果没有，很高兴看到一个关于如何绕过它的例子。

到目前为止，我只有：

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

我正在考虑使用我的地图使用pid->找到我的父母id，然后对该键进行排序。也可以在我的对象上存储额外的属性。

4

1 回答 1

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}
]
于 2013-04-23T10:26:11.950 回答