트리의 개요

트리는 스택,큐와 달리 비선형, 계층적 관계를 표현하는 구조이다.

트리는 데이터의 저장,삭제 보다는 표현에 초점을 두고 있다.

 

 

 

terminal node : 아래에 다른 노드가 뻗치지 않은 최하위 노드 ex)H,I,J,F,G

internal node: terminal node를 제외한 노드 ex)A,B,C,D,E

 

 

이진 트리와 서브 트리

이진트리란

1.루트 노드를 중심으로 두개의 서브 트리로 나뉜다. 

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

이 두 조건을 만족하는 트리이다.

 

위의 사진은 E가 2번 조건을 만족하지 못하니 이진 트리가 아니다라고 생각 할 수 있지만

사실 저 트리도 이진 트리가 맞다.

 

E의 자식 노드로 J의 형제가 존재할 수 있기 때문에 공(empty) 노드로 남아 있다.

 

 

포화 이진 트리와 완전 이진 트리

 

트리에서 레벨은 루트 노드를 레벨0으로 시작해 자식으로 내려갈 수록 1씩 증가하는 단위이고,

높이는 총 레벨 이기 때문에 최고 레벨(최하위 노드)=높이로 볼 수 있다.

포화 이진 트리는 모든 레벨들의 자식들이 꽉 차 있는 상태라 노드를 추가하기 위해서는 레벨을 늘려야 하는 모습이다.

 

 

완전 이진 트리는 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만 

 

 

위와 같이 빈 틈 없이 채워진 상태이다.

E,F,G의 자식 노드들이 공 노드로 채워져 있기 때문에 빈 틈이 없다고 볼 수 있다.