우리는 나무 비선형 데이터 구조입니다. 자녀 수에는 제한이 없습니다. ㅏ완전 이진 트리란 무엇입니까?
완전 이진 트리는 가능한 한 왼쪽부터 채워지는 가장 낮은 수준의 노드를 제외하고 트리의 모든 수준이 완전히 채워지는 특별한 유형의 이진 트리입니다.
완전한 이진 트리
완전 이진 트리의 일부 용어:
- 뿌리 – 상위 노드에서 엣지가 나오지 않는 노드. 예 -노드 A
- 어린이 – 들어오는 에지가 있는 노드를 자식이라고 합니다. 예 – 노드 B, F는 각각 A와 C의 하위입니다.
- 형제자매 – 동일한 상위를 갖는 노드는 형제입니다. 예 - D, E는 동일한 부모 B를 갖고 있으므로 형제입니다.
- 노드의 정도 – 특정 부모의 자녀 수. 예 - A 등급은 2이고 C 등급은 1입니다. D 등급은 0입니다.
- 내부/외부 노드 – 리프 노드는 외부 노드이고 리프 노드가 아닌 노드는 내부 노드입니다.
- 수준 – 대상 노드에 도달하기 위한 경로의 노드 수를 계산합니다. 예 - 노드 A와 B가 경로를 형성하므로 노드 D의 수준은 2입니다.
- 키 – 대상 노드에 도달하기 위한 간선 수, 루트의 높이는 0입니다. 예 – 루트에서 두 개의 간선이 있으므로 노드 E의 높이는 2입니다.
완전 이진 트리의 속성:
- 완전 이진 트리는 모든 리프가 동일한 깊이를 갖는 고유 이진 트리라고 합니다.
- 완전한 이진 트리에서 깊이에 있는 노드 수 디 ~이다 2 디 .
- 완전한 이진 트리에서 N 트리의 노드 높이는 로그(n+1) .
- 모든 레벨 마지막 레벨을 제외하고 완전히 가득 찼습니다.
완벽한 이진 트리 vs 완전 이진 트리:
최대 노드 수를 갖는 높이 'h'의 이진 트리는 다음과 같습니다. 완벽한 이진 트리.
주어진 높이에 대해 시간 , 최대 노드 수는 다음과 같습니다. 2 h+1 -1 .
ㅏ 완벽한 높이 h의 이진 트리는 최대 높이까지의 완벽한 이진 트리입니다. h-1 , 마지막 레벨 요소는 왼쪽에서 오른쪽 순서로 저장됩니다.
예시 1:
이진 트리
주어진 이진 트리의 높이는 2이고 해당 트리의 최대 노드 수는 n= 2입니다.h+1-1 = 22+1-1 = 2삼-1 = 7 .
따라서 우리는 다음과 같이 결론을 내릴 수 있습니다. 완벽한 이진 트리 .
이제 완전한 이진 트리의 경우 높이까지 가득 차 있습니다. h-1 즉.; 1, 마지막 레벨 요소는 왼쪽에서 오른쪽 순서로 저장됩니다. 따라서 완전한 이진 트리이기도 합니다. 다음은 배열에 저장될 때 요소의 표현입니다.
레벨별로 배열에 저장된 요소
배열에는 모든 요소가 연속적으로 저장됩니다.
예시 2:
목록 정렬 자바
이진 트리
주어진 이진 트리의 높이는 2이고 있어야 하는 최대 노드 수는 2입니다.h+1– 1 = 22+1– 1 = 2삼– 1 = 7 .
그러나 트리의 노드 수는 6 . 따라서 그것은 완벽한 이진 트리가 아님 .
이제 완전한 이진 트리의 경우 높이까지 가득 차 있습니다. h-1 즉.; 1 , 마지막 레벨 요소는 왼쪽에서 오른쪽 순서로 저장됩니다. 따라서 이것은 완전 이진 트리 . 요소를 배열에 저장하면 다음과 같습니다.
레벨별로 배열에 저장된 요소
예시 3:
알리사 만요녹
이진 트리
이진 트리의 높이는 2이고 존재할 수 있는 최대 노드 수는 7이지만 노드는 5개이므로 완벽한 이진 트리가 아님 .
완전한 이진 트리의 경우 마지막 레벨의 요소가 왼쪽에서 오른쪽 순서로 채워지지 않음을 알 수 있습니다. 그래서 그렇습니다 완전한 이진 트리가 아님 .
레벨별로 배열에 저장된 요소
배열의 요소는 연속적이지 않습니다.
완전 이진 트리 대 완전 이진 트리:
완전 이진 트리의 경우 모든 노드에는 2개의 자식 또는 0개의 자식이 있습니다.
예시 1:
이진 트리
주어진 이진 트리에는 1차를 갖는 노드가 없으며 모든 노드에 대해 2개 또는 0개의 자식이 있으므로 다음과 같습니다. 완전 이진 트리 .
완전한 이진 트리의 경우 요소는 마지막 수준의 가장 왼쪽이 아닌 수준별로 저장됩니다. 따라서 이것은 완전한 이진 트리가 아님 . 배열 표현은 다음과 같습니다:
레벨별로 배열에 저장된 요소
예시 2:
이진 트리
주어진 이진 트리에는 차수가 1인 노드가 없습니다. 모든 노드는 2 또는 0의 차수를 갖습니다. 따라서 이는 완전 이진 트리 .
완전한 이진 트리의 경우 요소는 수준별로 저장되며 마지막 수준의 가장 왼쪽부터 채워집니다. 그러므로 이것은 완전 이진 트리 . 다음은 트리의 배열 표현입니다.
레벨별로 배열에 저장된 요소
예시 3:
이진 트리
주어진 이진 트리에서 노드 B는 완전 이진 트리의 속성을 위반하는 차수 1을 갖습니다. 완전한 이진 트리가 아님
자바의 문자열에서
완전한 이진 트리의 경우 요소는 수준별로 저장되며 마지막 수준의 가장 왼쪽부터 채워집니다. 따라서 이것은 완전 이진 트리 . 이진 트리의 배열 표현은 다음과 같습니다.
레벨별로 배열에 저장된 요소
예시 4:
이진 트리
팬더 로크
주어진 이진 트리에서 노드 C는 완전 이진 트리의 속성을 위반하는 차수 1을 갖습니다. 완전한 이진 트리가 아님
완전한 이진 트리의 경우 요소는 수준별로 저장되며 마지막 수준의 가장 왼쪽부터 채워집니다. 여기서 노드 E는 조건을 위반합니다. 따라서 이것은 완전한 이진 트리가 아님 .
완전한 이진 트리 생성:
우리는 완전 이진 트리 마지막 수준을 제외한 트리입니다(예: 엘 )다른 모든 레벨에는 ( 2리터 ) 노드와 노드는 왼쪽에서 오른쪽으로 정렬됩니다.
배열을 사용하여 표현할 수 있습니다. 부모가 인덱스라면 나 그래서 왼쪽 아이는 2i+1 그리고 오른쪽 아이는 에 있어요 2i+2 .
완전한 이진 트리와 그 배열 표현
연산:
생성을 위해 완전한 이진 트리 , 우리는 1 단계: 트리가 비어 있으면 새 노드로 루트를 초기화합니다.
2 단계: 트리가 비어 있지 않으면 앞쪽 요소를 가져옵니다.
- 앞 요소에 왼쪽 자식이 없으면 왼쪽 자식을 새 노드로 설정합니다.
- 올바른 자식이 없으면 올바른 자식을 새 노드로 설정하십시오.
3단계: 노드에 두 자식이 모두 있으면 팝 대기열에서 가져옵니다.
4단계: 새 데이터를 대기열에 넣습니다.
삽화:
아래 배열을 고려하십시오.
그리드 레이아웃1. 첫 번째 요소는 루트(인덱스 값 = 0 )
A는 루트로 간주됩니다.
2. 다음 요소(인덱스 = 1 )가 왼쪽이고 세 번째 요소(색인 = 2 )는 루트의 오른쪽 자식이 될 것입니다
B는 왼쪽 자식, D는 오른쪽 자식
3. 네 번째(색인 = 삼 ) 및 다섯 번째 요소(색인 = 4 )는 B 노드의 왼쪽 및 오른쪽 자식이 됩니다.
E와 F는 B의 왼쪽과 오른쪽 자식입니다.
4. 다음 요소(색인 = 5 )는 노드 D의 자식으로 남게 됩니다.
G는 D 노드의 왼쪽 자식으로 만들어집니다.
이것이 완전한 이진 트리가 생성되는 방법입니다.
구현: 레벨 순서 순회에서 완전한 이진 트리를 구축하는 구현에 대한 내용은 다음과 같습니다. 이 게시물 .
완전 이진 트리의 적용:
- 힙 정렬
- 힙 정렬 기반 데이터 구조
주어진 이진 트리가 완전한지 확인하십시오. 따르다 이 게시물 주어진 이진 트리가 완전한지 여부를 확인합니다.