이진 트리 노드를 계산하는 방법

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

2. 깊이가 h인 트리에는 최대 2^k-1개의 노드가 있습니다

3. 이진 트리의 경우 n0개의 리프 노드와 2차 노드가 n2개 포함되어 있으면 다음과 같은 관계가 있어야 합니다. n2= n0-1

4. n 노드가 있는 완전한 이진 트리의 깊이는 [log2n]+1입니다. []는 반올림

5을 의미합니다. n 노드의 완전한 이진 트리는 위에서 아래로, 왼쪽에서 오른쪽으로 1부터 n까지 번호가 지정됩니다. 그런 다음 완전한 이진 트리에서 i 번호가 지정된 모든 노드에 대해:

i=1인 경우 노드는 이진 트리의 루트이며 부모가 없습니다. 그렇지 않으면 번호가 [i/2]인 노드가 부모 노드입니다.

2i>n이면 노드에 왼쪽 자식 노드가 없습니다. , 그렇지 않으면 번호가 2i인 노드는 왼쪽 자식 노드입니다.

2i+1>n이면 노드에는 오른쪽 자식 노드가 없습니다. 그렇지 않으면 번호가 2i+1인 노드가 오른쪽입니다. 자식 노드.

완전한 이진 트리의 노드 수가 n이면 n0, n1, n2, number의 높이 h, 왼쪽 자식 노드 수 nl, 오른쪽 자식 노드 수 nr을 구합니까?

(n0은 차수가 0인 노드, n1은 차수가 1인 노드, n2는 차수가 2인 노드)

위 내용은 이진 트리 노드를 계산하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!