이해해야 할 이진 트리 공식

1. 일반 이진 트리의 속성

속성 1. 비어 있지 않은 이진 트리의 i 수준에는 최대 2^i 노드가 있습니다.

속성 2. 높이 K인 이진 트리에는 최대 2^(k+1)-1개의 노드가 있습니다.

속성 3. 비어 있지 않은 이진 트리의 경우 리프 노드 수가 n0이고 차수가 2인 노드 수가 n2이면 n0=n2+1입니다.

2, 완전 이진 트리

정의: 이진 트리에서 맨 아래 두 수준의 노드 차수만 2보다 작고, 다른 수준의 노드 차수는 모두 2입니다. 최하위 레벨의 노드는 모두 레이어의 가장 왼쪽 위치에 집중되어 있으며, 이 이진 트리를 완전 이진 트리라고 합니다.

속성 1. n 노드가 있는 완전한 이진 트리의 높이 k는 [log^2n]입니다.

속성 2. n 노드가 있는 완전한 이진 트리의 경우, 이진 트리의 모든 노드가 0에서 n으로 시작하여 위쪽(루트 노드)에서 아래쪽(리프 노드)으로 순서대로 시작하고 왼쪽에서 오른쪽으로 -1의 번호가 지정되면, 첨자 i가 있는 노드의 경우 다음이 있습니다.

(1) i=0이면 루트 노드이고 i>0이면 상위 노드가 없습니다. 상위 노드의 첨자는 ( i-1)/2.

(2) 2i+1<=n-1이면 첨자 i가 있는 노드의 왼쪽 자식 노드의 첨자는 2i+1입니다. 그렇지 않으면 첨자 i가 있는 노드에는 왼쪽 자식 노드가 없습니다.

(3) 2i+2<=n-1이면 첨자 i가 있는 노드의 오른쪽 자식 노드의 첨자는 2i+2입니다. 그렇지 않으면 첨자 i가 있는 노드에는 오른쪽 자식 노드가 없습니다.

3. 완전 이진 트리

정의: 이진 트리의 노드가 리프이거나 비어 있지 않은 두 개의 하위 트리가 있는 경우 이진 트리를 완전 이진 트리라고 합니다.

속성, 완전 이진 트리에서는 리프 노드 수가 가지 노드 수보다 1개 더 많습니다.

4. 확장 이진 트리

정의: 확장 이진 트리는 확장 후 원래 이진 트리의 노드가 2차 분기 노드가 됩니다. 즉, 원래 노드의 차수가 2이면 변경되지 않고 유지됩니다. 차수가 1이면 하나의 분기가 추가되고, 차수가 0이면 두 개의 분기가 추가됩니다.

속성 1. 확장 이진 트리에서는 외부 노드 수가 내부 노드 수보다 1개 더 많습니다.

속성 2. 확장 이진 트리의 경우 외부 경로 길이 E와 내부 경로 길이 I 간에 다음 관계가 충족됩니다. E=I+2n, 여기서 n은 내부 노드 수입니다.

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

위 내용은 이해해야 할 이진 트리 공식의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!