如何在java中的二叉樹上實現深度優先搜索（DFS）？

根據the wikipedia article about depth-first search中的解釋，我認爲二叉樹上的DFS與先前遍歷的根 - 左 - 右（我是對嗎？）完全相同。如何在java中的二叉樹上實現深度優先搜索（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(); 
}

有人能解釋這個嗎？

來源

2013-03-06 Accessdenier

我認爲二叉樹的dps是同一個與前序遍歷根 - 左 - 右（是嗎？）

深度優先搜索可預先在 - 或者後序遍歷。您不需要堆棧：遞歸實現它更容易，在這種情況下，您不需要將節點標記爲已訪問。

來源

2013-03-06 01:40:33 EJP

您可以在此鏈接（http://en.wikipedia.org/wiki/Depth-first_search）右側檢查圖像嗎？ – Accessdenier 2013-03-06 01:47:23

是的，它是預先訂購的。但是，我不想說它是遍歷的，因爲你可能不會遍歷樹，只要你找到你的元素就停下來。您打印的程序不是搜索，而是遍歷：您正在打印所有內容。在二叉樹中搜索的搜索功能是：

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 
}

來源

2013-03-06 01:57:03

，使感官，順便說一句，如果你想dfs樹（而不是二叉樹）？ – Accessdenier 2013-03-06 02:27:41

我修改了普通樹的答案。 – 2013-03-06 06:45:49

如何在java中的二叉樹上實現深度優先搜索（DFS）？

回答

相關問題