Рекурсивных найти путь произвольного узла в дереве

Question

У меня есть дерево объектов, составленных со следующей структурой:

interface Node { 
    name: string; 
    children?: Node[]; 
} 

Где, например, { name: "foo", children: [ { name: "bar" } ] } является допустимым деревом. Я пытаюсь получить адрес произвольного узла, который может быть листом, возвращенным как массив пути для его получения, где узел будет сравниваться с помощью ссылки на объект. Пример дано, я иметь следующую структуру:

var data = { 
    name: "Languages", 
    children: [{ 
    name: "Functional", 
    children: [ 
     { name: "OCaml" }, 
     { name: "Haskell" }, 
     { name: "Erlang" } 
    ] 
    }, { 
    name: "Imperative", 
    children: [ 
     { name: "BASIC" }, 
     { name: "Clipper" } 
    ] 
    }] 
}; 

Ожидается, что, например, если у меня есть ссылка на OCaml хранится в переменной под названием ocaml, который указывает в точности этой ссылки в памяти, массив шагов возвращаться с путём для его достижения, что в данном случае будет [0, 0].

Я уже могу найти объект, но я не в состоянии сохранить предыдущий индекс, так как это не является детерминированным:

var tree = function(struct, cmp) { 
    if (struct.children) { 
    var lookup = []; 
    for (var i = 0; i < struct.children.length; i++) { 
     lookup.push(tree(struct.children[i], cmp)); 
    } 
    return lookup; 
    } else { 
    if (struct === cmp) { 
     return "PASS"; 
    } 
    return "FAIL"; 
    } 
} 

я могу найти элемент, но как я могу сохранить предыдущий индексы, чтобы достичь его с базы?

Answer 1

Попытка отслеживать пути в локально-контекстном переменном не будет работать, поскольку каждый рекурсивный вызов создает новую область. Предполагая, что вам нужно что-то очень похожее, что у вас уже есть, довольно небольшое изменение заключается в том, чтобы путь поиска индексов был возвращаемым значением из метода. Базовый регистр рекурсивного вызова (когда нет дочерних узлов) возвращает [] (найдено) или null (не найдено).

var tree = function(struct, cmp) { 
    if (struct === cmp) { 
     // `cmp` is found at current `struct`. 
     return []; 
    } else if (struct.children) { 
     for (var i = 0; i < struct.children.length; i++) { 
      var path = tree(struct.children[i], cmp); 
      if (path !== null) { 
       // `cmp` is found at `path` in `struct.children[i]`, 
       // so prefix `i` to `path` to get the path in `struct`. 
       path.unshift(i); 
       return path; 
      }   
     } 
    } 
    // `cmp` not found in this branch of the tree. 
    return null; 
}; 

console.log(tree(data, data.children[0].children[0])); // outputs [0, 0] 
console.log(tree(data, data.children[0].children[2])); // outputs [0, 2] 
console.log(tree(data, data.children[1].children[1])); // outputs [1, 1] 

Answer 2

Я завернул data в массив. Для всех узлов, вы можете хранить ссылки на объект как

var lookUp = { 
    'OCaml':getNode(data, 'OCaml'), 
    'BASIC': getNode(data, 'BASIC') 
}; 

Или вы можете создать ссылку с прогулки через объект.

var data = [{ 
 
    name: "Languages", 
 
    children: [{ 
 
     name: "Functional", 
 
     children: [ 
 
      { name: "OCaml" }, 
 
      { name: "Haskell" }, 
 
      { name: "Erlang" } 
 
     ] 
 
    }, { 
 
     name: "Imperative", 
 
     children: [ 
 
      { name: "BASIC" }, 
 
      { name: "Clipper" } 
 
     ] 
 
    }] 
 
}]; 
 

 
function getNode(array, name) { 
 

 
    function findNode(a, i, o) { 
 
     if (a.name === name) { 
 
      node = o[i] 
 
      return true; 
 
     } 
 
     return Array.isArray(a.children) && a.children.some(findNode); 
 
    } 
 

 
    var node; 
 
    array.some(findNode); 
 
    return node; 
 
} 
 

 
var lookUp = { 
 
    'OCaml':getNode(data, 'OCaml'), 
 
    'BASIC': getNode(data, 'BASIC') 
 
}; 
 

 
lookUp.BASIC.name = 'Basic'; 
 
document.write('<pre>' + JSON.stringify(data, 0, 4) + '</pre>');