재귀를 제대로 이해하려면 정말 당신의 도움이 필요합니다. 기본 재귀와 피보나치와 같은 논리를 이해할 수 있습니다.
int factorial(int n)
if(n <=1)
return n
else
return(n*factorial(n-1))
함수 n
가 0이 될 때까지 계승을 계속 호출 하고 마지막으로 모든 결과를 곱하는 것은 쉽습니다 . 하지만 트리 순회와 같은 재귀는 이해하기 어렵습니다.
void inorderTraverse(Node* head)
if(head!=NULL){
inorderTraverse(head->left)
cout << head-> data
inorderTraverse(head->right)
}
}
여기서는 첫 번째 재귀 호출이 함수로 돌아가는 경우이 함수가 어떻게 작동하는지 논리를 잃어 버렸습니다. 어떻게 cout 라인으로 갈 수 있는지 또는 어떻게 올바른 자식 데이터를 표시 할 수 있습니까? 정말 당신의 도움이 필요합니다.
감사합니다
알파벳 순서의 이진 검색 트리 :
B
/ \
A C
inorderTraverse(&A)
먼저 내려 가서 A
인쇄 (하위 트리를 재귀 적으로 인쇄) 한 다음 인쇄 B
한 다음 내려 가서 C
인쇄합니다 (하위 트리를 재귀 적으로 인쇄).
따라서이 경우 A B C
. 더 복잡한 트리의 경우 :
D
/ \
B E
/ \
A C
이것은로 인쇄됩니다 A B C D E
. 원래 트리가의 왼쪽에 D
있으므로 전체가 먼저 인쇄됩니다. 문제는 시작 문제의 더 작은 인스턴스로 축소됩니다. 이것이 재귀의 본질입니다. 다음은 D
오른쪽에, 다음 모든 인쇄 D
(단지이다 E
).
이 구현에서 노드는 부모에 대해 알지 못합니다. 재귀는이 정보가 호출 스택에 저장됨을 의미합니다. 당신은 반복적 인 구현에 모든 것을 대체 할 수있는,하지만 당신은 다시 이동을 추적하기 위해 일부 스택과 같은 데이터 구조를 필요 까지 트리를.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다