트리에서 각 노드에 대한 경로를 재귀 적으로 작성하는 방법 - JavaScript?

Question

내 데이터 구조는 다음과 같이 표시됩니다

는

var tree = [ 
    { 
     id: 1, 
     children: [] 
    }, { 
     id: 2, 
     children: [ 
      { 
       id: 3, 
       children: [] 
      } 
     ] 
    } 
]; 

한 지점에 노드 나 어린이의 숫자가있을 수 있습니다.

내 목표는 모든 노드에 대한 경로를 만드는 것입니다. 예를 들어 ID에 대한

: 3의 경로를해야합니다 1> 2> 3 ID : 2 일의 경로를해야합니다> 2 나는이 같은 수정 될 수 있도록 알고리즘을 통해 내 나무를 실행하려면

이 :

나는 트리에서 모든 노드를 방문하는 알고리즘 작성한

var tree = [ 
     { 
      id: 1, 
      path: [1], 
      children: [] 
     }, { 
      id: 2, 
      path: [2], 
      children: [ 
       { 
        id: 3, 
        path: [2, 3], 
        children: [] 
       } 
      ] 
     } 
    ]; 

: https://plnkr.co/edit/CF1VNofzpafhd1MOMVfj

어떻게 각 노드에 대한 경로를 구축 할 수 있습니까?

function traverse(branch, parent) { 

    for (var i = 0; i < branch.length; i++) { 

    branch[i].visited = true; 

    if (branch[i].path === undefined) { 
     branch[i].path = []; 
    } 

    if (parent != null) { 
     branch[i].path.push(parent); 
    } 

    if (branch[i].children.length > 0) { 
     traverse(branch[i].children, branch[i].id); 
    } 

    } 

} 

Answer 1

직접 관련이없는 부모의 불분명 복용 옆에, 당신이 arrray 같은 경로를 저장하고 각 중첩 된 반복을 위해 그것을 걸릴 수 :

여기 내 시도이다.

function iter(path) { 
 
    path = path || []; 
 
    return function (o) { 
 
     o.path = path.concat(o.id); 
 
     if (o.children) { 
 
      o.children.forEach(iter(o.path)); 
 
     } 
 
    } 
 
} 
 

 
var tree = [{ id: 1, children: [] }, { id: 2, children: [{ id: 3, children: [] }] }]; 
 

 
tree.forEach(iter()); 
 
console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

는이 재귀를 사용하여 입력 데이터 배열 또는 일반 오브젝트 인 경우, 확인할 수있다.

Answer 3

var tree = [{ id: 1, children: [] }, { id: 2, children: [{ id: 3, children: [] }] }]; 
 

 
function paths(tree, parent = []) { 
 
    if (Array.isArray(tree)) { 
 
    tree.forEach(e => paths(e, parent)) 
 
    } else if (typeof tree == 'object') { 
 
    parent = parent.concat(tree.id) 
 
    tree.path = parent; 
 
    if (tree.children) paths(tree.children, parent) 
 
    } 
 
} 
 

 
paths(tree) 
 
console.log(tree)

당신은

루트 노드가 배열이지만, 다른 모든 노드가 객체있는 실수를했다. 이 솔루션은 stop writing data using literals이다 - -

이 루트 노드의 차이를 처리 할 프로그램이 일관성이없고 불필요하게 복잡하게하는 대신, 단지 몇 가지 간단한 데이터 생성자을 위

처럼 당신이 실수를하게되어있어 당신의 복잡성은 허공

const Node = (id, ...children) => 
 
    ({ id, children }) 
 

 
const PathNode = (id, path, ...children) => 
 
    ({ id, path, children }) 
 

 
const addPaths = ({id, children}, acc = []) => 
 
    PathNode (id, acc, children.map (child => 
 
    addPaths (child, [...acc, id]))) 
 
    
 
const tree = 
 
    Node (0, Node (1), 
 
      Node (2, Node (3))) 
 

 
console.log (tree) 
 
// { id: 0, children: [ 
 
// { id: 1, children: [ ] }, 
 
// { id: 2, children: [ 
 
//  { id: 3, children: [ ] } ] } ] } 
 

 
console.log (addPaths (tree)) 
 
// { id: 0, path: [ ], children: [ 
 
// { id: 1, path: [ 0 ], children: [ ] }, 
 
// { id: 2, path: [ 0 ], children: [ 
 
//  { id: 3, path: [ 0, 2 ], children: [ ] } ] } ] }