Как называется этот обход дерева?

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. Если у узла нет дочерних элементов, то pop и посещают все узлы из стека.

Ниже приведена реализация 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.

Answer 2

Я не знаю имени, но алгоритм может быть таким:

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');