[자료구조] 트리

트리란 ? 

사이클이 없이 모든 정점이 연결되어 있는 그래프

정점의 개수가 N개이면 간선의 개수는 N-1이다.

• Node(노드): 트리를 구성하고 있는 각각의 요소
• Edge(간선): 트리에서 노드와 노드 사이를 연결하는 선
• Root Node(루트 노드): 트리 구조에서 최상단에 위치한 노드. 부모가 없는 노드
• Termanal Node(Leaf Node, 단말 노드): 하위에 더이상 다른 노드가 연결되어 있지 않은 노드. 자식이 없는 노드
• Internal Node(내부 노드, 비단말 노드): 단말 노드를 제외한 모든 노드. 루트 노드도 포함.
• 레벨(level, 깊이(depth)): 루트에서 어떤 노드까지의 경로 길이(간선의 수)
• 트리의 높이(height): 트리의 최고 레벨
• 부모 노드: 자신과 연결된 상위 노드
• 자식 노드: 자신과 연결된 하위 노드
• 형제 노드: 같은 부모를 가지는 노드
• 크기(size): 특정 노드가 자신을 포함한 자손의 수
• 노드의 차수(degree): 노드가 가진 자식 노드의 수
• 트리의 차수(degree): 노드의 차수 중 최댓값