使用DFS打印树的完整遍历

Question

我正在尝试从根节点开始打印图形的遍历，向下到图形再返回到根节点。例如，如果这是图形：

          0             
         /
        1
       / \
      3   4
     / 
    2   

我要打印：0、1、3、2、3、1、4、1、0

我当前正在使用DFS打印0、1、3、2、4。如何修改我的算法以打印回溯？

DFS代码：

def dfs(graph, start, visited=None):
if visited is None:
    visited = set()
visited.add(start)
print(start)
for next in graph[start] - visited:
    dfs(graph, next, visited)
return visited

Answer 1

假设您具有parent: children[]对这样的数据结构。然后，您可以解决以下问题：

const ROOT = 0;
const tree = {
    /* parent: children[] */
    [ROOT]: [1],
    1: [3, 4],
    3: [2],
    4: [],
    2: []
};

const pathStack = [];

pathStack.peek = () => pathStack[pathStack.length - 1];
pathStack.push(ROOT);

const traverse = () => {
    const node = pathStack.peek();

    if (node == null) { // if path is over, stop
        return;
    }

    console.log(node); // print the node

    const children = tree[node];

    if (!children.length) { // if children doesn't exist, go to its parent
        pathStack.pop();
        traverse();

        return;
    }

    const child = tree[node].shift();

    pathStack.push(child); // go to its child
    traverse();
};

traverse();

我不知道您使用的语言。所以我用了JS。我认为您可以在上述解决方案中获得算法的核心思想。