[자료구조 ] 이진 트리 - 그래프와 차이점, 명칭, 종류

 

 

트리는 그래프(graph)의 한 종류다.

 

또한 위 그림에서 보듯이 계층형 자료구조다.

 

그러면  트리와 그래프와 차이점은 무엇일까?

 

 

 

 

우선 트리는 순환 구조를 가지지 않는다. 트리는 위 그림과 같은 연결구조를 가질 수 없다

 

 

 

 

그래프는 위 그림과 같은 양방향(Uni-directional) 및 단방향(Bi-directional) 구조 모두 가능하지만,

 

트리는 단방향 구조만 가능하다.

 

 

 

트리는 위 그래프 처럼 루트 노드를 두개 이상 가질 수 없고,

 

한 노드가 두 개 이삳의 부모 노드를 가질 수 없다.

 

 

 

 

'루트 노드'나 '부모 노드'와 같은 명칭에 익숙하지 않을 수도 있다.

 

트리를 대표적인 명칭은 아래와 같다.

 

 

맨 윗단에 있는 노드를 '루트(Root)노드', 맨 아랫단에 있는 노드를 '리프(Leef)노드'라고 한다. 

 

그리고 위-아래로 연결된 노드를 각각 '부모', '자식 노드'라고  부른다. 

 

'차수'는 부모노드가 가지는 자식 노드의 개수를 말한다.

 

'크기'는 부모 노드와 자식 노드를 합한 개수이다.

 

'레벨'은 맨 윗층부터 0, 1, 2 순서대로 분류된다.

 

'깊이'는 루트 노드를 기준으로 현재 노드의 위치를 말하며,

 

'높이'는 리프 노드를 기준으로 현재 노드의 위치를 나타낸다.

 

 

 

 

마지막으로  이진트리(Binary Tree)의 종류에 대해서 알아보겠다.

(이진트리는 다진트리 중 자식 노드의 개수가 2개 이하인 노드를 지칭하는 말이다)

 

 

 

1. 정 이진 트리(Full Binary Tree)는 모든 노드가 0개 또는 2개의 자식 노드를 가지고 있는 경우를 말한다.

 

 

 

 

 

 

2. 완전 이진 트리(Complete Binary Tree)는 마지막 레벨을 제외하고 모든 레벨에 노드가 완전하게 채워졌으며,

 

마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다.

 

 

 

 

 

 

3. 포화 이진 트리(Perfect Binary Tree)는 모든 노드가 2개의 자식을 가지고 있으며,

 

모든 리프 노드가 동일한 깊이, 레벨에 위치하는 구조를 말한다.

 

 

 

 

본 글은 '파이썬 알고리즘 인터뷰(박상길 / 책만)'의 내용을 정리한 내용입니다.