완전한 이진 트리의 리프 노드 수

n 노드가 있는 완전한 이진 트리, 리프 노드 수 n0은 n/2 반올림 또는 (n+1)/2 반내림

확장 정보:

완전 이진 트리

완전 이진 트리는 매우 효율적인 데이터 구조입니다. 완전 이진 트리는 완전 이진 트리에서 파생됩니다. 깊이 K와 n개 노드를 갖는 이진 트리의 경우 각 노드가 깊이 K를 갖는 전체 이진 트리에서 1부터 n까지 번호가 매겨진 노드와 일대일로 대응하는 경우에만 완전 이진 트리라고 합니다.

Definition

이진 트리의 깊이가 h라면, h번째 레이어를 제외하고 다른 레이어(1~h-1)의 노드 개수는 최대 개수에 도달하고, 모두 h번째 레이어의 노드 포인트는 완전한 이진 트리인 맨 왼쪽에 연속적으로 집중됩니다.

완전 이진 트리는 완전 이진 트리에서 파생됩니다. 깊이 K와 n개 노드를 갖는 이진 트리의 경우 각 노드가 깊이 K를 갖는 전체 이진 트리에서 1부터 n까지 번호가 매겨진 노드와 일대일로 대응하는 경우에만 완전 이진 트리라고 합니다.

(1) 모든 리프 노드는 k번째 레이어 또는 k-l 레이어(가장 큰 두 레벨)에 나타납니다.

(2) 모든 노드에 대해 오른쪽 하위 트리의 최대 레벨이 L이면 해당 노드의 최대 레벨은 왼쪽 하위 트리는 L 또는 L+l입니다.

이진 트리에서는 기껏해야 하위 두 레벨의 노드 차수가 2보다 작을 수 있으며, 최하위 레벨의 노드가 레벨의 가장 왼쪽 위치에 집중되면 이진 트리는 완전한 트리가 됩니다. 이진 트리, 그리고 가장 낮은 레이어의 노드가 레이어의 가장 왼쪽 위치에 집중되어 있으며, 마지막 레이어에서는 오른쪽의 여러 노드가 누락된 이진 트리가 되며, 이 이진 트리는 완전한 이진 트리가 됩니다. .

자주 묻는 질문과 관련된 더 많은 기술 기사를 보려면 FAQ 칼럼을 방문하여 알아보세요!

위 내용은 완전한 이진 트리의 리프 노드 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!