Preorder 이진 트리 순회. vs가

Question

인 동안 나는 아래의 코드에서 if 대신에 사용할 때 콘솔 출력이 리프의 무한 루프에 걸리는 이유를 알아 내려고합니다. 예약 주문에 대한 재귀 함수가 잎에서 호출 될 때

void preOrder(Node root) { 
    Node n = root; 
    while(n != null) { 
     visit(n); 
     preOrder(n.left); 
     preOrder(n.right); 
     } 
    } 

는 잎 실행이 중지 더 왼쪽 child.Shouldn't이 없습니다.

Answer 1

while(n != null)을 가지고있을 때 null이 아닌 잠재적으로 무언가에 n을 재 할당하면 결코 무한 루프가 발생합니다.

if 문은 이미 재귀 호출을 가지고 있기 때문에 잎이 발견 될 때까지 당신이 나무를 통과 할,해야 할 것입니다 :

Node n = root; 
if (n != null) { 
    visit(n); 
    preOrder(n.left); 
    preOrder(n.right); 
} 

Answer 2

while(n != null)은 루프의 본문이 n의 값을 변경하지 않기 때문에 항상 true이거나 절대로 맞지 않습니다. 따라서 루프는 실행되지 않거나 무한합니다.

재귀를 사용하고 있으므로 루프가 필요하지 않습니다.

예약 주문에 대한 재귀 함수가 잎에서라고

void preOrder(Node root) { 
    Node n = root; 
    if (n != null) { 
     visit(n); 
     preOrder(n.left); 
     preOrder(n.right); 
    } 
} 

, 잎은 (더 왼쪽 실행이, preOrder(n.left)의 실행이 종료됩니다이

음을 중지 child.Shouldn't가 없습니다 n.left이 null이므로), 이전 preOrder 호출로 돌아가서 preOrder(n.right)으로 전화를 걸면 해당 호출이 종료되면 무한 while 루프에서 중단됩니다.