이 재귀 함수를 추적하는 방법?

나는 이진 검색 트리에 요소를 추가하기위한이 자바 재귀 프로그램을 발견했다 : 그것은 끝에 N을 반환 한 후 다시 뿌리를 할당하는 이유를 이해하지 못하는 것을이 재귀 함수를 추적하는 방법?

public void add(int e){ 
    root=add(root, e); 
} 
public Node add(Node n, int e){ 
    if (n==null){ 
     n=new Node(e); 
    } else { 
     if (e<n.elem){ 
      n.left=add(n.left,e); 
     } else{ 
      n.right=add(n.right,e); 
     } 
    } 
    return n; 
}

입니다. 도움이 되었습니까?

출처

2016-06-17 Little

왼쪽과 오른쪽에 대한 재귀 호출이 끝나면 끝에있는 return n 문이 호출됩니다. 재귀를 다루는 튜토리얼 (또는 교과서)을 검토해야합니다. –

이것을 이해하는 가장 좋은 방법은 연필과 종이로 처리하고 빈 나무로 시작하는 것입니다. 그런 다음 코드를 추적하여 2, 4, 1 및 5 값을 추가하십시오.'root'는 첫 번째 호출에서만 실제 트리 루트를 참조합니다. 그 후, 하나 이상의 레벨이 내려 가면'root'는 현재 서브 트리의 루트를 참조합니다. –

할당 이유는 Java가 매개 변수를 전달하는 한 가지 방법 (값 기준) 만 가지고 있기 때문입니다.

root에 대한 참조는 add 값으로 전달됩니다. 그러나 add은 루트로 전달 된 노드를 수정해야합니다. 예를 들어 첫 번째 노드를 트리에 추가하면 root의 값은 null이지만 노드를 추가 한 후에는 null이되어야합니다.

이 제한 사항을 해결하는 관용구는 수정 된 값을 반환하는 메서드를 만들어 매개 변수에 다시 할당하는 것입니다. if (n==null) n=new Node(e); : 그것은 당신이 재귀를 이해하려는 경우 add 방법은 여기

root=add(root,e);

여기

n.left = add(n.left, e); 
n.right = add(n.right, e);

출처

2016-06-17 01:26:46 dasblinkenlight

알고리즘의이 버전이 더 잘 고려 되었습니까? 아니면 다음 단계의 순환을 거치기 전에 null을 확인하고 그에 따라 행동하겠습니까? – HopefullyHelpful

@HopefullyHelpful 당신은 할당없이 할 수있다. 그러나 최상위 레벨'void add '와 조건부의 두 가지 브랜치를'null '체크해야한다. 반면에이 구현은 단일 'null'체크를 가지고 있으므로 더 짧습니다. – dasblinkenlight

을 무엇을하고 있는지, 당신은 그것을 종료 조건을보고해야합니다.

즉, Node n이 null 일 때 마지막 통화가됩니다. 그게 언제있을거야? 잎 중 하나에서. 그런 다음에 만 트리에 추가 된 다른 오브젝트가 작성됩니다.

그 후에는 return n의 논리에만 해당합니다. 마지막 호출 후 n은 new Node(e)입니다. 누가 새로운 Node에게 배정 될 것입니까? 일부 (이전) 잎의 n.left 또는 n.right. 스택에서 메소드 add에 대한 첫 번째 호출이 도달 할 때까지 동일한 로직이 트리를 형성합니다. 그러면 원하는 최종 제품인 완전히 업데이트 된 트리가 반환됩니다.

출처

2016-06-17 01:33:51 MaxG

이 재귀 함수를 추적하는 방법?

답변

관련 문제