높이 계산 없이 C 언어로 포화 이진 트리의 중간 레벨 출력하기

문제 개요

이 프로그램은 이진 트리의 중간 레벨에 있는 노드들을 출력해야 합니다. 예를 들어 트리의 레벨이 총 4개라면 레벨 2에 해당하는 노드들이 출력 대상이 됩니다. 여기서 핵심 요구 사항은 트리의 높이를 먼저 구하지 않고 중간 레벨을 찾아내는 것입니다.

포화 이진 트리(Perfect Binary Tree)란?

포화 이진 트리는 모든 내부 노드가 반드시 두 개의 자식을 가지며, 모든 리프 노드가 동일한 레벨(깊이)에 위치하는 트리를 말합니다.

위 그림에서 확인할 수 있는 특징은 다음과 같습니다.

내부 노드 21과 32는 모두 자식 노드를 두 개씩 가지고 있습니다.
리프 노드 41, 59, 33, 70은 모두 같은 레벨에 놓여 있습니다.

이 두 가지 성질을 모두 만족하므로 위 트리는 포화 이진 트리입니다.

예제

Input : 12 21 32 41 59 33 70
Output : 21 32

접근 방식

여기서 사용하는 방법은 연결 리스트에서 중간 원소를 찾을 때 쓰이는 두 포인터(two pointer) 기법과 매우 유사합니다. 한 포인터는 한 칸씩, 다른 포인터는 두 칸씩 이동하도록 하여 함수를 재귀적으로 호출하고, 빠른 포인터가 리프 노드에 도달한 시점에 느린 포인터가 가리키는 노드가 바로 중간 레벨의 노드가 됩니다.

즉, 노드의 왼쪽·오른쪽 포인터가 NULL인지 아닌지를 검사하는 과정을 재귀 호출과 함께 반복하면서 높이를 따로 계산하지 않고도 중간 레벨을 찾아낼 수 있습니다.

알고리즘

START
    Step 1 -> 구조체 타입의 노드 변수 생성
        int형 key 선언
        node 타입의 포인터 *left, *right 선언
    Step 2 -> 값을 매개변수로 받는 노드 삽입용 함수 생성
        malloc을 사용해 node 타입의 temp 변수 선언
        temp->data = value 대입
        temp->left = temp->right = NULL 대입
        temp 반환
    Step 3 -> void middle(struct Node* a, struct Node* b) 함수 선언
        IF a == NULL || b == NULL
            Return
        IF ((b->left == NULL) && (b->right == NULL))
            a->key 출력
            Return
        End
        middle(a->left, b->left->left) 호출
        middle(a->right, b->left->left) 호출
    Step 4 -> void mid_level(struct Node* node) 함수 선언
        middle(node, node) 호출
    Step 5 -> main() 함수 안에서
        삽입하려는 값을 인자로 New 호출: struct Node* n1 = New(13);
        mid_level(n1) 호출
STOP

C 언어 구현 예제

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int key;
    struct Node* left, *right;
};
struct Node* New(int value) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->key = value;
    temp->left = temp->right = NULL;
    return (temp);
}
void middle(struct Node* a, struct Node* b) {
    if (a == NULL || b == NULL)
        return;
    if ((b->left == NULL) && (b->right == NULL)) {
        printf("%d ",a->key);
        return;
    }
    middle(a->left, b->left->left);
    middle(a->right, b->left->left);
}
void mid_level(struct Node* node) {
    middle(node, node);
}
int main() {
    printf("middle level nodes are : ");
    struct Node* n1 = New(13);
    struct Node* n2 = New(21);
    struct Node* n3 = New(44);
    struct Node* n4 = New(98);
    struct Node* n5 = New(57);
    struct Node* n6 = New(61);
    struct Node* n7 = New(70);
    n2->left = n4;
    n2->right = n5;
    n3->left = n6;
    n3->right = n7;
    n1->left = n2;
    n1->right = n3;
    mid_level(n1);
}

출력 결과

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

middle level nodes are : 21 44

이 예제의 트리는 총 3개의 레벨로 구성되어 있으므로, 중간에 해당하는 두 번째 레벨의 노드인 21과 44가 출력됩니다. 높이를 별도로 계산하지 않고도 두 포인터의 이동 속도 차이를 활용해 중간 레벨을 효율적으로 찾아낼 수 있다는 점이 이 알고리즘의 핵심입니다.