트리(쓰는 중)

트리는 선형 자료구조인 스택과 큐와 다르게 비선형 자료구조이다.  선형 자료구조들은 보통 삽입,삭제 등 기능에 초점이 맞춰져 있다면

트리는 '표현'에 초점이 맞춰져 있다. 즉, 트리는 계층적 관계를 표현하는 자료구조이다.

트리가 표현할 수 있는 것들 중 예를 들자면, 디렉터리 구조나 기업의 조직도 등이 있겠다.

트리 관련 용어:

1.노드 

트리의 구성요소에 해당하는 데이터.

2.간선

노드와 노드를 연결하는 연결선

3. 루트 노드

트리 구조에서 최상위에 존재하는 노드

4.단말 노드

아래로 또 다른 노드가 연결되어 있지 않은 노드

5.내부 노드

단말 노드를 제외한 모든 노드

6.조상 노드

특정 노드의 위에 위치한 모든 노드를 가리켜 '조상 노드'라 한다.

7.후손 노드

특정 노드의 아래에 위치한 모든 노드를 가리켜 '후손 노드'라 한다.

큰 트리는 작은 트리로 구성이 된다.  큰 트리에 속하는 작은 트리를 가리켜 '서브 트리'라 한다.

이진 트리의 조건

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

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

3.노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주한다.

트리의 용어 중에 레벨과 높이가 있다. 레벨은 루트 노드부터 아래로 레벨 0부터 시작하며

높이는 최고의 레벨을 높이라고 한다.

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

포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 틈 없이 채워진 이진트리를 완전 이진 트리라 한다.

차곡차곡 빈 틈 없이 채워진 상태가 갖는 의미는 노드가 위에서 아래로, 그리고 왼쪽에서 오른쪽의 순서대로 채워진 상태를 말한다.

트리를 표현하기에는 연결 리스트가 더 유연하기 때문에 트리는 연결 리스트를 기반으로 구현하는 것이 용이하다.

하지만, 완전 이진 트리라면 배열 기반의 구현도 고려해볼 만하다.

※배열은 연결 리스트에 비해 탐색이 매우 용이하고 빠르다.