7 / 14강

트리와 순회

폴더 안에는 파일과 다른 폴더가 들어갑니다. 이런 계층 관계를 나타낼 때 트리를 씁니다. 여기서는 시작점 하나에서 부모와 자식으로 이어지는 루트 트리를 다룹니다.

꼭 알아둘 이름

• 루트(root): 가장 위의 시작 노드입니다.
• 부모와 자식: 바로 위와 아래로 연결된 노드입니다. 루트를 제외한 노드는 부모가 하나입니다.
• 리프(leaf): 자식이 없는 노드입니다.
• 이진 트리: 각 노드가 왼쪽과 오른쪽, 최대 두 자식을 갖습니다.

다음 트리에는 노드가 다섯 개 있습니다. A가 루트이고 C, D, E는 리프입니다.

    A
   / \
  B   C
 / \
D   E

언제 자신을 방문할까요?

순회는 모든 노드를 방문하는 일입니다. 왼쪽 자식부터 살펴본다고 정하면 다음 순서를 얻습니다.

• 전위: 자신 → 왼쪽 → 오른쪽. 결과는 A B D E C입니다.
• 중위: 왼쪽 → 자신 → 오른쪽. 결과는 D B E A C입니다.
• 후위: 왼쪽 → 오른쪽 → 자신. 결과는 D E B C A입니다.
• 레벨 순회: 가까운 층부터 방문합니다. 큐를 쓰며 결과는 A B C D E입니다.

중위 순회 따라가기

튜플 (값, 왼쪽, 오른쪽)로 노드 하나를 표현하겠습니다. None은 자식이 없다는 뜻입니다.

tree = ("A",
        ("B", ("D", None, None), ("E", None, None)),
        ("C", None, None))

def inorder(node):
    if node is None:
        return
    value, left, right = node
    inorder(left)
    print(value)
    inorder(right)

inorder(tree)

출력은 D, B, E, A, C입니다. A를 만나자마자 출력하지 않고 왼쪽 트리를 먼저 처리합니다. 각 노드를 한 번 방문하므로 시간은 O(n)입니다. 재귀 호출 공간은 트리 높이를 h라 할 때 O(h)입니다.

확인 문제

하위 폴더의 용량을 모두 계산한 뒤 상위 폴더의 용량을 합치려 합니다. 전위와 후위 중 어떤 순서가 자연스러울까요?