[자료구조] 트리 (Tree)

트리(Tree)는 데이터를 저장하고 탐색하기 유용한 구조를 갖고 있습니다. 프로그래밍에서는 계층 구조를 표현하는 용도로도 많이 사용되는데, 루트 노드(root node)를 기준으로 가지처럼 뻗어 나가는 자료구조를 가지고 있습니다.

 

참고로 간선이란, 노드와 노드 사이를 이어주는 선을 의미하고, 특정 노드에서 아래로 향하는 간선의 개수를 통해 차수를 정의합니다. 즉, 노드 간의 간선이 몇개인지에 따라 차수가 정해집니다.

차수가 2개인 이진 트리를 배열로 표현하면 오른쪽 그림과 같은데, 루트 노드는 배열 인덱스 1번에 저장합니다.
왼쪽 자식 노드의 인덱스는 [부모 노드의 배열 인덱스 * 2] 입니다.
오른쪽 자식 노드의 인덱스는 [부모 노드의 배열 인덱스 * 2 + 1] 입니다.

 

 

 

그렇다면 이진 트리를 탐색할 때, 어떤 방식으로 순회를 할까요?

트리는 각 노드의 Left, Right 포인터를 통해 탐색하게 되는데, 순회 방식은 크게 3가지로 나뉘어 집니다. 전위 순회, 중위 순회, 후위 순회로 구분되고, 탐색 데이터에 따라 어떤 방식이 유리할지 고민해보면 좋을 것 같습니다ㅎ

구분	상세
전위 순회	부모 노드  →  왼쪽 자식 노드  →  오른쪽 자식 노드 순서로 방문
중위 순회	왼쪽 자식 노드  →  부모 노드  →  오른쪽 자식 노드 순서로 방문
후위 순회	왼쪽 자식 노드  →  오른쪽 자식 노드  →  부모 노드 순서로 방문

 

 

 

전위, 중위, 후위 순회 결과를 반환하는 solution() 함수를 구현해봅시다!

# 전위 순회
def preorder(nodes, idx):
   if idx < len(nodes):
      ret = str(nodes[idx]) + " "
      ret += preorder(nodes, idx * 2 + 1)
      ret += preorder(nodes, idx * 2 + 2)
      return ret
   else:
      return ""

# 중위 순회
def inorder(nodes, idx):
   if idx < len(nodes):
      ret = inorder(nodes, idx * 2 + 1)
      ret += str(nodes[idx]) + " "
      ret += inorder(nodes, idx * 2 + 2)
      return ret
   else:
      return ""

# 후위 순회
def postorder(nodes, idx):
   if idx < len(nodes):
      ret = postorder(nodes, idx * 2 + 1)
      ret += postorder(nodes, idx * 2 + 2)
      ret += str(nodes[idx]) + " "
      return ret
   else:
      return ""

def solution(nodes):
   # 전위, 중위, 후위 순회 결과 계산
   return [
      preorder(nodes, 0)[:-1],
      inorder(nodes, 0)[:-1],
      postorder(nodes, 0)[:-1]
   ]

# 테스트 코드
nodes = [1, 2, 3, 4, 5, 6, 7]
print(solution(nodes))