나는 아래 나무의 용어에 대해 혼란스럽고 나무를 연구하고 있으며 이러한 나무를 구별 할 수 없습니다.
a) 완전한 이진 트리
b) 엄격한 이진 트리
c) 전체 이진 트리
이 나무들을 구별 할 수 있도록 도와주세요. 데이터 구조에서 이러한 트리가 언제 어디서 사용됩니까?
답변
완전한 이진 트리 (때로는 적절한 이진 트리 또는 2- 트리 또는 엄격하게 이진 트리)는 잎을 제외한 모든 노드에 두 개의 자식이있는 트리입니다.
따라서 자식이 하나 뿐인 노드가 없습니다. 엄격한 이진 트리와 동일하게 나타납니다.
다음은 google의 전체 / 엄격 바이너리 트리 이미지입니다.
완전한 이진 트리는 마지막 수준을 제외한 모든 수준이 완전히 채워지고 모든 노드가 가능한 한 왼쪽에있는 이진 트리입니다.
균형 잡힌 나무를 의미하는 것 같습니다.
다음은 Google의 완전한 이진 트리 이미지입니다. 이미지의 전체 트리 부분은 보너스입니다.
답변
완벽한 나무 :
x
/ \
/ \
x x
/ \ / \
x x x x
/ \ / \ / \ / \
x x x x x x x x
완전한 나무 :
x
/ \
/ \
x x
/ \ / \
x x x x
/ \ /
x x x
엄격한 / 전체 트리 :
x
/ \
/ \
x x
/ \
x x
/ \
x x
답변
STRICT와 FULL BINARY TREE에는 차이가 있습니다.
1) FULL BINARY TREE : 정확히 (2 ^ h) -1 요소를 포함하는 높이 h의 이진 트리를 전체 이진 트리 라고합니다 . (참조 : Pg 427, C ++의 데이터 구조, 알고리즘 및 응용 [University Press], Sartaj Sahni의 Second Edition).
또는 다른 말로
FULL BINARY TREE에서 각 노드에는 정확히 0 개 또는 2 개의 자식이 있으며 모든 리프 노드는 동일한 수준에 있습니다.
예 : 다음은 FULL BINARY TREE입니다.
18
/ \
15 30
/ \ / \
40 50 100 40
2) 엄격한 이진 나무 : 각 노드에는 정확히 0 개 또는 2 개의 자식이 있습니다.
예 : 다음은 STRICT BINARY TREE입니다.
18
/ \
15 30
/ \
40 50
나는 Complete Binary Tree의 정의에 혼동이 없다고 생각하지만, 여전히 게시물의 완전성을 위해 Complete Binary Tree가 무엇인지 말하고 싶습니다.
3) 완전한 이진 트리 : 마지막 수준을 제외한 모든 수준이 완전히 채워지고 마지막 수준에 가능한 한 모든 키가 남아 있으면 이진 트리는 완전한 이진 트리입니다.
예 : 다음은 완전한 이진 트리입니다.
18
/ \
15 30
/ \ / \
40 50 100 40
/ \ /
8 7 9
참고 : 다음은 완전한 이진 트리이기도합니다.
18
/ \
15 30
/ \ / \
40 50 100 40
답변
부인 성명- -일부 정의의 주요 소스는 위키피디아이며 내 답변을 개선하기위한 제안을 환영합니다.
이 게시물에는 허용되는 답변이 있고 좋은 답변이지만 여전히 혼란 스러웠으며 이러한 용어의 차이점에 대해 좀 더 설명을 추가하고 싶습니다.
(1) FULL BINARY TREE- 풀 바이너리 트리는 잎을 제외한 모든 노드에 두 개의 자식이있는 바이너리 트리로, 엄격하게 바이너리 트리 라고도 합니다 .
위의 두 가지는 전체 또는 엄격 이진 트리의 예입니다.
(2) 완전한 이진 트리- 이제 완전한 이진 트리의 정의는 매우 모호합니다 .- 완전한 이진 트리는 마지막을 제외한 모든 레벨 이 완전히 채워지고 모든 노드가 다음과 같은 이진 트리입니다. 최대한 왼쪽으로. 마지막 레벨 h에서 가능한 한 가장 왼쪽에있는 1 ~ 2h 노드를 가질 수 있습니다.
기울임 꼴로 표시된 선을 확인하십시오.
모호성은 이탤릭체로 된 줄에 있습니다. “마지막 레벨을 제외하고”는 마지막 레벨도 완전히 채워질 수 있음을 의미합니다. 즉,이 예외가 항상 충족 될 필요는 없습니다. 예외가 유지되지 않으면 내가 게시 한 두 번째 이미지와 똑같으며 완벽한 이진 트리 라고도합니다 . 따라서 완벽한 이진 트리도 완전하고 완전하지만 그 반대는 아닙니다.
ALMOST COMPLETE BINARY TREE- 완전한 이진 트리 정의의 예외가 유지되면 거의 완전한 이진 트리 또는 거의 완전한 이진 트리라고합니다. 그것은 완전한 이진 트리의 한 유형일 뿐이지 만 더 명확하게 만들기 위해서는 별도의 정의가 필요합니다.
따라서 거의 완전한 이진 트리는 다음과 같이 보일 것입니다. 이미지에서 노드가 가능한 한 멀리 남아 있으므로 완전한 이진 트리의 하위 집합에 가깝습니다. 더 엄격하게 말하면 거의 완전한 이진 트리가 완전한 이진 트리입니다. 나무이지만 그 반대는 아닙니다. :
답변
위의 답변에서 결론을 내리면 완전 / 엄격, 완전 및 완벽한 바이너리 트리의 정확한 차이점은 다음과 같습니다.
-
Full / Strictly binary tree :-리프 노드를 제외한 모든 노드에는 두 개의 자식이 있습니다.
-
완전한 이진 트리 :-마지막 레벨을 제외한 모든 레벨이 완전히 채워지고 모든 노드가 정렬됩니다.
-
완벽한 이진 트리 :-리프 노드를 제외한 모든 노드에는 두 개의 자식이 있으며 모든 수준 (마지막 수준도)이 완전히 채워집니다.
답변
노드가 트리 방식으로 그려진 이진 트리를 고려하십시오. 이제 노드 번호를 위에서 아래로, 왼쪽에서 오른쪽으로 시작합니다. 완전한 트리에는 다음과 같은 속성이 있습니다.
n에 자식이 있으면 n보다 작은 번호의 모든 노드에는 자식이 두 개 있습니다.
n에 하나의 자식이있는 경우 왼쪽 자식이어야하며 n 미만의 모든 노드에는 두 개의 자식이 있어야합니다. 또한 n보다 큰 번호의 노드에는 자식이 없습니다.
n에 자식이 없으면 n보다 큰 번호의 노드에는 자식이 없습니다.
완전한 이진 트리를 사용하여 힙을 나타낼 수 있습니다. 간격없이 연속 메모리에서 쉽게 표현할 수 있습니다 (즉, 끝에 존재할 수있는 공간을 절약하기 위해 모든 배열 요소가 사용됨).
답변
완전한 이진 트리는 완전한 이진 트리이지만 그 반대는 불가능하며 이진의 깊이가 n이면 아니오입니다. 전체 이진 트리의 노드 수는 (2 ^ n-1)입니다. 이진 트리에서 두 개의 자식을 가질 필요는 없지만 전체 바이너리에서는 모든 노드에 자식이 없거나 두 개 있습니다.
