DFS沒有內存的樹

我正在嘗試編寫一個函數來遍歷深度優先搜索的樹。DFS沒有內存的樹

我現在的算法進行類似：

If children 
go to first child 

If no children 
go to next sibling 

If no siblings 
go to parent

我遇到的問題是，我不能標記的樹節點被訪問了已經，所以當我去到父的週期只是重新設置，然後再次回到孩子身上，陷入循環。有沒有人有任何想法可以解決這個問題？

（它使用ANTLR插件是在Java）

編輯：

繼我寫這個的建議之一：

public void traverseTree(Tree tree){ 

    if (tree.getChildCount() > 0){ 
     tree = tree.getChild(0); 
     traverseTree(tree); 
     System.out.println(tree.toString()); 
    } 
    if (tree.getParent().getChild(tree.getChildIndex() + 1) != null){ 
     tree = tree.getParent().getChild(tree.getChildIndex() + 1); 
     traverseTree(tree); 
     System.out.println(tree.toString()); 
    } 
    if (!tree.getParent().toString().contains("ROOT_NODE")){ 
     tree = tree.getParent(); 
     traverseTree(tree); 
     System.out.println(tree.toString()); 
    } 
}

根節點爲根節點的名稱，但我收到堆棧溢出錯誤。任何人有任何想法爲什麼？

謝謝。

來源

2012-03-15 djcmm476

如果你不需要擔心週期或其他問題，那麼最簡單的方法就是像@PeterLawrey所建議的那樣使用遞歸方法。清潔和簡單。如果你不能使用遞歸，你仍然可以使用一個單獨的堆棧來維護相同的信息，包括返回的鏈接列表，如果節點沒有反向鏈接的話。 – 2012-03-15 15:46:05

會在這種情況下使用遞歸。

class Node { 
    public List<Node> getChildren() { .... } 

    public void traverse(Visitor<Node> visitor) { 
     // If children 
     // go to first child - by traversing the children first. 
     for(Node kid: getChildren()) 
      kid.traverse(visitor); 
      // If no children 
      // go to next sibling, - by continuing the loop. 

     visitor.visit(this); 
     // If no siblings 
     // go to parent - by returning and letting the parent be processed 
    } 
} 


interface Vistor<N> { 
    public void visit(N n); 
}

來源

2012-03-15 15:43:12

這看起來不錯，我不知道我100％理解它。你能解釋一下它在做什麼嗎？（對不起，我只是讀代碼非常糟糕）。 – djcmm476 2012-03-15 15:52:21

我已添加評論。您可能會發現在調試器中遍歷代碼以確切查看它在做什麼很有用。 – 2012-03-15 15:56:12

嗯，我試過把它寫在一個java文件中來理解它，但是我很難讓它運行，它不識別Visitor或getChildren（）（儘管我認爲我只需要改變它到奇怪的ANTLR格式）。 – djcmm476 2012-03-15 16:08:01

使用hash_table地圖中的每個頂點表示布爾無論我參觀與否

來源

2012-03-15 15:42:59

在樹形搜索中，這不是必需的。 – 2012-03-15 15:44:13

編寫一個深度優先的迭代器，用於在內部跟蹤訪問節點。這樣樹不需要改變就知道它正在被監視。

來源

2012-03-15 15:48:33 duffymo

如果「不記得」可以解釋爲O（1）內存，那麼改變可能會幫助：

記住不僅是當前節點，也是節點，在你
導線孩子們又來到只有當你不是來自其中一個人時

來源

2012-03-15 15:54:47 maxim1000

DFS沒有內存的樹

回答

相關問題