logo

전체 이진 트리와 완전 이진 트리의 차이점

이진 트리



다른 이진 트리의 종류 하지만 여기서는 완전한 이진 트리 그리고 완전 이진 트리 .

완전 이진 트리:

완전 이진 트리는 다음과 같은 이진 트리입니다. 모든 노드에는 0 또는 2개의 자손이 있습니다. . 즉, 완전 이진 트리는 리프 노드를 제외한 모든 노드가 두 개의 자손을 갖는 이진 트리입니다.



파일 리눅스 수정

완전 이진 트리

자바 반환 명령

허락하다, 내부 노드의 수
N 총 노드 수
잎의 개수가 되다
레벨 수

그 다음에,



잎의 수는 (나는 + 1) .
총 노드 수는 다음과 같습니다. (2i + 1) .
내부 노드의 수는 (n – 1) / 2 .
잎의 수는 (n + 1) / 2 .
총 노드 수는 다음과 같습니다. (2l – 1) .
내부 노드의 수는 (l – 1) .
잎의 수는 최대 (2- 1) .

완전한 이진 트리:

이진 트리는 다음과 같다고 합니다. 완전 이진 트리 마지막 레벨을 제외한 모든 레벨이 가능한 최대 노드 수를 가지며, 해당 레벨의 모든 노드가 마지막 레벨은 최대한 왼쪽에 표시됩니다. .

완전한 이진 트리

여기에서 알 수 있는 두 가지 점이 있습니다.

  1. 리프 노드의 가장 왼쪽 부분은 항상 먼저 채워져야 합니다.
  2. 마지막 리프 노드에 오른쪽 형제가 있을 필요는 없습니다.

더 나은 방법으로 전체 및 완전한 이진 트리를 이해하려면 다음 예를 확인하십시오.

JSON 예제의 JSON

예시 1:

완전하지도 완전하지도 않음

  • 마디 그러므로 자녀가 한 명뿐입니다. 완전 이진 트리가 아닙니다.
  • 마디 또한 오른쪽 자식은 있지만 왼쪽 자식은 없습니다. 또한 완전한 이진 트리도 아닙니다.

따라서 위에 표시된 이진 트리는 다음과 같습니다. 완전하거나 완전 이진 트리가 아닙니다.

예시 2:

트리 순회

가득 차 있지만 완전하지는 않음

  • 모든 노드에는 다음 중 하나가 있습니다. 0 또는 2 그러므로 자손은 완전 이진 트리이다 .
  • 노드가 있기 때문에 완전한 이진 트리가 아닙니다. 자식이 없지만 노드는 없습니다. 자식이 있고 완전한 이진 트리에 따르면 노드는 다음에서 채워져야 합니다. 왼쪽 .

따라서 위에 표시된 이진 트리는 다음과 같습니다. 완전 이진 트리 그리고 그건 완전한 이진 트리가 아닙니다.

예시 3:

안드로이드에서 차단된 번호를 찾는 방법

완전하지만 완전하지는 않음

    모든 노드가 채워져 있으므로 완전한 이진 트리입니다.
  • 노드 B에는 자식이 하나만 있으므로 완전한 이진 트리가 아닙니다.

따라서 위에 표시된 이진 트리는 다음과 같습니다. 완전한 이진 트리 그리고 그건 완전 이진 트리가 아닙니다.

예시 4:

완전하고 가득 차 있습니다.

  • 이것은 완전한 바이너리 모든 노드가 트리이기 때문에 왼쪽이 채워짐 .
  • 모든 노드에는 다음 중 하나가 있습니다. 0 또는 2 자식, 그러므로 그것은 완전 이진 트리 .

따라서 위에 표시된 이진 트리는 다음과 같습니다. 완전하고 완전한 이진 트리.

예 아니오. 완전한 이진 트리 완전 이진 트리
1. 완전한 이진 트리에서 마지막 수준의 노드는 자식을 하나만 가질 수 있습니다. 완전 이진 트리에서 노드는 자식을 하나만 가질 수 없습니다.
2. 완전한 이진 트리에서는 노드가 왼쪽에서 오른쪽으로 채워져야 합니다. 전체 이진 트리에는 노드를 채우는 순서가 없습니다.
삼. 완전 이진 트리는 주로 힙 기반 데이터 구조에 사용됩니다. 완전 이진 트리는 그 자체로는 적용할 수 없지만 적절한 이진 트리라고도 합니다.
4. 완전 이진 트리는 거의 완전한 이진 트리라고도 합니다. 완전 이진 트리는 고유 이진 트리 또는 2-트리라고도 합니다.
5 완전한 이진 트리는 전체 리프 노드가 정확히 동일한 깊이에 있어야 합니다.
전체 이진 트리에서는 리프 수준이 반드시 동일한 깊이에 있을 필요는 없습니다.