algorithm - 这个树遍历叫什么？

Question

给定一棵在根部有A的树

A 
+-- B 
|   +-- C
|   +-- D
+-- E 
    +-- F
    +-- G 

我希望遍历是

C,B,A,D,F,E,G

可以从叶子到根的所有路径开始构造

C,B,A
D,B,A
F,E,A
G,E,A

然后删除所有已经遇到的节点

C,B,A
D
F,E
G

这个遍历有名字吗？

Answer 1

我不认为它有一个名字。正如您所定义的，它不仅限于二叉树(与“有序”不同)，而且可以用于 n 叉树。

与另一个答案一样，我将在此处提供递归实现，但使用单个堆栈:

1. 将给定的节点放入栈中
2. 如果节点有子节点，则对每个子节点递归应用此例程
3. 如果该节点没有子节点，则弹出并访问堆栈中的所有节点。

下面是该算法的 JavaScript 实现，它将在下图上运行:

           a 
        /     \
      r         e
    / | \     / | \
   G  h  N   d  i  t  
      |     / \    |
      p    o   L   s

预期的遍历将按以下顺序列出节点:“GraphNodeList”

function traverse(adjacency, id, visit, stack=[]) {
    stack.push(id);
    if (adjacency[id]) {
        for (let child of adjacency[id]) traverse(adjacency, child, visit, stack);
    } else {
        while (stack.length) visit(stack.pop());
    }
}

// Example run
let adjacency = { a: 're', r: 'GhN', h: 'p', e: 'dit', d: 'oL', t: 's' };
traverse(adjacency, 'a', console.log); // log each visited node to console.