트리 구조

* 트리(Tree)

- 트리는 비선형 자료구조 중에서 자료들 간에 계층관계를 가진 계층형 자료구조이다.

 

- 트리를 구성하는 원소들을 노드라 하고 노드를 연결하는 선을 간선(Edge)라고 한다.

- 부모노드와 자식노드는 간선으로 연결되어 있다.

- 트리의 시작 노드를 루트 노드(Root Node)라고 하고 레벨 0이 된다.

- 같은 부모노드의 자식노드들은 서로 형제 노드(Sibling Node)가 된다.

- 자식노드들은 각각 독립하여 새로운 트리를 구성할 수 있다.

- 따라서, 각 노드는 자식노드 수만큼의 서브 트리(Sub Tree)를 갖는다.

 

- 한 노드가 가지는 서브 트리의 수, 즉 자식노드의 수를 그 노드의 차수(Degree)라 한다.

- 예를 들어, 노드 A의 차수는 3이며 노드 B의 차수는 2이다.

- 차수가 0인 노드, 즉 자식이 없는 노드를 리프 노드 또는 단말 노드라 부른다.

- 그리고 노드의 차수 중에서 가장 큰 차수는 트리의 차수가 된다. (A의 차수 3)

 

- 한 노드의 높이는 루트에서 그 노드에 이르는 경로에 있는 간선의 수가 된다.

- 예를들어, B의 높이는 1, E의 높이는 2가 된다.

- 그리고 노드의 높이 중에서 가장 큰 높이가 그 트리의 전체 높이가 된다. (J의 높이 3)

 

 

* 이진 트리(Binary Tree)

- 모든 노드의 차수를 2 이하로 정하여 전체 트리의 차수가 2 이하가 되도록 만든 것이 이진 트리이다.

 

① 이진 트리는 2개의 자식노드를 모두 가진 경우

② 왼쪽 자식노드만 가지고 오른쪽 자식노드는 공백인 경우

③ 왼쪽 자식노드는 공백이고 오른쪽 자식노드만 가진 경우

- 위 3가지가 이진트리의 기본 구조이다.

 

[ 이진 트리의 추상 자료형 ]

 

createBT()	공백 이진 트리를 생성하는 연산
isEmpty(bt)	이진 트리가 공백인지 아닌지를 확인하는 연산
makeBT(bt1, item, bt2)	두 개의 이진 서브 트리를 연결하여 하나의 이진 트리를 만드는 연산
leftSubtree(bt)	이진 트리의 왼쪽 서브 트리를 구하는 연산
rightSubtree(bt)	이진 트리의 오른쪽 서브 트리를 구하는 연산
data(bt)	이진 트리에서 루트 노드의 데이터를 구하는 연산

- 이진 트리의 추상 자료형에 따라서 만들어진 이진 트리는 3가지 특징을 갖는다.

 

① n개의 노드를 가진 이진 트리는 항상 (n-1)개의 간선을 가진다.

② 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 된다.

③ 높이가 h인 이진 트리가 기질 수 있는 노드의 최대 개수는 (

 )개가 된다.

 

[ 이진 트리의 분류 ]

 

① 포화 이진 트리

- 포화 이진 트리는 모든 레벨에 노드가 꽉 차서 포화 상태인 이진 트리를 의미한다.

 

② 완전 이진 트리

- 완전 이진 트리는 높이가 h고, 노드 수가 n개 일 때, 노드의 위치가 포화 이진 트리의 노드 1번부터 n번까지의 위치와 완전히 일치하는 이진 트리이다.

 

③ 편향 이진 트리

- 이진 트리 중에서 최소 개수의 노드를 가지면서 왼쪽이나 오른쪽 서브  트리만 가지고 있는 트리를 편향 이진 트리(Skewed Binary Tree)라 한다.