[자료구조] 9강 트리

정의

- 그래프 중에서 사이클을 포함하지 않는 연결 그래프로서의 임의의 노드에서 다른 노드로의 경로가 하나 밖에 없는 것을 트리라한다.

트리는 계층적인 자료구조로 노드와 각 노드를 연결하는 간선들로 구성

노드 중에서 단 하나의 루트 노드가 존재하고 루트 노드에서 다른 하위노드들이 간선들로 연결된 비선형 구조의 계층 구조

트리의 종류에는 이진트리, 전 이진 트리, 포화 이진 트리, 사향 트리들이 있다.

트리의 응용 분야는 계층적인 조직, 디택토리 구조, 인공지능에서 의사결정 구조등을 표현하는 결정 트리를 표현하는데 사용된다.

 

2. 용어

노드와 차수 : 밑으로 나뉘는 개수 (한 노드가 가지고 있는 서브 트리의 수)

단말 노드와 비단말 노드 : 단말 노드는 차수가 0인 노드를 말한다., 리프,노드 또는 터미널 노드라고도 부른다.

부모 노드와 자식 노드 : 노드의 부모노드는 어떤 하나의 노드에 대하여 상위에 연결된 노드를 말하며 하위에 연결된 노드는 자식 노드라 한다.

트리의 차수 : 트리에 있는 노드의 최대 차수를 트리의 차수라한다.

노드의 레벨 : 루트노드가 레벨 0에 해당되고 자식 노드로 내려갈수록 레벨이 1씩 증가

트리의 깊이 : 최대 레벨이 3이면 높이도 3

포리스트 : 루트 노드를 제거 했을 때 만들어지는 트리들

 

3. 트리의 표현

트리의 표현 방법은 리스트 구조를 사용할 수 있다.