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

Question

假设我们有一棵如下图所示的树。是否有一种算法可以给定 2 个节点找到连接它们的路径。例如，给定 (A,E) 它将 return [A,B,E]，或者给定 (D,G) 它将 return [D,B,A,C,G]

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

Answer 1

您将需要一个树实现，其中子节点与其父节点有 link。

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

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

最后给你留下两条岔路。反转第二个，加入两条路径，将最后删除的节点放在两者之间。

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

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

Is there a way to find a path in a tree?

algorithm

tree

pseudocode