[C] 트리와 이진트리

트리(Tree)와 이진트리(Binary Tree)에 대해 알아보자.

 

(1) 트리

트리는 계층적인 구조를 나타내는 자료구조이다. 지금까지 배웠던 스택, 큐, 리스트는 모두 선형 자료구조이지만, 트리는 비선형 자료구조 중 하나이다. 트리의 응용분야에는 회사의 조직도, 컴퓨터의 폴더 구조, 인공지능에서의 결정 트리(decision tree) 등이 있다. 

 

 

 

• 차수(degree): 노드의 자식 노드 수
• 레벨(level): 트리의 각 층의 번호
• 높이(height): 트리의 최대 레벨

예를 들면, 루트노드인 P의 차수는 2이고(자식이 Q, R 2개이므로), A의 레벨은 3이다. 레벨을 구할 때 루트=1인 것을 잊지말자. 이 트리의 높이는 5이다. 

트리도 데이터필드와 링크필드로 나누어서 메모리상에 구현할 수 있는데, 링크필드는 자식노드를 가리키게 만들어야 한다. 즉,

 

링크의 개수 = 자식노드의 개수 = 노드의 차수

 

그런데 문제는, 자식노드가 몇 개인줄 알고..? 노드의 차수가 n이라고 생각하면 구현이 존나게 복잡해지는 것이다. 그래서 앞으로는 자식노드의 개수가 2개인 이진트리만을 다루기로 한다.

 

 

 

(2) 이진트리

이진트리는 모든 노드가 2개의 서브트리를 가지고 있다. 물론 서브트리가 공집합일 수도 있기 때문에 정확히는 0~2개 사이의 자식 노드가 존재하고, 모든 노드의 차수가 2이하이다. 공집합도 이진트리이다!!

 

 

그림의 트리 둘 다 이진트리이다. 대신 왼쪽은 포화이진트리(full binary tree), 오른쪽은 완전이진트리(complete binary tree)라는 차이점이 있음. 자세히는 이렇다.

• 포화이진트리: 단말노드를 제외한 모든 노드가 자식노드를 2개씩 갖고 있어야 함(각 레벨에 노드가 꽉 차있음)
• 완전이진트리: 높이가 h일 때, 레벨 1부터 h-1까지는 노드가 모두 채워지고, 마지막 레벨 h에서는 노드가 왼쪽부터 순서대로 채워져야 함

 

이진트리의 성질

1. n개의 노드를 가진 이진트리는 n-1개의 간선을 가진다.
2. 높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 (2^h)-1개의 노드를 가진다.
3. n개의 노드를 가진 이진트리의 높이는 최대 n이거나 최소 [log(n+1)]이 된다.

2번과 3번은 그림을 그려보면 쉽다. 각 레벨에 노드가 하나씩만 있는 일자 형태의 트리와, 모든 레벨의 노드가 포화상태인 트리를 생각해보자. 

 

이진트리의 코드 구현법은 다음 포스트에서...