레벨 순회의 순회 트리 순회

Question

다음과 같은 재귀 적 데이터 구조와 반복 방법이 있습니다. 그렇게하는 동안 각 노드에 고유 번호 인 n을 추가해야합니다. 그 나무의 level order traversal에있는 해당 번호.

var data = { 
    children: [ 
     { children: [ ... ] }, 
     { children: [ ... ] }, 
     { children: [ ... ] }, 
     ... 
    ] 
} 

var process = function (node) { 
    node.children.forEach(child, function() { 
     process(child); 
    }); 
    return node; 
} 

데이터 구조를 변경하지 않고 처리 기능을 최소한으로 변경하지 않고 어떻게이 작업을 수행 할 수 있습니까? process(data)의 결과는

var data = { 
    n: 1 
    children: [ 
     { n: 2, children: [ ... ] }, 
     { n: 3, children: [ ... ] }, 
     { n: 4, children: [ ... ] }, 
     ... 
    ] 
} 

Answer 1

이어야합니다. 큐를 사용하여 각 수준에 노드를 저장하십시오. 한 레벨 끝을 표시하려면 null을 사용하십시오.

처음에는 루트 노드 인 null을 큐로 푸시합니다. 그런 다음 큐를 반복하고, 각 노드의 하위 노드를 큐에 넣고 Null이 아닌 요소를 표시합니다. null 요소가 나타나면 새 요소를 누릅니다. 따라서 결과적으로 두 개의 null은 반복의 끝을 표시합니다.

var process = function (node) { 
    var queue = [node, null]; 
    var i = 0, n = 1; 
    while (queue[i] != null || (i == 0 || queue[i-1] != null)) { 
     if (queue[i] == null) { 
      queue.push(null); 
     } 
     else { 
      queue[i].n = n++; 
      queue[i].children.forEach(function (elem) { 
       queue.push(elem); 
      }); 
     } 
     i++; 
    } 
} 

process(data); 
console.log(data); 

나는 큐에 대한 배열을 사용 ( O (n)이 공간이 필요)를 방문 요소를 큐에서 제거하지 않았다. queue이 소비하는 공간에 병목 현상이있는 경우이를 다른 대기열 구현으로 바꾸고 알고리즘을 약간 변경할 수 있습니다.