재귀가 나무를 가로 지르는 방법은 무엇입니까

Question

java version "1.8.0_92" 

저는 나무를 연구하고 재귀를 사용하여 나무를 탐색하는 방법을 배우고 있습니다. 그러나 나는 그것에 대해 혼란 스럽다.

public void preOrder(BinaryTree root) { 
     if(root != null) { 
      System.out.println(root); 
      preOrder(root.leftChild); <-- this gets called and will start from the top of the function 
      preOrder(root.rightChild); <-- how can this get called if the top one will always calls itself? 
     } 
    } 

나는 두 번째가 실행되지 않습니다 때문에 호출이 위에서 항상 자신을 호출로 두 번째 선주문이 호출되지 얻을 않을 것이라고 생각합니다.

Answer 1

아니요.은 항상 자체를 호출합니다. 그것은 leftChild가 null이 될 때까지 계속됩니다. 그런 다음 아무것도 수행하지 않고 실행이 반환됩니다.이 작업은 한 수준을 백업하고 가장 낮은 수준의 상위 노드의 rightChild에서 반복됩니다. 해당 호출에도 하위 노드가 없어지면이 최하위 수준의 부모 노드를 처리하지 못하고 호출이 다시 백업되고 전체 트리가 통과 될 때까지 의 rightChild 노드가 노드가됩니다.

Answer 2

root.leftChild이 null이되면 (즉, 트리의 리프를 얻을 때) preOrder은 preOrder(null)과 같이 호출됩니다. 이 경우 조건은 false으로 평가되고 순환 되감기 및 중지는 preOrder(root.rightChild)이 평가됩니다. 여기

는 (스칼라) 전화 추적 : 당신은 당신이 원하는 정보를 찾을 때까지의

case class BinaryTree(nodeName: String, leftChild: Option[BinaryTree], rightChild: Option[BinaryTree]) { 
    def preOrder(root: Option[BinaryTree], depth: Int = 0) { 
     root match { 
      case Some(root) => { 
       println(" " * depth + root.nodeName) 
       preOrder(root.leftChild, depth+4) 
       preOrder(root.rightChild, depth+4) 
      } 
      case None => println(" " * depth + "leaf") 
     } 
    } 
} 


val tree = new BinaryTree(
    "root", 
    Some(new BinaryTree(
     "a", 
     Some(new BinaryTree("aa", None, None)), 
     Some(new BinaryTree("ab", None, None)))), 
    Some(new BinaryTree(
     "b", 
     Some(new BinaryTree("ba", None, None)), 
     Some(new BinaryTree("bb", None, None))))) 


tree.preOrder(Some(tree)) 

root 
    a 
     aa 
      leaf 
      leaf 
     ab 
      leaf 
      leaf 
    b 
     ba 
      leaf 
      leaf 
     bb 
      leaf 
      leaf 

Answer 3

생각해 그런 다음 다시 닫 가야, 개방으로 문의 전체 무리가 있습니다/다른 것들을 확인하십시오.

public void preOrder(BinaryTree root) { 
    if(root != null) { 
     System.out.println(root); 
     preOrder(root.leftChild); <-- this gets called and will start from the top of the function 
     preOrder(root.rightChild); <-- how can this get called if the top one will always calls itself? 
    } 
} 

우리는 예약 주문을 대체 할 수는처럼 보이도록 일치하는 코드를 호출

public void preOrder(BinaryTree root) { 
    if(root != null) { <-- note the if check 
     System.out.println(root); 

     if(root.leftChild!= null) { <-- note the if check 
      System.out.println(root.leftChild.leftChild); 
      preOrder(root.leftChild.leftChild); <- this expands into another if block 
      preOrder(root.leftChild.rightChild); <- this also expands 
     } 

     if(root.rightChild!= null) { <-- note the if check 
      System.out.println(root.rightChild.leftChild); 
      preOrder(root.rightChild.leftChild); 
      preOrder(root.rightChild.rightChild); 
     } 

    } 
} 

재귀를 중지하는 조건 경우 특별한 "기본"을 칠 때까지 ... 바깥쪽으로 확장 유지합니다. 이 경우 트리의 리프 노드, 즉 node == null을 찾았을 때 if 조건문이 더 이상 true가 아니며 모든 것이 자체적으로 축소되기 시작했거나 확장 할 수 없기 때문에 확장을 중지합니다. 코드 블록을 정상적으로 계속 실행하십시오.

Answer 4

방금 ​​배우기 시작하면 재귀가 혼동스러워 보일 수 있습니다. 첫째, 하위 문제를 생각할 수 있습니다. preOder의 경우 항상 루트 노드를 출력하고 왼쪽 노드와 오른쪽 노드를 출력합니다. 하위 문제를 해결하기 만하면됩니다. (아래 기본 간단한 트리) 이제

 root 
    / \ 
    left right 
/  \ 
...  ... 

코드를 살펴 돌아가 :

if(root != null) { 
    System.out.println(root); 
    preOrder(root.leftChild); // the left node now becomes another root, and keep making the next left node root until the next left node is null. 
    preOrder(root.rightChild); // this line of code won't be executed until the last preOrder function call its root == null(hit the condition.) 
} 

신뢰 재귀; 당신의 상태가 맞으면 항상 나머지 부분을 할 것입니다. 더 나은 이해를 위해 디버그 모드를 실행하는 데 동의합니다. 코드 작동 방식을 이해하려고 할 때 "단계별 사용"방법을 익히는 것이 매우 유용합니다.