9-1. 트리의 개념

트리 (tree : $T$)

루트(root)라고 하는 특별한 노드(node)에서 시작하는 그래프로, 그래프의 정점에 해당하는 노드 $u, v$ 사이에 $u$에서 $v$로 가는 단순 경로가 존재하는 비순환의 연결그래프

노드 (node)

트리인 그래프 $T$를 구성하는 정점

루트노드 (root node)

트리인 그래프 $T$의 가장 높은 곳에 위치하는 정점으로, 트리 $T$의 시작 노드

부모노드 (parent node)

트리인 그래프 $T$를 구성하는 임의의 노드의 한 단계 상위 노드

자식노드 (child node)

트리인 그래프 $T$를 구성하는 임의의 노드의 한 단계 하위 노드

형제노드 (sibling node)

트리인 그래프 $T$를 구성하는 임의의 노드와 부모가 같은 노드

리프노드 (leaf node)

트리인 그래프 $T$를 구성하는 노드 중 자식노드가 없는 노드

중간노드 (internal node)

트리인 그래프 $T$를 구성하는 노드 중 루트노드나 리프노드가 아닌 노드

조상노드 (ancestor node)

트리인 그래프 $T$의 루프노드부터 임의의 한 노드에 이르는 경로에 포함된 모든 노드

자손노드 (descendant node)