트리

- 이번 글에서는 배열이나 연결 리스트와 같은 선형 자료구조와는 다르게 

  '계층형 자료구조'에 속하는 트리에 대해 알아보겠습니다. 

 

 

1) 트리 기본 개념

- 트리를 이해하기 위해서는 우선 몇 가지 기본 개념을 알아야 합니다. 

 

(1) 루트 노드

- 트리의 맨 상위 노드를 루트 노드라고 합니다. 

 

(2) 부모 노드

 - 특정 노드에 상위 링크로 연결된 노드를 부모 노드라고 합니다. 

   위의 그림에서는 2,3,4,5번 노드의 부모 노드가 1번 노드(루트 노드)입니다.  

 

(3) 자식 노드

-  특정 노드에 하위 링크로 연결된 노드를 자식 노드라고 합니다. 

   위의 그림에서는 1번 노드이 자식 노드가 2,3,4,5번 노드입니다. 

 

(4) 레벨

- 트리의 한 층위를 레벨이라고 합니다. 트리의 레벨은 0부터 시작합니다.  

  위의 그림에서는 루트 노드가 레벨0이고, 2~5번 노드가 레벨1, 

  6~13번 노드가 레벨2에 속합니다. 

 

5) 높이

- 트리의 층위의 개수를 높이라고 합니다. 

  위의 그림에서는 총 4개의 층위가 존재하므로, 높이는 4라고 할 수 있습니다. 

 

(5) 조상 노드

- 특정 노드의 모든 상위 노드를 조상 노드라고 합니다.  

  예를 들어, 7번 노드의 경우 2번 노드와 1번 노드가 조상 노드입니다.

 

(6) 자손 노드

- 특정 노드의 모든 하위 노드를 자손 노드라고 합니다. 

  예를 들어, 3번 노드의 경우 8번 노드, 9번 노드, 10번 노드, 15번 노드, 16번 노드가 자손 노드입니다. 

 

 

2) 트리 종류

- 트리에는 여러 가지 종류가 있습니다. 

 

1) 이진 트리

-  각 노드가 최대 2개의 자식 노드를 갖는 트리를 의미합니다. 

 

2) 삼진 트리

- 각 노드가 최대 3개의 자식 노드를 갖는 트리를 의미합니다. 

 

3) 균형 트리 vs 불균형 트리

- 균형 트리는 루트 노드를 기준으로 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 1이하인 트리를 의미합니다.

  불균형 트리는 균형 트리가 아닌 트리를 의미합니다.

  균형 트리의 대표적인 예로는 AVL 트리나 Red-black 트리가 있습니다. 

 

4) 완전 이진 트리

- 완전 이진 트리는 트리의 높이가 h라면, h-1 높이까지의 노드는 꽉 차있고,

  h번째 높이는 왼쪽 부터 오른쪽으로 꽉 차 있는 이진 트리를 의미합니다. 

 

5) 포화 이진 트리 

- 포화 이진 트리는 자식 노드를 가진 모든 노드가 0개 혹은 2개의 자식 노드를 가진  이진 트리를 의미합니다. 

 

3) 트리 순회

- 트리 순회란 트리의 모든 노드를 방문하는 과정을 의미합니다. 

  이진 트리를 기준으로, 트리 순회에는 크게 3가지 방법이 있습니다.

  그것은 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)입니다.

(1) 전위 순회

- 전위 순회는 루트 노드 - 왼쪽 자식 노드 - 오른쪽 자식 노드 순으로 방문하면서 순회하는 것을 의미합니다.

  위의 이진 트리를 기준으로 전위 순회를 하면 A -> B -> D -> C -> E -> G -> F -> H -> I 순으로 순회합니다. 

 

(2) 중위 순회

- 중위 순회는 왼쪽 자식 노드 - 루트 노드 - 오른쪽 자식 노드 순으로 방문하면서 순회하는 것을 의미합니다.

  위의 이진 트리를 기준으로 중위 순회를 하면 D -> B -> A  -> E -> G -> C -> H -> F -> I 순으로 순회합니다. 

 

(3) 후위 순회

- 후위 순회는 왼쪽 자식 노드 - 오른쪽 자식 노드 - 루트 노드 순으로 방문하면서 순회하는 것을 의미합니다.

  위의 이진 트리를 기준으로 후위 순회를 하면 D -> B -> G -> E -> H -> I -> F -> C -> A 순으로 순회합니다. 

 

참고  

누구나 자료구조와 알고리즘

Introduction to Tree Data Structure - GeeksforGeeks        

Data Structure - Binary Tree Traversal Techniques : Inorder-Preorder-Postorder-Levelorder - EXAMRADAR