비선형 자료구조 - 트리

 

트리는 1대 N 또는 1대 1 대응 구조로 노드와 선분으로 구성되어 있다.

또한 노드 사이 연결관계가 계급적인 구조로 뻗어나간 정점들이 다른 정점들과 연결되지 않는다.

 

트리의 구성요소

노드 - 기본 구성요소인 각 점들

근 노드 - 가장 상위에 위치한 노드

레벨 - 근노드를 기준으로 특정 노드까지의 경로 길이를 말함

깊이 - 트리의 최대 레벨

차수 - 특정 노드 밑에 자식 노드의 개수를 말한다.

 

이진 트리

모든 노드의 차수가 2 이하인 트리로 구성되어 있으며,

트리의 전체 노드 수는 최대 $2^(k+1)$이다.

 

포화 이진 트리

모든 노드의 레벨이 같으며 2개의 자식을 가진다.

이진 트리로서 가장 많은 노드를 가진 트리이기도 하다.

 

완전 이진 트리

완전 이진트리는 포화 이진트리에서 오른쪽으로 하나씩 제거하여 얻어진 트리로,

포화 이진트리는 동시에 완전 이진트리이다.

 

 

 

 

 

힙 트리

특수 형태의 포화 이진 트리로 부모 노드가 자식 노드보다 값이 작으면 최소 힙이 되고 크면 최대 힙이 된다.

최대 힙의 최상단 노드는 최대값, 최소 힙의 최상단 노드는 최소값이 된다.

 

트리 운행법

전위 운행 (루트 -> 좌측 -> 우측) 

중위 운행 (좌측 -> 루트 -> 우측)

후위 운행 (좌측 -> 우측 -> 루트)