완전 이진 트리란 무엇입니까?
완전 이진 트리는 다음과 같이 정의될 수 있습니다. 이진 트리 모든 노드에는 0개 또는 2개의 자식이 있습니다. 즉, 완전 이진 트리는 리프 노드를 제외한 모든 노드가 두 개의 자식을 갖는 이진 트리로 정의할 수 있습니다.
부정 이산 수학
아래 트리는 완전 이진 트리입니다.
위의 트리는 리프 노드를 제외한 모든 노드에 두 개의 자식이 있으므로 완전 이진 트리입니다.
완전 이진 트리 정리:
이진 트리 T를 비어 있지 않은 트리로 간주합니다.
- 내가 트리의 내부 노드이고 L이 트리의 리프 노드라고 가정하면 리프 노드의 수는 다음과 같습니다.
엘 = 나 + 1 - T에 I개의 내부 노드가 있고 N이 총 노드 수인 경우 총 노드 수는 다음과 같습니다.
N = 2I + 1 - T가 'N'개의 총 노드 수를 포함하고 'I'가 내부 노드 수인 경우 내부 노드 수는 다음과 같습니다.
나는 = (N-1)/2 - 'T'에 'N'개의 총 노드 수가 있고 'L'이 리프 노드 수인 경우 리프 노드 수는 다음과 같습니다.
L = (N+1)/2 - 'T'에 'L' 수의 리프 노드가 포함된 경우 총 노드 수는 다음과 같습니다.
N = 2L - 1 - 'T'에 리프 노드 수가 'L'개 있고 'I'가 내부 노드 수인 경우 내부 노드 수는 다음과 같습니다.
나는 = L - 1
완전 이진 트리란 무엇입니까?
이진 트리는 왼쪽부터 채워지는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워지는 경우 완전 이진 트리라고 합니다.
아래 트리는 완전한 이진 트리입니다.
완전 이진 트리는 아래에 제시된 두 가지 차이점을 제외하면 완전 이진 트리와 유사합니다.
- 리프 노드 채우기는 가장 왼쪽부터 시작해야 합니다.
- 마지막 리프 노드에 올바른 형제 노드가 있어야 하는 것은 필수는 아닙니다.
예를 통해 위의 사항을 이해해 보겠습니다.
아래 트리를 고려하십시오.
위의 트리는 완전 이진 트리이지만 노드 6에는 오른쪽 형제가 없기 때문에 완전 이진 트리가 아닙니다.
완전한 이진 트리 생성
아래와 같이 6개의 요소로 구성된 배열이 있다고 가정합니다.
위의 배열에는 6개의 요소, 즉 1, 2, 3, 4, 5, 6이 포함되어 있습니다. 다음은 완전한 이진 트리를 만드는 데 사용되는 단계입니다.
1 단계: 먼저 배열의 첫 번째 요소인 1을 선택하고 트리의 루트 노드를 만듭니다. 첫 번째 수준에서 사용할 수 있는 요소 수는 1개입니다.
2 단계: 이제 배열의 두 번째와 세 번째 요소를 선택하겠습니다. 배열의 두 번째 요소와 세 번째 요소를 각각 아래와 같이 루트 노드의 왼쪽 및 오른쪽 자식으로 유지합니다.
위에서 볼 수 있듯이 두 번째 수준에서 사용할 수 있는 요소 수는 2입니다.
3단계: 이제 배열에서 다음 두 요소(예: 4와 5)를 선택합니다. 아래와 같이 노드 2의 왼쪽과 오른쪽에 이 두 요소를 유지합니다.
위에서 볼 수 있듯이 노드 4와 5는 각각 노드 2의 왼쪽과 오른쪽 자식입니다.
4단계: 이제 배열의 마지막 요소인 6을 선택하고 이를 노드 3의 왼쪽 자식으로 유지합니다. 완전한 이진 트리에서 노드는 아래와 같이 왼쪽부터 채워집니다.
두 번째 레벨에는 3개의 요소가 포함되어 있음을 알 수 있습니다.
이미지를 통해 완전 이진 트리와 완전 이진 트리의 차이점을 이해해 보겠습니다.
- 아래에 표시된 이진 트리는 완전한 이진 트리도 아니고 완전한 이진 트리도 아닙니다. 노드 3에는 자식이 하나만 있으므로 완전 이진 트리가 아닙니다. 또한 노드가 왼쪽부터 채워져야 하므로 완전한 이진 트리가 아니지만 노드 3에는 오른쪽 자식이 있고 왼쪽 자식이 없습니다.
- 아래에 표시된 이진 트리는 완전한 이진 트리이지만 완전한 이진 트리는 아닙니다. 모든 노드에는 0개 또는 2개의 자식이 있으므로 완전 이진 트리입니다. 노드 3에는 자식이 없고 노드 2에는 자식이 있으므로 완전한 이진 트리가 아니며 완전한 이진 트리에서는 노드가 왼쪽부터 채워져야 한다는 것을 알고 있습니다.
- 아래에 표시된 이진 트리는 완전한 이진 트리이지만 완전한 이진 트리는 아닙니다. 모든 노드가 채워져 있으므로 완전한 이진 트리입니다. 노드 2에는 자식이 하나만 있으므로 완전 이진 트리가 아닙니다.
- 아래에 표시된 이진 트리는 완전한 이진 트리이자 전체 이진 트리입니다. 모든 노드가 채워져 있으므로 완전한 이진 트리입니다. 모든 노드에는 0개 또는 2개의 자식이 있으므로 완전 이진 트리입니다.
