완전 이진 트리란 무엇인가요?

완전 이진 트리(Complete Binary Tree)

이진 트리의 높이가 h라면 h번째 레이어를 제외하고 다른 모든 레이어의 노드 수(1 ~h-1)이 최대 개수에 도달하면 h번째 레이어에는 오른쪽에서 왼쪽으로 여러 노드가 누락되어 완전한 이진 트리가 됩니다.

리프 노드는 두 개의 가장 큰 수준에만 나타날 수 있습니다. 어떤 노드에서든 오른쪽 가지 아래의 하위 항목의 최대 수준이 L인 경우 왼쪽 가지 아래의 하위 항목의 최대 수준은 L이어야 합니다. 또는 L 1

이진 트리는 다음과 같이 재귀적으로 정의할 수 있는 매우 중요한 유형의 트리 구조입니다.

이진 트리 T는 유한 노드의 집합입니다. 빈 집합 또는 루트 노드 u와 각각 왼쪽 하위 트리 및 오른쪽 하위 트리라고 불리는 두 개의 분리된 이진 트리 u(1) 및 u(2)로 구성됩니다. n, n1, n2가 각각 T의 노드 수 u(1), u(2)를 나타내는 데 사용되면 n=1 n1 n2입니다. u(1)과 u(2)는 각각 T의 첫 번째 및 두 번째 하위 트리라고도 합니다.

따라서 이진 트리의 루트에는 왼쪽 하위 트리가 비어 있거나 오른쪽 하위 트리가 비어 있거나 왼쪽 및 오른쪽 하위 트리가 모두 비어 있을 수 있습니다.

이진 트리에서 각 노드에는 최대 2명의 아들이 있으며 왼쪽과 오른쪽으로 나뉩니다. 따라서 모든 노드의 아들에게는 네 가지 상황만 있습니다. 즉, 왼쪽 아들은 한 명만 있고, 오른쪽 아들은 한 명만 있습니다.