트리와 순회·수식 표기법

트리(tree)는 뿌리 하나에서 가지가 갈라져 내려가는 계층 구조다. 실기 시험은 그림으로 트리를 주고 **차수(degree)·단말 노드(terminal node)·깊이(depth)**를 묻거나, 전위 순회(preorder)·중위 순회(inorder)·후위 순회(postorder)의 방문 순서를 쓰게 한다. 순회와 같은 원리로 수식을 적는 표기법과 후위 표기식 계산은 다음 문서에서 다룬다.

트리 용어

아래 이진 트리(binary tree)를 예로 쓴다. 트리의 한 칸을 노드(node)라 하고, K가 맨 위의 근 노드(root node)다.

다이어그램 로딩…

B의 자식은 왼쪽 A 하나, F의 자식은 오른쪽 G 하나다.

용어	뜻	예제 트리
노드의 차수	한 노드의 자식 수	K 2, B 1, A 0
트리의 차수	노드 차수 중 가장 큰 값	2
단말 노드	자식이 없는 노드	A, G, P, T
레벨	근 노드를 1로 센 층 번호	A·G는 4
깊이	가장 큰 레벨	4

차수가 0인 노드를 단말 노드 또는 잎 노드(leaf node)라 한다. 레벨(level)과 깊이는 시험에서 근 노드를 1로 센다.¹ 여러 트리를 모아 놓은 것은 숲(forest)이라 한다. 예제에서 근 노드 K를 지우면 D와 R을 근으로 하는 트리 두 개로 이루어진 숲이 남는다.

이진 트리는 모든 노드의 차수가 2 이하인 트리다. 깊이가 k이면 노드는 최대 2ᵏ − 1개이고, 레벨 i에는 최대 2ⁱ⁻¹개가 있다. 깊이 4면 최대 15개다. 모든 레벨이 꽉 찬 트리를 포화 이진 트리(perfect binary tree), 마지막 레벨만 왼쪽부터 채워진 트리를 완전 이진 트리(complete binary tree)라 한다.

세 가지 순회

순회(traversal)는 모든 노드를 한 번씩 방문하는 순서다. 이름은 근 노드를 언제 방문하느냐로 정한다. 왼쪽 서브트리(subtree, 어떤 노드 아래 딸린 작은 트리)는 항상 오른쪽보다 먼저다.

순회	순서	예제 결과
전위 순회	근 → 왼쪽 → 오른쪽	K D B A F G R P T
중위 순회	왼쪽 → 근 → 오른쪽	A B D F G K P R T
후위 순회	왼쪽 → 오른쪽 → 근	A B G F D P T R K

손으로 풀 때는 서브트리를 한 덩어리로 보고 규칙을 되풀이해 적용한다. 전위 순회라면 K를 먼저 쓰고, 왼쪽 덩어리 D를 다시 전위로 풀고, 그다음 오른쪽 덩어리 R을 푼다. 후위 순회에서는 근 노드 K가 항상 맨 끝에 오고, 전위 순회에서는 항상 맨 앞에 온다. 이것으로 답을 빠르게 검산할 수 있다. 중위 순회는 가운데 방문이다.

시험 포인트

• 근 노드 먼저 전위, 가운데 중위, 마지막 후위. 왼쪽은 항상 오른쪽보다 먼저.
• 차수 0 → 단말 노드. 트리의 차수 = 노드 차수의 최댓값. 트리 여러 개의 모임 → 숲.
• 깊이 k 이진 트리 최대 노드 2ᵏ − 1(근 레벨 1 기준).

참고

1. 영어권 자료는 근 노드의 깊이를 0으로 세는 경우가 많다. 그 기준이면 예제 트리의 높이는 3이다. 시험 답안은 근 노드를 레벨 1로 세는 방식을 따른다. ↩︎