这个树遍历叫什么？

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

我不知道名字，但算法可以是这样的：

half-explore:
    inorder style (I mapped the first "read" element to be the left)
    except for the right node: push it to a FIFO

whenever _half-explored_ some node, get the right node to explore from FIFO and half-explore it

  /*
  A 
  +-- B 
  |   +-- C
  |   +-- D
  +-- E 
      +-- F
          +--H
          +--I
      +-- G 
   */
  let m = [];
  m['A'] = ['B','E'];
  m['B'] = ['C','D'];
  m['E'] = ['F','G'];
  m['F'] = ['H','I'];
  function main(id){
      function leftdfs(id, queue=[]){
          if(m[id]){
              leftdfs(m[id][0], queue);
              console.log(id);
              queue.push(m[id][1]);
          }else{
              console.log(id);
          }
      }
      let queue = [id];
      while(queue.length){
          let id = queue.shift();
          leftdfs(id, queue)
      }
  }
  //CBADHFEIG
  main('A');

Answer 2

我不认为它有一个名字。正如你所定义的，它不仅限于二叉树（不像"in-order"），而且可以用于n叉树。

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

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

下面是该算法的 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.

这个树遍历叫什么？

What's this tree traversal called?

algorithm

tree

tree-traversal