2017-02-23 7 views
1

У меня есть дерево, как это:Как вычислить путь к дочернему узлу в дереве?

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 []; 
    }, []); 
} 

Я думаю, что функция должна строить путь во время прохождения, тогда, если он достигает листа, не найдя узел, удалите только ту часть этого пути, которая принадлежала ветке, где узел не был найден, затем продолжите с другими ветвями ,

+1

Вы пробовали обучения/с использованием рекурсии? – gyre

+0

Я отредактировал мой вопрос, чтобы включить то, что я пробовал до сих пор. Да, это определенно работа для рекурсии, с которой я обычно справлялся, но эта задача для меня намного сложнее. – silvenon

ответ

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);

+0

Количество кода для этого действительно впечатляет. – silvenon

+0

@silvenon, слишком много? –

+0

Нет, очень мало, вот почему это впечатляет. :) – silvenon

Смежные вопросы