이진 트리의 기본 속성

컴퓨터 과학에서 이진 트리는 노드당 최대 2개의 하위 트리가 있는 트리 구조입니다. 일반적으로 하위 트리를 "왼쪽 하위 트리" 및 "오른쪽 하위 트리"라고 합니다. 이진 트리는 이진 검색 트리와 이진 힙을 구현하는 데 자주 사용됩니다.

깊이 k와 2^k-1 노드를 갖는 이진 트리를 완전 이진 트리라고 합니다. 이런 종류의 트리의 특징은 각 레벨의 노드 수가 최대 노드 수라는 것입니다. 이진 트리에서 마지막 수준을 제외한 모든 수준이 가득 차 있고 마지막 수준이 가득 차거나 오른쪽에 여러 개의 연속 노드가 부족한 경우 이진 트리는 완전한 이진 트리입니다. n개의 노드를 갖는 완전한 이진 트리의 깊이는 바닥(log2n)+1입니다. 깊이가 k인 완전한 이진 트리에는 최소 2k-1개의 리프 노드와 최대 2k-1개의 노드가 있습니다.

이진 트리 속성

(1) 비어 있지 않은 이진 트리에서 레벨 i의 총 노드 수는 , i>=1을 초과하지 않습니다.

(2) 깊이가 h인 이진 트리는 최대 노드( h>=1), 적어도 h 개의 노드가 있습니다.

(3) 임의의 이진 트리에 대해 리프 노드의 수가 N0이고 차수가 2인 총 노드 수가 N2이면 N0=N2+1;

(4) n 노드가 있는 완전한 이진 트리의 깊이는 입니다(참고: [ ]는 반내림을 의미함)

추천 과정: PHP 튜토리얼.

(5) N개의 노드가 있는 완전한 이진 트리의 각 노드가 순차적 방식으로 저장되는 경우 노드는 다음과 같은 관계를 갖습니다.

I가 노드 번호이면 I>1이면 상위 노드입니다. 숫자는 I/2입니다.

2*I<=N이면 왼쪽 하위 트리의 루트 노드 수는 2*I입니다. 왼쪽 자식

2*I+1<=N이면 오른쪽 자식의 노드 번호는 2*I+1>N이면 오른쪽 자식이 없습니다.

(6) N개의 노드가 주어지면 h(N)개의 서로 다른 이진 트리가 형성될 수 있습니다.

h(N)은 카텔란 수의 N번째 항입니다. h(n)=C(2*n,n)/(n+1).

(7) i개의 가지점이 있고, I는 모든 가지점의 도로 길이의 합, J는 나뭇잎의 도로 길이의 합 J=I+2i [2]

기본 개념

이진 트리는 재귀적으로 정의되며, 해당 노드는 왼쪽과 오른쪽 하위 트리로 나누어집니다. 논리적으로 이진 트리에는 다섯 가지 기본 형태가 있습니다.

(1) 빈 이진 트리 - (a)에 표시된 대로; 루트 노드가 하나만 있는 이진 트리 - 예: 그림 (b)

(3) 왼쪽 하위 트리만 - (c)와 같이

(4) 오른쪽 하위 트리만 - (d)와 같이; (5) 완전한 이진 트리 - (e)와 같습니다.

참고: 이진 트리는 나무와 많은 유사점이 있지만 이진 트리는 나무의 특별한 경우가 아닙니다. [1]

Type

(1) 완전 이진 트리 - 이진 트리의 높이가 h라면 h번째 레이어를 제외하고 각 레이어의 노드 수(1~h-1)는 레이어 h에는 리프 노드가 있으며 리프 노드는 왼쪽에서 오른쪽으로 배열됩니다. 이는 완전한 이진 트리입니다. (2) 완전 이진 트리 - 리프 노드를 제외한 모든 노드가 왼쪽 및 오른쪽 하위 리프를 갖고 리프 노드가 모두 아래쪽에 있는 이진 트리입니다.

(3) 균형 이진 트리 - 균형 이진 트리는 AVL 트리라고도 합니다(AVL 알고리즘과 다름). 이진 정렬 트리이며 다음과 같은 속성을 갖습니다. 빈 트리이거나 왼쪽 및 오른쪽 자식입니다. 트리의 높이 차이의 절대값은 1을 초과하지 않으며, 왼쪽과 오른쪽 하위 트리는 모두 균형 이진 트리입니다.

차별

이진 트리는 트리와 많은 유사점이 있지만 트리와 이진 트리 사이에는 두 가지 주요 차이점이 있습니다. 1 최대 노드 수준에는 제한이 없습니다. 트리에서 이진 트리 노드의 최대 차수는 2입니다.

2. 트리의 노드는 왼쪽과 오른쪽으로 나뉘지 않지만 이진 트리의 노드는 왼쪽과 오른쪽으로 나뉩니다.

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