ㅏ

이진 트리

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

완전 이진 트리:

완전 이진 트리는 다음과 같은 이진 트리입니다. 모든 노드에는 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 자식, 그러므로 그것은 완전 이진 트리 .

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