TechCodeview

이진 트리는 노드가 최대 2개의 자식을 가질 수 있음을 의미합니다. 여기서 바이너리 이름 자체는 '2'를 의미합니다. 따라서 각 노드는 0, 1 또는 2개의 하위 항목을 가질 수 있습니다.

예를 통해 이진 트리를 이해해 봅시다.

위의 트리는 각 노드가 최대 2개의 자식을 포함하므로 이진 트리입니다. 위 트리의 논리적 표현은 다음과 같습니다.

위의 트리에서 노드 1에는 두 개의 포인터, 즉 왼쪽 및 오른쪽 노드를 각각 가리키는 왼쪽 및 오른쪽 포인터가 포함되어 있습니다. 노드 2에는 두 노드(왼쪽 및 오른쪽 노드)가 모두 포함되어 있습니다. 따라서 두 개의 포인터(왼쪽 및 오른쪽)가 있습니다. 노드 3, 5, 6은 리프 노드이므로 이 모든 노드에는 다음이 포함됩니다. 없는 왼쪽과 오른쪽 부분 모두에 포인터가 있습니다.

이진 트리의 속성

• i의 각 레벨에서 최대 노드 수는 2입니다.^나.
• 트리의 높이는 루트 노드에서 리프 노드까지의 가장 긴 경로로 정의됩니다. 위에 표시된 트리의 높이는 3입니다. 따라서 높이 3의 최대 노드 수는 (1+2+4+8) = 15와 같습니다. 일반적으로 높이 h에서 가능한 최대 노드 수는 (2⁰+ 2¹+ 2²+….2^시간) = 2^h+1-1.
• 높이 h에서 가능한 최소 노드 수는 다음과 같습니다. h+1 .
• 노드 수가 최소이면 트리의 높이도 최대가 됩니다. 반대로, 노드 수가 최대이면 트리의 높이는 최소가 됩니다.

이진 트리에 'n'개의 노드가 있는 경우.

최소 높이는 다음과 같이 계산할 수 있습니다.

우리가 알고 있듯이,

n = 2^h+1-1

n+1 = 2^h+1

양변에 로그를 취하고,

통나무₂(n+1) = log2(2^h+1)

통나무₂(n+1) = h+1

h = 로그₂(n+1) - 1

최대 높이는 다음과 같이 계산할 수 있습니다.

우리가 알고 있듯이,

모의 추상 클래스를 주입하는 방법

n = h+1

h= n-1

이진 트리의 유형

이진 트리에는 네 가지 유형이 있습니다.

전체/적절/엄격한 이진 트리 완전한 이진 트리 완벽한 이진 트리 퇴화된 이진 트리 균형 잡힌 이진 트리

1. 완전/적절/엄격한 이진 트리

완전 이진 트리는 엄격한 이진 트리라고도 합니다. 각 노드가 0 또는 2개의 자식을 포함해야 하는 경우에만 트리는 전체 이진 트리로 간주될 수 있습니다. 전체 이진 트리는 각 노드가 리프 노드를 제외하고 2개의 자식을 포함해야 하는 트리로 정의될 수도 있습니다.

전체 이진 트리의 간단한 예를 살펴보겠습니다.

위 트리에서 우리는 각 노드가 0개 또는 2개의 자식을 포함하고 있음을 관찰할 수 있습니다. 그러므로 이는 완전 이진 트리입니다.

완전 이진 트리의 속성

• 리프 노드의 수는 내부 노드의 수에 1을 더한 것과 같습니다. 위의 예에서 내부 노드의 수는 5입니다. 따라서 리프 노드의 수는 6과 같습니다.
• 최대 노드 수는 이진 트리의 노드 수와 동일합니다. 즉, 2개입니다.^h+1-1.
• 전체 이진 트리의 최소 노드 수는 2*h-1입니다.
• 전체 이진 트리의 최소 높이는 다음과 같습니다. 통나무₂(n+1) - 1.
• 전체 이진 트리의 최대 높이는 다음과 같이 계산할 수 있습니다.

n= 2*h - 1

n+1 = 2*h

h = n+1/2

완전한 이진 트리

완전 이진 트리는 마지막 레벨을 제외한 모든 노드가 완전히 채워지는 트리입니다. 마지막 레벨에서는 모든 노드가 가능한 한 왼쪽에 있어야 합니다. 완전한 이진 트리에서는 왼쪽부터 노드를 추가해야 합니다.

완전한 이진 트리를 만들어 보겠습니다.

위 트리는 모든 노드가 완전히 채워지고 마지막 레벨의 노드가 모두 왼쪽에 먼저 추가되므로 완전 이진 트리입니다.

완전 이진 트리의 속성

100개 중 10개는 무엇인가요?

• 완전 이진 트리의 최대 노드 수는 2입니다.^h+1- 1.
• 완전한 이진 트리의 최소 노드 수는 2입니다.^시간.
• 완전한 이진 트리의 최소 높이는 다음과 같습니다. 통나무₂(n+1) - 1.
• 완전한 이진 트리의 최대 높이는 다음과 같습니다.

완벽한 이진 트리

모든 내부 노드에 2개의 자식 노드가 있고 모든 리프 노드가 동일한 수준에 있으면 트리는 완벽한 이진 트리입니다.

완벽한 이진 트리의 간단한 예를 살펴보겠습니다.

아래 트리는 모든 리프 노드가 동일한 수준에 있지 않기 때문에 완벽한 이진 트리가 아닙니다.

참고: 모든 완벽한 이진 트리는 완전한 이진 트리이자 전체 이진 트리이지만 그 반대는 사실이 아닙니다. 즉, 모든 완전한 이진 트리와 전체 이진 트리는 완벽한 이진 트리입니다.

퇴화된 이진 트리

퇴화 이진 트리는 모든 내부 노드에 자식이 하나만 있는 트리입니다.

예제를 통해 Degenerate 이진 트리를 이해해 봅시다.

위의 트리는 모든 노드에 자식이 하나만 있기 때문에 퇴화된 이진 트리입니다. 모든 노드에는 오른쪽 자식만 있으므로 오른쪽으로 치우친 트리라고도 합니다.

위의 트리는 모든 노드에 자식이 하나만 있기 때문에 퇴화 이진 트리이기도 합니다. 모든 노드에 왼쪽 자식만 있으므로 왼쪽으로 치우친 트리라고도 합니다.

균형 잡힌 이진 트리

균형 이진 트리는 왼쪽 트리와 오른쪽 트리 모두 최대 1만큼 차이가 나는 트리입니다. 예를 들어, AVL 그리고 레드-블랙 트리 균형 잡힌 이진 트리입니다.

예제를 통해 균형 이진 트리를 이해해 봅시다.

위 트리는 왼쪽 하위 트리와 오른쪽 하위 트리의 차이가 0이므로 균형 이진 트리입니다.

위 트리는 왼쪽 하위 트리와 오른쪽 하위 트리의 차이가 1보다 크기 때문에 균형 이진 트리가 아닙니다.

이진 트리 구현

이진 트리는 포인터의 도움으로 구현됩니다. 트리의 첫 번째 노드는 루트 포인터로 표시됩니다. 트리의 각 노드는 데이터, 왼쪽 포인터, 오른쪽 포인터의 세 부분으로 구성됩니다. 이진 트리를 생성하려면 먼저 노드를 생성해야 합니다. 아래와 같이 사용자 정의 노드를 생성합니다.

 struct node { int data, struct node *left, *right; } 

위의 구조에서, 데이터 값은, 왼쪽 포인터 왼쪽 노드의 주소를 포함하고, 오른쪽 포인터 오른쪽 노드의 주소를 포함합니다.

C의 이진 트리 프로그램

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

위 코드는 create() 함수를 재귀적으로 호출하고 각 재귀 호출마다 새 노드를 생성합니다. 모든 노드가 생성되면 이진 트리 구조를 형성합니다. 노드를 방문하는 프로세스를 트리 순회라고 합니다. 노드를 방문하는 데 사용되는 순회에는 세 가지 유형이 있습니다.

• 중위순회
• 선주문 순회
• 우편 주문 순회