遞歸深入遍歷一棵樹第一個問題

Question

我想用ANTLR樹命令和遞歸遍歷一棵樹。我現在的代碼是：

public void traverseTree(Tree tree){ 
     int counter = 0; 
     System.out.println(tree.toString()); 
     if (tree.getChildCount() > 0 && tree.getChild(0) != null){ 
      System.out.println(tree.toString() + counter++); 
      tree = tree.getChild(0); 
      traverseTree(tree); 

     } 
     while (tree.getParent().getChild(tree.getChildIndex() + 1) != null){ 
      System.out.println(tree.toString() + counter++); 
      tree = tree.getParent().getChild(tree.getChildIndex() + 1); 
      traverseTree(tree); 

     } 
    } 

但是，它不工作。我在樹中獲得了很多條目，但是沒有明顯的順序。任何人都可以看到我要去哪裏嗎？

謝謝。

編輯：

評論我低於發應該是在這裏開始：

對不起，我應該取出的打印報表，他們就在那裏嘗試和調試。我遇到的問題是，它應該只搜索它開始的節點以及該節點的所有兄弟節點，它不應該升級，但它會打印所有內容。 （我會把它編入主文件，應該在那裏開始，對不起）。

我設法得到的代碼工作，最終像這樣：

public void traverseTree(Tree tree){ 
     System.out.println(tree); 
     if (tree.getChild(0) != null){ 
      traverseTree(tree.getChild(0)); 
     } 
     if(tree.getParent().getChildCount() > 1){ 
      if(tree.getParent().getChild(tree.getChildIndex() + 1) != null) 
      traverseTree(tree.getParent().getChild(tree.getChildIndex() + 1)); 
     } 
    } 

Answer 1

確保永不升級的最簡單方法是確保您永遠不會撥打getParent()。如果你不知道有一個較高的水平，你不能去那裏。

public void traverseTree(Tree tree) { 

    // print, increment counter, whatever 
    System.out.println(tree.toString()); 

    // traverse children 
    int childCount = tree.getChildCount(); 
    if (childCount == 0) { 
     // leaf node, we're done 
    } else { 
     for (int i = 0; i < childCount; i++) { 
      Tree child = tree.getChild(i); 
      traverseTree(child); 
     } 
    } 
} 

遞歸的要點是你不需要回去。當此級別的traverseTree()完成時，上一級的循環將繼續到下一個兄弟。

（請注意，if實際上並不是必須的，除非當你到達葉節點時你想做一些特殊的事情，我只是把它放在那裏，所以評論會使它明白髮生了什麼事情，從概念上講，它總是一個遞歸中的好主意，通過確定如何知道何時停止遞歸來開始。）

Answer 2

試試這個：

int counter = 0; 
public void traverseTree(Tree tree) { 

    for (int i=0; i<tree.getChildCount(); i++) { 
     Tree child = tree.getChild(i); 
     System.out.println(tree.toString() + counter++); 
     traverseTree(tree); 
    } 
} 

Answer 3

它看起來像你打印出相同的節點幾次。如果你只是想爲你去到打印出來的節點，

1 
2 3 
4 5 6 

Depth first - 1 2 4 5 3 6 
Breadth first - 1 2 3 4 5 6 

//For depth first 
public void traverseTree(Tree tree){   
    System.out.println(tree.toString()); 
    for (int x = 0; x < tree.getChildCount(); x++) 
     traverseTree(tree.getChild(x)); 
} 

要切換到4 5 6 2 3 1，只需移動的println後for循環。