yeolyi.com성열의 컴퓨터공학

트리와 순회

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

컴퓨터의 폴더는 폴더 안에 또 폴더가 들어 있습니다. 값을 한 줄로 늘어놓는 배열이나 연결 리스트로는 이런 위아래 관계가 드러나지 않습니다. 어떻게 담으면 될까요?

트리

연결 리스트의 노드가 다음 노드 하나 대신 여러 노드를 가리키게 하면 됩니다. 폴더 노드는 그 안의 폴더와 파일 노드를 가리킵니다. 그리면 나무를 거꾸로 세운 모양이라 이런 구조를 트리(tree)라 부릅니다.

home사진음악메모.txt여행3.jpga.mp31.jpg2.jpg
부모
home
자식
여행, 3.jpg
깊이
1
서브트리
사진, 여행, 1.jpg, 2.jpg, 3.jpg (5개)

노드를 눌러 봅시다. 누른 노드는 하이라이트되고, 그 서브트리는 굵은 테두리로 보입니다.

둘레를 도는 순회

트리의 모든 노드를 한 번씩 들르는 일을 순회(traversal)라 합니다. 트리는 갈래가 나뉘니 배열처럼 앞에서부터 훑을 수 없습니다.

자식이 많아야 둘인 이진 트리(binary tree)로 살펴봅시다. 두 자식은 왼쪽과 오른쪽으로 구분합니다. 루트에서 출발해 왼쪽 자식부터 내려가고, 다 돌면 부모로 돌아와 오른쪽으로 내려갑니다. 이렇게 트리 둘레를 한 바퀴 돌면 노드마다 세 번 지납니다. 처음 도착할 때, 왼쪽 서브트리를 돌고 올 때, 오른쪽 서브트리를 돌고 올 때입니다. 어느 때 방문했다고 치느냐에 따라 이름이 다릅니다.

DBGEACHF
방문 순서

루트 A에서 출발합니다.

하이라이트된 노드가 지금 지나는 곳, 굵은 테두리가 방문한 노드입니다.

전위는 부모를 자식보다 먼저, 후위는 자식을 부모보다 먼저 방문합니다. 이 둘은 자식이 여럿이어도 똑같이 정할 수 있습니다. 폴더 목록을 적을 때는 폴더 이름을 그 안의 내용보다 먼저 쓰니 전위, 폴더 크기를 셀 때는 안의 크기를 먼저 알아야 하니 후위입니다. 중위 순회는 그림을 왼쪽부터 읽은 순서와 같습니다.

레벨 순서

깊이 0, 1, 2 순으로 층마다 왼쪽부터 방문할 수도 있습니다. 이를 레벨 순서 순회(level-order)라 합니다. 둘레를 도는 길에서는 이 순서가 나오지 않으니 큐를 씁니다. 루트를 큐에 넣고, 앞에서 하나 꺼내 방문한 뒤 그 자식을 뒤에 넣기를 큐가 빌 때까지 되풀이합니다.

DBGEACHF
큐 (왼쪽이 앞)
A
방문 순서

루트 A를 큐에 넣었습니다.

먼저 넣은 얕은 노드가 먼저 나오니, 한 층을 다 방문해야 다음 층으로 넘어갑니다.

도전 문제

어떤 이진 트리를 전위 순회하면 E B H A F I D G C, 중위 순회하면 H B F A I E D C G 순서로 방문합니다. 노드 이름은 모두 다릅니다. 이 트리를 후위 순회하면 어떤 순서일까요? 아홉 글자를 이어 쓰세요(예: ABCDEFGHI).