[자료구조] 트리(Tree) 정의 및 용어 정리

Tree는, 하나 이상의 노드로 이루어진 유한집합으로서, 하나의 루트 노드와 분리 집합으로 분할된 다른 노드들의 집합이다.

 

앞서 다루었던 다른 자료구조와 달리(stack,queue,linkedlist) 원소들 간에 1:n 관계를 가지는 비선형 자료구조이며, 원소들 간에 계층 관계를 가지는 계층형 자료구조이다.

 

[Tree의 주요 용어 및 개념]

node: 트리의 구성 요소

서브트리: 하나의 노드와 그 노드들의 자손으로 이루어진 트리

노드의 차수: 노드의 서브트리 개수

루트 노드: 부모가 없는 노드(최상위 노드)

단말 노드: 자식이 없는 노드, 차수 0

형제 노드: 부모가 같은 자식들

트리의 차수: max{노드의 차수}

노드 레벨: 트리의 각 층의 번호

트리의 높이: max{노드 레벨}

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