[자료구조] 트리란...

[자료구조] 트리란...[자료구조] 트리란...[자료구조] 트리란...

리스트와 스택, 큐는 자료들이 선의 형태로 나열되어 있는 구조를 가진 선형 자

료구조였다. 자료들이 나열된 구조가 선형이 아닌 자료구조를 비선형 자료구조

라고 하는데, 트리(tree)는 비선형 자료구조 중에서 자료들간에 계층관계를 가

진 계층형 자료구조다. 흔히 우리가 알고있는 가계도가 바로 계층형 자료구조

이다.

가계도에서 가족 구성원을 연결하는 선은 부보 자식 관계를 나타낸다. 가계도

의 시작을 루트로 보고, 그 아래 자식노드는 1세대(레벨1)그 아래의 자식노드들

은 2세대(레벨 2) 라고 볼 수 있다.

트리를 구성하는 원소는 노드라고 하고 노드를 연결하는 선을 간선(edge)이라

고 한다. 같은 부모 노드의 자식 노드들은 서로 형제 노드가 된다. 한 노드에서

간선을 따라 루트 노드까지 이르는 경로에 있는 노드들은 모두 그 노드의 조상

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

각 노드의 자식 노드 수만큼의 서브 트리를 갖는다. 한 노드의 자손 노드들은

그 노드의 서브 트리에 있는 노드들이 된다.

한 노드가 가지는 서브 트리의 수, 즉 자식 노드의 수를 그 노드의 차수라 한다.
한 노드의 높이는 루트에서 그 노드에 이르는 경로에 있는 간선의 수가 되고,

노드의 높이 중에서 가장 큰 값, 즉 최대 레벨이 그 트리의 높이가 된다.

나무가 모이면 숲이 되듯이 여러 트리들의 집합을 포레스트 라고 한다. n개의

서브트리를 가진 루트 노드를 제거하면 n개의 분리된 트리가 생겨서 포레스트

를 이룬다.

[자료구조] 트리란...[자료구조] 트리란...[자료구조] 트리란...