📌 트리(Tree)란?

실제 나무를 거꾸로 한 것과 같은 모양을 하고 있어 ‘트리’라고 부릅니다.
계층적인 자료를 표현하는 데 이용되는 자료구조이며, 컴퓨터의 directory를 예시로 들 수 있습니다. 트리는 값을 가지는 노드(node)와 노드들을 연결해주는 간선(edge)들로 이루어져 있는 자료구조입니다. 모든 노드들이 0개 이상의 자식 노드를 가지며 부모-자식 관계가 존재합니다.

특징

• 트리에는 사이클이 존재할 수 없습니다.
  • 만약 사이클이 생성된다면 그 순간 그 자료구조는 트리가 아닌, 그래프(graph)가 됩니다.
• 루트 노드로 부터 특정 노드로 가는 경로는 오직 하나뿐입니다.
• 만약 트리 내 노드 갯수가 N개라면 간선 갯수는 N-1 개입니다. -> 서로다른 두 노드를 연결하는 간선은 오직 하나이기 때문입니다.
• 트리 내에 다시 트리가 존재하는 재귀적 구조를 갖습니다.
• 데이터를 순차적으로 저장하지 않습니다. 비선형 자료구조이고 방향이 없는 그래프 구조입니다.
• 노드 사이에 부모-자식 관계가 존재하는 특징을 가지며 모든 자식 노드는 단 하나의 부모 노드를 갖습니다.

관련 용어

• 루트 노드(root node): 부모가 없는 최상위 노드 (A)
• 단말 노드(leaf node) : 자식이 없는 노드(H, I, E, J, G)
  - 크기(size) : 트리에 포함된 모든 노드의 개수
• 깊이(depth) : 루트 노드로부터의 거리 (A는 0, 그 밑에 B와 C로 나누어지니 B와 C의 깊이는 1, 또 그 아래의 D,E,F,G는 2..)
• 높이(height) : 깊이 중 최대값(깊이 중 가장 높은 값 / 즉, 루트 노드로부터 가장 멀리 있는 노드)
• 차수(degree) : 각 노드의 간선 개수 (A에서 B와 C로 나눠지니까 A의 차수는 2)

📌 트리 순회 방식

1. 전위 순회, pre-order: 루트 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드

   1-2-4-8-9-5-10-11-3-6-13-7-14

2. 중위 순회, in-order: 왼쪽 자식 노드 -> 루트 노드 -> 오른쪽 자식 노드

   8-4-9-2-10-5-11-1-6-13-3-14-7

3. 후위 순회, post-order: 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 루트 노드

   8-9-4-10-11-5-2-13-6-14-7-3-1

4. 레벨 순회, level-order: 루트 노드부터 계층별로 순회

   1-2-3-4-5-6-7-8-9-10-11-13-14

참고

• https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/Tree.md

피드백 및 개선점은 댓글을 통해 알려주세요😊