이진 트리 구조에서의 스택 프레임 (feat 재귀함수)

이진 트리 구조에서의 스택프레임 

이진트리의 규칙

노드는 왼쪽부터 오른쪽의 순으로, 상위 노드부터 하위 노드의 순으로 생성이 된다

노드에 도착만 하다: 하위 트리를 순회

노드에 방문한다: 해당 노드를 출력(print)

	전위 순회 (preorder)	중위 순회 (inorder)	후위 순회 (postorder)
순회 순서	NLR 순으로 노드 방문 (노드 -> 왼쪽 -> 오른쪽)	LNR 순으로 노드 방문 (왼쪽 -> 노드 -> 오른쪽)	LRN 순으로 노드 방문 (왼쪽 -> 오른쪽 -> 노드)
특징	>> print(n.item) >> if n.left >> if n.right	>> if n.left >> print(n.item) >> if n.right	>> if n.left >> if n.right >> print(n.item)
적용	디렉토리의 하위 디렉토리를 포함한 파일 복사		계산기

이진 트리 구조의 형태

특징: 노드의 생성은 왼쪽에서 오른쪽으로, 부모노드에서 자식노드로의 순서를 가지게 된다.

[완전 이진 트리 구조]

# 전위 순회 코드

def preorder(self, n):
    if n != None:
    print(str(n.item), ' ', end-='')
    if n.left:
    self.preorder(n.left)
    if n.right:
    self.preorder(n.right)
 
t.preorder(t.root)

가장 헷갈렸던 것이 재귀함수에 대한 정확한 이해가 안됐었는지,

Node D 까지 방문을 한 이후 -> 다시 부모노드인 B Node 로 어떻게 올라가는지가 혼동스러웠다.

결론적으로는 스택프레임의 가장 상위에 push 된 Node D 함수를 순회 방문하며 pop 이 된 이후 스택에 남아있는 Node B 의 함수 처리를 진행하는 것이었다.

(즉, 맨 마지막 D 노드의 방문이 끝나면 preorder(B) 의 함수가 실행되어 self.preorder(n.right) 가 실행)