ツリー内の各ノードへのパスを再帰的に構築する方法 - JavaScript？

Question

私のデータ構造は次のようになります。

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

1つのブランチ上のノードや子供の数に制限はありません。

私の目標は、すべてのノードへのパスを構築することです。例えば、IDの

：2私はそれは次のように変更されますので、アルゴリズムによって、私のツリーを実行したい1> 2

のパスを持っています：3は1> 2> 3 IDのパスを持っていますこの：

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にある - あなたは、あなたが代わりに

上で行ったようにミスを犯すためにバインドされている、ちょうどいくつかの簡単なデータ構築を行い、あなたの複雑さは、なぜ開始時 ` '1'`のID = 2経路を有する

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