[좌충우돌, 파이썬으로 자료구조 구현하기] 트리 구현하기

트리는 족보의 가계도나 조직도, 마인드맵을 생각하자.

어려운 말로는 그래프(Graph)의 한 형태로서, 순환(cycle)이 없는 연결 그래프라 한다.

구성

• 노드(Node): 트리를 구성하는 기본 요소, 값(key or data)과 하위 노드를 가리키는 포인터(pointer)를 가진다.
• 간선(Edge): 노드와 노드를 연결한 선(Link)

위 그림처럼 트리는 루트(Root)에서 시작한다.

• 루트: 부모 노드가 없는 최상위 노드
• 부모(parent)노드: 자식(child) 노드를 가진 노드
• 자식(child)노드: 부모 노드의 하위 노드
• 형제(siblings)노드: 부모가 같은 노드
• 리프(leaf)노드: 자식이 없는 노드
• 서브 트리(sub tree): 특정 노드를 루트로 생각할 때 생기는 트리

기타 용어

• 크기(size): 자신을 포함한 모든 자식 노드의 갯수
• 레벨(level): 루트 노드로부터 특정 노드까지 연결된 간선의 수
• 깊이(depth): 루트 노드로부터 특정 노드까지의 거리, 수치로만 보면 레벨과 같다.
• 높이(height): 노드에서 가장 깊은 노드까지의 길이
• 경로(path): 한 노드에서 다른 노드로 갈 때 거쳐 가는 노드들의 순서
• 차수(degree): 자식의 개수

레벨, 깊이, 높이는 비슷해 보인다. 깊이는 루트부터 아래로 내려간 길이이고 높이는 서브 트리에서 가장 깊은 노드부터 위로 올라간 길이라고 생각하자.

이진트리와 순회 방법

이진트리(binary tree)는 모든 노드가 두 개 이하의 자식 노드를 가지는 트리이다.

트리에서 각 노드를 한번씩 체계적으로 방문하는 과정을 순회(traversal)라고 한다.

부모 노드와 왼쪽 노드, 오른쪽 노드를 어떤 순서로 방문하느냐에 따라 순회 방법이 다르다. 순회 방법에는 전위 순회, 중위 순회, 후위 순회가 있다.

각 노드는 서브 트리일 수 있으므로, 순회방법은 재귀적이다.

• 전위, 중위, 후위 순회는 재귀적으로 구현하거나 스택으로 구현할 수 있다.
• 노드 레벨 순설로 방문하는 레벨 순서 순회는 큐를 이용하여 구현할 수 있다.

전위 순회(Preorder traversal)

현재 노드 먼저 방문 후 왼쪽 또는 오른쪽 노드를 차례로 방문한다.

1. 루트부터 방문하고 왼쪽 B를 방문한다.
2. A의 오른쪽인 C를 방문하기 전에, B-D-E가 서브 트리이므로 같은 방법으로 순회한다.
   • B는 방문했으므로, B의 왼쪽인 D를 방문한다.
   • D도 서브 트리이므로, B의 오른쪽인 E보다 먼저 순회한다.
     • D를 이미 방문했으므로, 왼쪽 G를 방문한다.
   • B-D-G를 모두 방문했으므로, B의 오른쪽인 E를 방문한다.
3. A-B-D-G-E를 방문했으므로, A의 오른쪽인 C를 방문한다.
   • C의 왼쪽 노드인 F를 방문한다.

순회 결과는 A → B → D → G → E → C → F

중위 순회(Inorder traversal)

왼쪽 노드를 먼저 방문한 후 현재 노드 방문한다. 그리고 오른쪽 노드를 방문한다.

1. 먼저 루트 A에서 출발은 하되, A를 방문하기 전에 왼쪽 B를 먼저 방문한다.
2. B-D-E도 서브 트리이므로 B를 방문하기 전에 B의 왼쪽인 D를 먼저 방문한다.
   • D-G도 서브 트리이므로 D를 방문하기 전에 D의 왼쪽인 G를 먼저 방문한다.
   • D의 왼쪽을 방문했으니 D를 방문하고 D의 오른쪽을 방문한다.
   • D의 오른쪽은 없으므로, B의 왼쪽인 G-D를 모두 방문했으니 B를 방문하고 B의 오른쪽인 E를 방문한다.
3. A의 왼쪽인 G-D-B-E를 방문했으니 A를 방문한다.
   • A를 방문했으니 A의 오른쪽을 향한다.
   • C를 방문하기 전에 C-F가 서브 트리이므로 C의 왼쪽인 F를 방문한다.
   • C를 방문한다.

순회 결과는 G → D → B → E → A → F → C

후위 순회(Postorder traversal)

왼쪽 노드를 먼저 방문한다. 그리고 오른쪽 노드와 현재 노드를 차례로 방문한다.

1. A에서 출발하되 A의 왼쪽 노드인 B를 먼저 방문한다.
   • B-D-E도 서브 트리이므로, B를 방문하기 전에 B의 왼쪽인 D를 방문한다.
   • D-G도 서브 트리이므로, D를 방문하기 전에 G를 방문한다.
   • D의 왼쪽을 방문했으니 D의 오른쪽을 방문한다.
   • D의 오른쪽은 없으므로 D를 방문한다.
   • B의 왼쪽인 G-D를 방문했으므로, B의 오른쪽인 E를 방문하고 B를 방문한다.
2. A의 왼쪽인 G-D-E-B를 방문했으니 A의 오른쪽인 C를 방문한다.
   • C-F가 서브 트리이므로, C를 방문하기 전에 C의 왼쪽 노드인 F를 방문한다.
   • C의 오른쪽 노드가 없으므로 C를 방문한다.
3. A의 오른쪽인 C-F를 방문했으므로 마지막으로 A를 방문한다.

순회 결과는 G → D → E → B → F → C → A

레벨 순서 순회(Level order traversal)

레벨 0부터 차례대로 방문하며, 같은 레벨에서는 왼쪽에서 오른쪽으로 가면서 방문한다.

순회 결과는 A → B → C → D → E → F → G