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。

1 回の反復のみを使用して、このような配列を並べ替える方法はありますか? -そうでない場合は、それを回避する方法の例を見るといいでしょう。

これまでのところ、私は次のものしか持っていません:

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

pidそして、マップを使用して->を使用して親を見つけ、idそのキーで並べ替えることを考えています。オブジェクトに追加のプロパティを保存しても問題ありません。

4

1 に答える 1

1

pid 0 のルートが 1 つあると仮定します。

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 に答える