[자료구조] 이진트리(Binary Tree) - 1

 

이번에는 이진 트리를 구현 해보기 전에..

 

이진 트리는 뭔가용??

 

매우 간단 하게 설명하면 위 그림처럼 자식 노드가 2개씩 달린 트리이다.

 

이진 트리는 다음 두 조건을 만족 해야 한다.

루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.

나뉘어진 두 서브 트리도 모두 이진 트리어야 한다.

 

그러면 다음 구조는 이진 트리가 맞을까??

이것을 보고 이진 트리가 아닌거 같지만 이것도 이진 트리가 맞다

 

왜냐하면 이진 트리 관련해서 다음의 내용이 추가로 정의 되어있다.

노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면 공집합(empty set)노드가 존재하는 것으로 간주

공집합 노드도 이진 트리의 판단에 있어서 노드로 인정!

그러므로 공집합까지 보이면 다음 그림과 같이 된다.

 

이러한 공집합 노드 때문에 서브 트리가 B와 C인 노드, D와F 도 이진 트리가 되는 것이다.

이러한 트리도 공집합 노드 때문에 이진 트리가 될 수 있다.

 

 

이진 트리의 몇몇 분류를 소개하기전에 트리 관련 용어를 설명하겠습니다

트리에서는 각 층별로 숫자를 매겨서 이름 트리의 레벨 이라하고 트리의 최고 레벨을 가리켜 높이라고 한다.

 

 

이렇게 모든 레벨이 꽉찬 이진트리를 '포화 이진 트리'라고 한다.

 

 

포화 이진 트리처럼 모든 레벨이 가득 찬 상태는 아니지만 빈 틈 없이 노드가 채워진 이진트리를

'완전 이진 트리(complete binary tree)' 라 한다.

 

위의 트리는 '이진 트리'이긴 하나 '완전 이진 트리'는 아니다

저런 건 그냥 이진 트리이다.