有没有办法在树上找到路径？

Question

假设我们有一棵下面的树。有没有给定2个节点找到连接它们的路径的算法。例如，给定（A，E）它将返回[A，B，E]，或者给定（D，G）它将返回[D，B，A，C，G]

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

Answer 1

您将需要一个树实现，其中子节点具有与其父节点的链接。

然后，对于两个节点，只需跟随父链接，就可以构建从节点到根的路径。

然后比较两条路径，从路径的末端（根在此处）开始：只要它们相同，就从两条路径中删除该公共节点。

最后，您剩下两条转移路径。反转第二条路径，并加入两条路径，将最后删除的节点置于两条路径之间。

这里是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);
}