如何在java二叉树上实现深度优先搜索(DFS)

Question

根据维基百科文章中关于深度优先搜索的解释，我认为二叉树上的DFS与预先顺序遍历根相同——从左到右(我对吗?)

但是我只是做了一点搜索，得到了这段代码，这段代码的作者声称DFS需要一个树来记录节点之前是否被访问过(或者在图的情况下我们需要这个吗?)

// copyright belongs to the original author 
public void dfs() {
    // DFS uses Stack data structure
    Stack stack = new Stack();
    stack.push(this.rootNode);
    rootNode.visited=true;
    printNode(rootNode);
    while(!stack.isEmpty()) {
        Node node = (Node)s.peek();
        Node child = getUnvisitedChildNode(n);
        if(child != null) {
            child.visited = true;
            printNode(child);
            s.push(child);
        }
        else {
            s.pop();
        }
    }
    // Clear visited property of nodes
    clearNodes();
}

有人能解释一下吗?

Answer 1

是的，它是预订的。但是，我不喜欢说它是遍历因为你可能不遍历树，你只要找到你的元素就会停止。你输出的程序不是一个搜索，而是一个遍历:你输出了所有的东西。在二叉树中搜索的搜索函数是:

public boolean search(Tree t, int i) {
    if(t == null)
        return false;
    elif(t.value() == i)
        return true;
    else
        for(child in t.children()) {
            if(search(child,i))
                return true;
        }
        return false;
        //return search(t.leftTree(), i) or search(t.rightTree(),i) binary tree case
}

Answer 2

我认为二叉树上的dps与预先顺序遍历根—左—右相同。(我说的对吗?)

深度优先搜索可以是前序、中序或后序遍历。您不需要堆栈:递归地实现它更容易，在这种情况下，您也不需要将节点标记为已访问。