트리(Tree)

트리란?

임의의 노드에서 다른 노드로의 경로가 하나 밖에 없는 자료구조.

노드 중에 단 하나의 루트 노드(Root Node)가 있고, 루트 노드에서 하위 노드(Sub Node)들이 연결된 비선형 계층 구조.

 

종류

일반 트리

이진 트리 : 다음 데이터를 가리키는 것이 2개인 단방향 트리 구조. 한 노드의 자식 노드가 최대 2개인 트리 구조.

 

용도

운영체제의 파일 시스템

 

구현 방법

배열이나 연결 리스트

 

용어

깊이(Depth) : 루트 노드로부터의 거리. 루트 노드로부터 특정 노드까지 가기위한 간선의 수. 루트 노드의 깊이는 0이다.

깊이 1의 노드를 뿌리의 자식 노드, 깊이 2의 부모 노드라고도 표현한다.

레벨 : 특정 깊이를 가지는 노드의 집합.

잎(Leap) : 자식 노드가 없는 노드.