이진 트리의 5가지 속성

이진 트리에는 다음과 같은 다섯 가지 속성이 있습니다.

1 이진 트리의 i번째(ｉ>=1) 수준에는 최대 2＾(ｉ - 1)개의 노드가 있습니다.

2. 깊이가 k(k>=0)인 이진 트리에는 최소 k개의 노드와 최대 2＾ｋ-1개의 노드가 있습니다.

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

4. n개의 노드가 있는 완전한 이진 트리의 깊이는 int_UP(log(2,ｎ+1))입니다.

5. n개의 노드가 있는 완전한 이진 트리가 위에서 아래로 구성되면 동일한 레이어의 노드에는 왼쪽에서 오른쪽으로 연속적으로 1, 2, 3의 번호가 지정됩니다. ． ． ． ． ． , n을 입력하고, 이 노드 번호에 따라 트리의 각 노드를 1차원 배열로 순차적으로 저장하고, i번 노드를 노드 i(i>=1 && i

(1) ｽi= 1이면 노드 i는 루트이고 ｽi> 1이면 노드 i의 상위 노드는 노드 int_DOWN(ｉ / 2)입니다. 2) 2*i

(3) 2*i

(4) 노드 번호 i가 홀수이고 i! =1, 오른쪽 형제 위치에 있으면 왼쪽 형제는 노드 i-1입니다.

(5) 노드 번호 i가 짝수이고 i! =n, 왼쪽 형제 위치에 있고 오른쪽 형제는 노드 i+1입니다.

(6) 노드 i의 레벨은 int_DOWN(log(2, i)) + 1입니다.

일부 속성 증명

속성 1은 수학적 귀납법으로 증명 가능

속성 2 증명:

속성 1에서 볼 수 있듯이 ｋ 레이어의 최대 총 노드 수는 2개로 표현 가능 ＾0+2＾ 1+...+2^ (| 두 개의 가장자리를 연결하고, 하나의 가장자리를 n1 아래에 연결하고, n 노드를 2개씩 연결합니다. 총 n-1개의 가장자리가 필요하며 2*n2+n1=n을 얻을 수 있습니다. -1. 이것은 공식 (2)입니다.

공식 (1) - (2) 공식에서

ｎ0-ｎ2=1을 얻을 수 있습니다.

위 내용은 이진 트리의 5가지 속성의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!