[Data Structure] 비선형 - 이진 트리(Binary Tree)

#구체적인 설명

• 그래프의 일종 ➡️ 한 노드에서 시작해서 다른 정점(Edge)들을 순회하여 자신에게 돌아오는 순환이 없는 연결 그래프
• 부모 - 자식 관계로 정의가 가능
• 부모에서 자식으로 간선이 이어져 있는 방향성이 있는 그래프
• 용어 정리

https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84)

 

노드: 트리를 구성하는 기본 원소 루트 노드: 트리에서 부모가 없는 최상위 노드, 트리의 시작점 부모 노드: 루트 노드 방향으로 직접 연결된 노드 자식 노드: 루트 노드 반대 방향으로 직접 연결된 노드 형제 노드: 같은 부모 노드를 갖는 노드 리프 노드: 루트 노드를 제외한 차수가 1인 정점 ➡️ 말단, 단말에 있는 노드 경로: 한 노드에서 다른 노드로 이르는 길 사이에 있는 노드들의 순서 길이: 출발 노드에서 도착 노드까지 거치는 간선(Edge)의 갯수 깊이: 류투 경로의 길이 레벨: 루트 노드(level = 0)부터 노드까지 연결된 간선 수의 합 차수: 각 노드의 자식의 개수 트리의 차수: 트리의 최대 차수 크기: 노드의 갯수 너비: 가장 많은 노드를 갖고 있는 레벨의 크기 내부 정점: 차수가 2 이상인 정점 포레스트: 서로 독립인 트리들의 모임

• 이진 트리 종류

정 이진 트리(Full Binary Tree): 모든 트리의 자식은 0개 or 2개 이다  포화 이진 트리(Perfect Binary Tree) - 모든 리프 노드의 높이가 같고 리프노드가 아닌 노드는 모두 2개의 자식을 갖는다. ➡️ 서브 트리까지 모두 빈 곳 없이 꽉찬 트리 - 노드의 개수는 n = 2^(높이) - 1 - 포화 이진 트리 (Perfect Binary Tree) ⊂  정 이진 트리 (Full Binary Tree) 완전 이진 트리(Complete Binary Tree) - 모든 리프노드의 높이가 1차이가 남 - 트리의 원소를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간 형태 - 포화 이진 트리 (Perfect Binary Tree) ⊂ 완전 이진 트리(Complete Binary Tree)

# 그림

https://ssocoit.tistory.com/217