"트리"(Tree) ADT는 계층 구조를 가지는 그래프의 일종으로 비선형 자료구조이다. 그래프의 일종이기 때문에, 노드와 간선으로 이루어져 있다.이때, 각 노드는 하나의 부모 노드만을 가지며, 여러 개의 자식 노드를 가질 수 있다.이러한 계층 구조에 의해 트리에서는 절대로 순환이 발생하지 않는다. 즉, 트리는 각 노드를 한 번씩만 방문했을 때, 절대 순환이 발생하지 않는 연결 그래프이다.  이렇게 최상위의 노드를 루트노드라 부르며, 모든 트리에는 항상 하나만 존재한다. 또한, 트리 구조는 각 노드를 루트 노드로 하여 하위트리로 분류할 수 있으며, 이러한 특성에 의해 재귀적 자료구조라고도 부른다.  루트 노드(root) : 모든 트리에 하나만 존재하며, 부모가 없는 최상위 노드 리프(단말) 노드(leaf)..