4-1. 이진 트리 (Binary Tree)

이진 트리란?

 트리의 차수가 2인 트리. 트리를 구성하는 노드들의 자식은 최대 2개이다. 하나의 부모 노드에는 왼쪽, 오른쪽 자식이 존재하는 형태이다.

 

이진 트리의 형태

 1. 정 이진 트리 (Full Binary Tree)

정 이진 트리 예시

 모든 노드의 차수가 2 혹은 0인 경우이다. 만약 자식이 하나만 존재하는 노드가 있다면, 정 이진 트리라고 할 수 없다. 위 같은 경우 차수가 1인 노드가 존재하지 않고, 리프 노드를 제외한 노드들의 자식은 모두 2개 이므로 정 이진 트리이다.

 

 2. 포화 이진 트리 (Perfect Binary Tree)

포화 이진 트리 예시

 

 정 이진 트리의 조건에 더하여 모든 리프 노드의 레벨이 같아야 한다. 우리가 생각하는 예쁘게 꽉 찬 트리의 모습이 포화 이진 트리이다.

 

 3. 완전 이진 트리 (Complete Binary Tree)

완전 이진 트리 예시

 가장 마지막 레벨을 제외한 레벨은 모든 노드가 채워져 있어야 하고, 노드들이 왼쪽 -> 오른쪽 방향으로 채워져 있으면, 완전 이진 트리라고 한다. 자식의 개수는 상관 없지만, 빈틈없이 순서대로 채워져야하는 형태이다.

 

이진 트리 순회

 트리의 탐색은 알고리즘에서 트리 구조의 활용을 위해 필수적으로 알아야 한다. 탐색하는 방법에는 대표적으로 3가지가 있다.

 

 

 1. 전위 순회 (Pre-Order)

 루트 -> 왼쪽 -> 오른쪽 의 순서로 탐색한다.

 위 트리를 기준으로 탐색을 할 때, 루트 노드 a부터 시작하여 왼쪽 자식인 b로 간다. 그 다음은 b의 왼쪽인 d, 오른쪽인 e순서로 탐색한다. 이렇게 되면 a의 왼쪽이 탐색이 완료 되었으므로 c로 넘어간다. 이런 식으로 반복하면 a b d e c f g 순서로 탐색한다.

 

 2. 중위 순회 (In-Order)

 왼쪽 -> 루트 -> 오른쪽 의 순서로 탐색한다.

 위 트리를 기준으로 탐색을 할 때, 가장 왼쪽인 d부터 시작, d의 부모인 b, 오른쪽 e를 탐색하고, 이제 b의 부모인 a, 그 다음은 크게 보았을 때 a의 오른쪽으로 가야 하고, 해당 서브 트리에서 가장 왼쪽인 f - c - g 순서로 탐색한다.

 이런 식으로 하면 d b e a f c g 순서로 탐색한다.

 

 3. 후위 순회 (Post-Order)

 왼쪽 -> 오른쪽 -> 루트 의 순서로 탐색한다.

 위 트리를 기준으로 탐색을 할 때, 가장 왼쪽인 d부터 시작, d의 형제인 e, 부모 b를 거치고, a를 기준으로 오른쪽 서브 트리로 넘어가 f - g - c 순서로 탐색한 뒤, 마지막으로 a를 탐색한다. 

 

예시 코드

#include <stdio.h>
#include <stdlib.h>

// 노드 구조체 정의
struct Node {
    char data;
    struct Node* left;
    struct Node* right;
};

// 새로운 노드를 생성하는 함수
struct Node* createNode(char data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 전위 순회 (Pre-order)
void preorder(struct Node* node) {
    if (node == NULL)
        return;
    printf("%c ", node->data); // 노드 데이터 출력
    preorder(node->left);      // 왼쪽 서브트리 순회
    preorder(node->right);     // 오른쪽 서브트리 순회
}

// 중위 순회 (In-order)
void inorder(struct Node* node) {
    if (node == NULL)
        return;
    inorder(node->left);       // 왼쪽 서브트리 순회
    printf("%c ", node->data); // 노드 데이터 출력
    inorder(node->right);      // 오른쪽 서브트리 순회
}

// 후위 순회 (Post-order)
void postorder(struct Node* node) {
    if (node == NULL)
        return;
    postorder(node->left);     // 왼쪽 서브트리 순회
    postorder(node->right);    // 오른쪽 서브트리 순회
    printf("%c ", node->data); // 노드 데이터 출력
}

 

 위 예시 코드는 C언어 구조체로 이진 트리 노드를 구현한 것과, 각 순회 방법을 함수로 나타낸 것이다.