[자료구조] 트리(Tree)

트리는 비선형 자료 구조로 직관적으로 자료 사이의 관계를 나타낸다.

트리와 같은 자료 구조는 계층 구조로 트리를 구성하는 노드가 부모-자식 관계이다.

이러한 구조는 회사 조직도, 컴퓨터 폴더 구조 등 주의에서 쉽게 볼 수 있다.

트리 용어는 다음과 같은 것들이 있다.

- 노드 : 트리의 한 요소, 모델링하려는 시스템의 객체

- 간선 : 간선은 노드 간 부모-자식 관계를 정의함

- 루트 노드 : 최상위 노드

- 서브 트리 : 트리에서 루트 노드를 제거했을 때 생기는 종속 트리

- 부모 노드, 자식 노드 : 이 둘은 서로 연결되어 있음

- 차수 : 어떤 특정 노드의 자식 노드 수

- 단말 노드 : 자식 노드가 없는 노드

- 내부 노드 : 자식 노드가 있는 노드

- 조상 노드 : 루트 노드부터 부모 노드까지의 경로상에 있는 노드

- 후손 노드 : 특정 노드의 아래에 있는 모든 노드

- 레벨 : 루트 노드를 레벨 1이라 하고, 내려가면서 레벨이 오른다.

- 형제 노드 : 같은 부모 노드의 자식 노드

- 높이 또는 깊이 : 트리의 특정 노드의 최대 레벨

이진트리

이진 트리는 모든 노드의 차수가 2 이하인 트리이다.

이진 트리 종류는 다음과 같은 것들이 있다.

- 포화 이진 트리 : 모든 레벨의 노드가 꽉 차있는 이진 트리

 

- 완전 이진 트리 : 마지막 레벨에서 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진 트리

 

- 편항 이진 트리 : 오른쪽 또는 왼쪽 서브트리만 가지는 이진 트리

이진 트리 순회

이진 트리 순회 방법은 전위 순회, 중위 순회, 후위 순회로 나누어 진다.

전위 순회 : 현재 노드 방문 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리

중위 순회 : 왼쪽 서브 트리 -> 현재 노드 방문 -> 오른쪽 서브트리

후위 순화 : 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 현재 노드 방문

예를 들어 이진 트리가 이렇게 있으면

각각의 순회는 이렇다.

 

[출처] [자료구조] 트리|작성자 03tlqfk