정렬 배열

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

그리고지도 개체 :

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

:

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

나는이 패턴을 일치하도록 정렬 노력하고 있어요

위에서 알 수 있듯이 중첩 트리 구조입니다. 그리고 id 아래에 pid을 입력하고 상단에 가장 낮은 숫자는 id입니다.

하나의 반복 만 사용하여 이런 식으로 배열을 정렬 할 수있는 방법이 있습니까? - 그렇지 않다면 주위를 둘러 보는 방법에 대한 예를 보는 것이 좋습니다.

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

그리고 pid 사용하여 내 부모 찾을 수 내지도를 사용하여 생각 해요 - 그 키에 종류 다음>id를 실행 한 다음,

지금까지 난 단지있다. 내 개체에 추가 속성을 저장하는 것도 괜찮습니다.

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