ツリー内の子ノードへのパスを計算する方法は？

Question

私はこのような木き：このツリーの

var tree = [ 
    { 
    type: "folder", 
    children: [ 
     { 
     type: "folder", 
     children: [ 
      { 
      type: "document", 
      id: 1, 
      children: [] 
      } 
     ] 
     } 
    ] 
    }, 
    { 
    type: "folder", 
    children: [] 
    } 
]; 

葉は常に空childrenの配列を持っています。

インデックスのパスを与えられた条件を満たすノードに返す関数を構築する必要があります。

getPathToNode(tree, function (node) { 
    return node.type === "document" && node.id === 1; 
}) 

し、以下を返します：

[0, 0, 0] 

そのノードへのパスを記述する：

tree[0].children[0].children[0] 

この再帰関数は、私が得たものである機能は、このように呼ばれますこれまで：

function getPathToNode(tree, fn) { 
    return tree.reduce(function (path, node, i) { 
    if (fn(node)) { 
     return path.concat(i); 
    } 
    if (node.children.length > 0) { 
     const pathToNode = getPathToNode(node.children, fn); 
     return pathToNode.length > 0 ? path.concat(i, pathToNode) : []; 
    } 
    return []; 
    }, []); 
} 

私は関数が通過中にパスを構築する必要があると思います。ノードを見つけずにリーフに到達すると、ノードが見つからなかったブランチに属するそのパスの部分だけを削除し、他のブランチ。

Answer 1

この提案では、反復が早期に終了する可能性があるため、Array#someが使用されています。

次に、レベルと必要なインデックスに変数を使用できます。

function getPathToNode(node, fn) { 
 
    var path = []; 
 
    return node.some(function iter(level) { 
 
     return function (a, i) { 
 
      path.length = level; 
 
      path[level] = i; 
 
      return fn(a) || a.children.some(iter(level + 1)); 
 
     }; 
 
    }(0)) && path; 
 
} 
 

 
var tree = [{ type: "folder", children: [{ type: "folder", children: [{ type: "document", id: 1, children: [] }] }] }, { type: "folder", children: [] }], 
 
    result = getPathToNode(tree, function (node) { 
 
     return node.type === "document" && node.id === 1; 
 
    }); 
 

 
console.log(result);

代わりレベルの一時的な配列を持つ別のバージョン。

function getPathToNode(node, fn) { 
 
    var path = []; 
 
    return node.some(function iter(p) { 
 
     return function (a, i) { 
 
      if (fn(a)) { 
 
       path = p.concat(i); 
 
       return true; 
 
      } 
 
      return a.children.some(iter(p.concat(i))); 
 
     }; 
 
    }([])) && path; 
 
} 
 

 
var tree = [{ type: "folder", children: [{ type: "folder", children: [{ type: "document", id: 1, children: [] }] }] }, { type: "folder", children: [] }], 
 
    result = getPathToNode(tree, function (node) { 
 
     return node.type === "document" && node.id === 1; 
 
    }); 
 

 
console.log(result);