트리

• 계층적인 자료의 표현에 적합한 자료구조.

  	ex) 조직도, 가계도, 폴더구조 등

• 컴퓨터에서도 트리는 다양한 응용을 갖는다. 폴더구조를 표현하는 것은 물론이고, 효율적인 탐색을 위한 탐색트리, 우선순위 큐를 위한 힙 트리, 인공지능 문제에서 의사결정 구조를 표현하기 위한 결정 트리 등 매우 광범위하게 활용된다.

• 트리의 모든 노드(Node)는 자신의 서브트리의 루트 노드.

트리의 용어들:

루트(root)노드, 
간선(edge), 
부모(parent)노드, 
자식(child)노드, 
형제(sibling)노드, 
조상(ancestor)노드, 
자손(decendant)노드, 
단말(terminal, leaf)노드,
노드의 차수(degree) : 어떤 노드가 갖고있는 자식의 수.
트리의 차수 : 트리가 가지고 있는 노드의 차수 중에서 가장 큰 차수.
레벨(level) : 트리의 각층에 번호를 매기는 것, 루트는 lev. 1 이고, 한층씩 +1
트리의 높이(height) : 트리가 가지고있는 최대 레벨.
포티스트(forest) : 트리들의 집합.