[C로 만드는 자료구조]트리(Tree)

트리(Tree) - 특성

지금까지 포스팅했던 자료구조(스택(Stack), 리스트(List), 큐(Queue) 등)들은 선형구조였습니다. 하지만 오늘부터 포스팅 할 트리(Tree)는 계층적인 구조를 나타내는 자료구조입니다. 원소들간에 1:多의 관계를 가지는 비선형구조입니다.

트리(Tree) - 응용 분야

트리는 계층을 이용하는 모든 곳에서 이용되게 됩니다.

1. 계층적인 조직 표현
   
   
   조직도같은 계층적인 모양도 트리로 표현가능합니다.
   
   
2. 컴퓨터 디스크의 디렉토리 구조
   
   
   디렉토리도 트리를 통해 표현이 가능합니다.
   
   
3. 인공지능(AI)에서의 결정트리(Decision Tree)
   
   
   인공지능에서 앞선 다음 행동들을 결정하기 위해서 트리를 사용합니다.
   
   

트리(Tree) - 용어

트리에서만 사용하는 용어들이 있는데 이 용어 들을 알아보겠습니다.

• 노드(Node) : 드리의 구성 요소 하나하나를 의미
  
  
• 루트(Root) : 유일한 시작 노드 (노드 A), 부모가 없는 노드를 의미
  
  
• 서브트리(Sub-Tree) : 각 노드를 기준으로 그 노드가 루트가 되는 트리 
                                          -> Recursive structure
• 단말 노드(Terminal Node 또는 Leaf Node) : 자식이 없는 노드 (노드 E, 노드 F, 노드 G 등)
  
  
• 중간 노드(내부 노드, 비(非)단말 노드) : 적어도 하나의 자식을 가지는 노드(노드 A, 노드 B, 노드 C, 노드 D)
  
  

• 부모 노드 : 바로 위에 있는 노드를 의미
  
  
• 형제 노드 : 같은 계층에 있는 노드들끼리의 관계를 의미
  
  
• 자식 노드 : 자신의 바로 아래있는 노드를 의미

• 노드의 레벨(Level) : 루트 노드와 현재 노드를 연결하는 간선의 수(Root노드는 0 레벨에 위치한다.)
  
  
• 트리의 높이(height, depth) : 트리 최대 레벨 (트리에서) 가장 아래 있는 노드의 레벨)
  
  
• 차수(Degree) : 노드가 가지고 있는 자식 노드의 개수(자식이 없는 단말은 차수가 0)
  
  
• 트리의 차수(Degree of Tree) : 트리에 있느 노드 차수 중에서 가장 큰값을 의미
  
  

트리(Tree) - 그래프와의 차이

 

트리는 흔히 그래프와 비슷해 보이기도 하는데요. 그래프와는 다른 것이 어떤 것이 다를까요? 다음 두 가지가 다르답니다.

1. Root 노드에서 각 노드까지의 경로가 유일해야한다.
   
   
2. 임의 노드에 대한 부모는 하나여야한다.
   
   

위의 2가지를 가지고 그래프와 트리를 구분하게 됩니다.

위의 그림은 트리가 아닌 그래프임을 알 수 있습니다.

트리(Tree) - 트리의 종류

   
트리는 2가지로 구분할 수 있는데 이진 트리와 일반 트리로 구분하게 됩니다.

           

왼쪽의 경우를 이진트리 차수가 2인 트리를 이진트리라 하며 그외의 경우를 오른쪽의 경우 일반 트리라고 하게됩니다.

다음 포스팅에서는 이진트리(Binary Tree)와 그의 구현에대해서 알아보겠습니다.