부산대학교자료구조
Scientific Inference Lab

When Do We Visit the Root

Tree Traversals

같은 트리를 네 가지 순서로 방문하고 스택·큐와 parse tree로 추적한다.

문제 1

세 가지 재귀 순서

문제 1~3은 다음 이진트리를 쓴다. 괄호는 (왼쪽 부분 트리, 오른쪽 부분 트리)이고 -는 빈 자식이다.

M(H(C, K(J, -)), T(-, W))
  1. 전위, 중위, 후위 순회의 방문 순서를 각각 적는다.
  2. 세 재귀 함수에서 위치만 달라지는 문장을 적는다.
  3. 노드마다 자기 부분 트리의 노드 수를 계산하려면 세 순서 가운데 무엇이 알맞은지 적고 이유를 설명한다.
해설 펼치기
  1. 전위: M, H, C, K, J, T, W. 중위: C, H, J, K, M, T, W. 후위: C, J, K, H, W, T, M.
  2. visit(tree.key)다. 두 재귀 호출보다 앞(전위), 사이(중위), 뒤(후위)에 둔다.
  3. 후위 순회다. 왼쪽·오른쪽 부분 트리의 결과가 있어야 부모 노드의 노드 수를 계산할 수 있으므로 루트를 마지막에 처리한다.
문제 2

스택으로 전위 순회하기

문제 1의 이진트리를 쓴다.

루트를 스택에 넣고, pop한 노드를 방문한 뒤 오른쪽 자식 노드를 먼저, 왼쪽 자식 노드를 나중에 push한다.

  1. 각 pop 뒤에 push한 노드와 스택 상태(맨 위부터)를 끝까지 적는다.
  2. 왼쪽 자식 노드를 먼저 push하면 방문 순서가 어떻게 되는지 적는다.
  3. 명시적 스택이 재귀 호출에서 무엇을 대신 저장하는지 적는다.
해설 펼치기
  1. M: T, H push → [H, T]. H: K, C push → [C, K, T]. C → [K, T]. K: J push → [J, T]. J → [T]. T: W push → [W]. W → []. 방문 순서는 M, H, C, K, J, T, W로 재귀 전위 순회와 같다.
  2. LIFO라 오른쪽 자식을 먼저 방문해 M, T, W, H, K, J, C가 된다.
  3. 아직 처리하지 않은 오른쪽 부분 트리처럼 나중에 할 일을 저장한다. 재귀에서는 호출 스택이 이 대기 상태를 보관한다.
문제 3

큐로 레벨 순회하기

문제 1의 이진트리를 쓴다.

  1. 루트를 큐에 넣고 꺼낸 노드를 방문한 뒤 왼쪽, 오른쪽 자식 노드를 차례로 넣을 때 각 단계의 큐(앞쪽부터)와 방문 순서를 적는다.
  2. 깊이별로 방문 노드를 묶는다.
  3. 자식 노드를 오른쪽 먼저 넣으면 방문 순서가 어떻게 되는지 적는다.
  4. 스택과 큐가 만드는 방문 순서의 차이를 한 문장으로 적는다.
해설 펼치기
  1. M → [H, T], H → [T, C, K], T → [C, K, W], C → [K, W], K → [W, J], W → [J], J → []. 방문 순서는 M, H, T, C, K, W, J다.
  2. 깊이 0: M. 깊이 1: H, T. 깊이 2: C, K, W. 깊이 3: J.
  3. M, T, H, W, K, C, J다. 같은 깊이를 오른쪽부터 방문한다.
  4. 스택은 방금 넣은 자식 쪽으로 깊이 들어가고, 큐는 먼저 넣은 얕은 노드를 먼저 내보내 깊이가 감소하지 않는 순서를 만든다.
문제 4

parse tree로 식 다루기

식 ((8 − 2) × (1 + 3))의 parse tree를 쓴다.

  1. 루트와 두 부분 트리의 루트, 단말 노드를 적는다.
  2. 후위 순회로 값을 계산하는 과정을 적고 결과를 구한다.
  3. 중위 순회로 괄호를 함께 출력한 결과를 적고, 괄호를 빼면 어떤 문제가 생기는지 적는다.
  4. 식 (3 + (4 × 5))를 읽으며 트리를 만들 때 자식 노드로 내려가기 전에 스택에 무엇을 push하는지 적는다.
해설 펼치기
  1. 루트는 ×, 왼쪽 부분 트리의 루트는 −, 오른쪽은 +다. 단말 노드는 8, 2, 1, 3이다.
  2. 8, 2를 처리한 뒤 − 로 6, 1, 3을 처리한 뒤 + 로 4, 마지막에 × 로 6 × 4 = 24다.
  3. 강의의 print_exp는 빈 트리에 빈 문자열을 돌려주므로 수에도 괄호가 붙어 (((8)-(2))*((1)+(3)))로 출력된다. 수의 괄호를 뺀 ((8−2)×(1+3))도 같은 계층을 나타내므로 맞는 답으로 본다. 괄호가 없으면 8−2×1+3처럼 출력되어 연산 우선순위와 계산 순서를 잃는다.
  4. 현재 노드를 push한다. 수나 괄호 하나가 끝나면 pop해 부모 노드로 돌아간다.
문제 5

순회의 시간과 공간

  1. 노드가 n개인 이진트리에서 전위·중위·후위·레벨 순회의 시간을 적고 이유를 적는다.
  2. 노드 7개가 한쪽으로 한 줄로 이어진 트리와 높이 2인 꽉 찬 트리에서 재귀 순회의 호출 깊이를 각각 적는다.
  3. 재귀로 구현한 전위·중위·후위 순회는 모두 O(n)인데, 추가 공간이 트리 모양에 따라 달라지는 이유를 적는다.
해설 펼치기
  1. 모두 O(n)이다. 각 노드를 일정한 횟수만 보고 한 번씩 처리한다.
  2. 한 줄 트리는 높이 6이라 호출이 7단계까지 쌓이고, 꽉 찬 트리는 높이 2라 3단계까지 쌓인다. 높이 h에서 호출 깊이는 h + 1이며 빈 자식 확인을 세면 한 단계 더 깊어질 수 있다.
  3. 재귀 순회에서는 호출 스택에 동시에 쌓이는 프레임 수가 트리 높이에 비례한다. 한쪽으로 긴 트리는 O(n), 높이가 낮은 트리는 O(log n)이다. 레벨 순회는 큐를 쓰므로 이 호출 깊이 설명을 그대로 적용하지 않는다.