트리(Tree)

노드(Node): 트리를 구성하는 각각의 요소
간선(Edge): 트리를 구성하기 위해 노드와 노드를 연결하는 선

트리는 구조적인 데이터 구조로, 여러 요소들을 계층적으로 나타낼 수 있습니다. 아래는 트리와 관련된 주요 용어들을 정리한 것입니다.

기본 구성 요소

루트(Root): 트리 구조에서 최상위에 있는 노드
깊이(Depth): 루트 노드에서 해당 노드까지 도달하는 데 사용하는 간선의 개수 (루트 노드의 깊이는 0)
레벨(Level): 노드의 깊이 + 1
노드의 차수(Degree of Node): 노드의 자식 수
트리의 차수(Degree of Tree): 해당 트리 내 모든 노드의 차수 중 최댓값
높이(Height): 루트 노드에서 해당 노드까지 도달하는데 지나간 정점의 개수 (노드 중 가장 높이가 높은 노드의 높이를 트리의 높이라고 함)
단말 노드(Terminal or Leaf Node): 하위에 다른 노드가 연결되어 있지 않은 노드
내부 노드(Internal Node): 단말 노드를 제외한 모든 노드 (루트 노드 포함)
부모 노드(Parent Node): 상위 계층의 노드
자식 노드(Child Node): 하위 계층의 노드
형제 노드(Sibling Node): 동일한 부모 노드를 공유하는 노드들
조상 노드(Ancestor Node): 한 노드의 부모 노드부터 루트 노드까지의 경로에 존재하는 모든 노드
후손 노드(Descendant Node): 한 노드를 루트로 하는 서브트리에 있는 모든 노드

이진트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 이는 트리의 각 노드가 왼쪽 자식과 오른쪽 자식, 총 두 개까지만 가질 수 있음을 의미합니다.