Есть ли способ найти путь в дереве? - PullRequest
Новая
       27

Есть ли способ найти путь в дереве?

0 голосов
/ 29 апреля 2020

Допустим, у нас есть дерево, подобное приведенному ниже. Есть ли алгоритм, который с учетом 2 узлов находит путь, который их связывает. Например, если (A, E) он вернет [A, B, E], или (D, G) он вернет [D, B, A, C, G] 

           A
         /   \
       B       C
      / \     / \
     D   E   F   G

1 Ответ

0 голосов
/ 30 апреля 2020

Вам понадобится реализация дерева, в которой дочерний узел имеет ссылку на своего родителя.

Затем для обоих узлов вы можете построить путь от узла до root, просто следуя инструкциям родительская ссылка.

Затем сравните два пути, начиная с концов путей (где root): пока они одинаковые, удалите этот общий узел из обоих путей.

Наконец, у вас есть два пути. Переверните второй и соедините два пути, поместив последний удаленный узел между ними.

Вот реализация в JavaScript: 

function getPathToRoot(a) {
    if (a.parent == null) return [a];
    return [a].concat(getPathToRoot(a.parent));
}

function findPath(a, b) {
    let p = getPathToRoot(a);
    let q = getPathToRoot(b);
    let common = null;
    while (p.length > 0 && q.length > 0 && p[p.length-1] == q[q.length-1]) {
        common = p.pop();
        q.pop();
    }
    return p.concat(common, q.reverse());
}

// Create the example tree
let nodes = {};
for (let label of "ABCDEFG") {
    nodes[label] = { label: label, parent: null };
}
nodes.B.parent = nodes.C.parent = nodes.A;
nodes.D.parent = nodes.E.parent = nodes.B;
nodes.F.parent = nodes.G.parent = nodes.C;

// Perform the algorithm
let path = findPath(nodes.E, nodes.G);

// Output the result
console.log("Path from E to G is:");
for (let node of path) {
    console.log(node.label);
}
...