ㅏ
이진 트리
다른 이진 트리의 종류 하지만 여기서는 완전한 이진 트리 그리고 완전 이진 트리 .
완전 이진 트리:
완전 이진 트리는 다음과 같은 이진 트리입니다. 모든 노드에는 0 또는 2개의 자손이 있습니다. . 즉, 완전 이진 트리는 리프 노드를 제외한 모든 노드가 두 개의 자손을 갖는 이진 트리입니다.
파일 리눅스 수정
완전 이진 트리
자바 반환 명령허락하다, 나 내부 노드의 수
N 총 노드 수
엘 잎의 개수가 되다
엘 레벨 수그 다음에,
잎의 수는 (나는 + 1) .
총 노드 수는 다음과 같습니다. (2i + 1) .
내부 노드의 수는 (n – 1) / 2 .
잎의 수는 (n + 1) / 2 .
총 노드 수는 다음과 같습니다. (2l – 1) .
내부 노드의 수는 (l – 1) .
잎의 수는 최대 (2엘- 1) .
완전한 이진 트리:
이진 트리는 다음과 같다고 합니다. 완전 이진 트리 마지막 레벨을 제외한 모든 레벨이 가능한 최대 노드 수를 가지며, 해당 레벨의 모든 노드가 마지막 레벨은 최대한 왼쪽에 표시됩니다. .
완전한 이진 트리
여기에서 알 수 있는 두 가지 점이 있습니다.
- 리프 노드의 가장 왼쪽 부분은 항상 먼저 채워져야 합니다.
- 마지막 리프 노드에 오른쪽 형제가 있을 필요는 없습니다.
더 나은 방법으로 전체 및 완전한 이진 트리를 이해하려면 다음 예를 확인하십시오.
JSON 예제의 JSON
예시 1:
완전하지도 완전하지도 않음
- 마디 씨 그러므로 자녀가 한 명뿐입니다. 완전 이진 트리가 아닙니다.
- 마디 씨 또한 오른쪽 자식은 있지만 왼쪽 자식은 없습니다. 또한 완전한 이진 트리도 아닙니다.
따라서 위에 표시된 이진 트리는 다음과 같습니다. 완전하거나 완전 이진 트리가 아닙니다.
예시 2:
트리 순회가득 차 있지만 완전하지는 않음
- 모든 노드에는 다음 중 하나가 있습니다. 0 또는 2 그러므로 자손은 완전 이진 트리이다 .
노드가 있기 때문에 완전한 이진 트리가 아닙니다. 비 자식이 없지만 노드는 없습니다. 씨 자식이 있고 완전한 이진 트리에 따르면 노드는 다음에서 채워져야 합니다. 왼쪽 .따라서 위에 표시된 이진 트리는 다음과 같습니다. 완전 이진 트리 그리고 그건 완전한 이진 트리가 아닙니다.
예시 3:
안드로이드에서 차단된 번호를 찾는 방법완전하지만 완전하지는 않음
모든 노드가 채워져 있으므로 완전한 이진 트리입니다.
- 노드 B에는 자식이 하나만 있으므로 완전한 이진 트리가 아닙니다.
따라서 위에 표시된 이진 트리는 다음과 같습니다. 완전한 이진 트리 그리고 그건 완전 이진 트리가 아닙니다.
예시 4:
완전하고 가득 차 있습니다.
- 이것은 완전한 바이너리 모든 노드가 트리이기 때문에 왼쪽이 채워짐 .
- 모든 노드에는 다음 중 하나가 있습니다. 0 또는 2 자식, 그러므로 그것은 완전 이진 트리 .
따라서 위에 표시된 이진 트리는 다음과 같습니다. 완전하고 완전한 이진 트리.
예 아니오. | 완전한 이진 트리 | 완전 이진 트리 |
1. | 완전한 이진 트리에서 마지막 수준의 노드는 자식을 하나만 가질 수 있습니다. | 완전 이진 트리에서 노드는 자식을 하나만 가질 수 없습니다. |
2. | 완전한 이진 트리에서는 노드가 왼쪽에서 오른쪽으로 채워져야 합니다. | 전체 이진 트리에는 노드를 채우는 순서가 없습니다. |
삼. | 완전 이진 트리는 주로 힙 기반 데이터 구조에 사용됩니다. | 완전 이진 트리는 그 자체로는 적용할 수 없지만 적절한 이진 트리라고도 합니다. |
4. | 완전 이진 트리는 거의 완전한 이진 트리라고도 합니다. | 완전 이진 트리는 고유 이진 트리 또는 2-트리라고도 합니다. |
5 | 완전한 이진 트리는 전체 리프 노드가 정확히 동일한 깊이에 있어야 합니다. | 전체 이진 트리에서는 리프 수준이 반드시 동일한 깊이에 있을 필요는 없습니다. |