깊이있는 첫 번째 문제를 재귀 적으로 가로 지르다

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 메소드를 이동합니다.