[C언어] 이진 트리(Binary Tree) 구현 실습하기

이진 트리(Binary Tree) 구현 실습하기

이번 포스트에서는 이진 트리(Binary Tree)라는 자료구조를 직접 구현해보는 시간을 가져보려고 합니다. 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조인데요, 그렇다면 이러한 이진 트리를 어떻게 생성하고, 어떻게 출력하며, 어떻게 삭제할 수 있을까요?

 

처음에는 구조도 복잡하고 막막하게 느껴질 수 있지만, 이번 실습을 통해 이진 트리의 기본 원리를 직접 구현해보며 자연스럽게 개념을 익혀보면 좋겠습니다.

 

 

필요한 구조체, 함수 정의하기

구조체

• BTNode: (struct) 이진 트리 노드 구조체
  • item: (int field) 노드의 값
  • *left: (pointer field) 왼쪽 자식 노드 주소
  • *right: (pointer field) 오른쪽 자식 노드 주소

트리 생성 시, 노드를 순차적으로 생성하기 위해 스택을 이용합니다.

• StackNode: (struct) 트리 생성을 위한 스택 노드 구조체
  • *btnode: (pointer field) 이진 트리 노드 주소
  • *next: (pointer field) 다음(스택 아래쪽) 노드 주소

• Stack: (struct) 트리 생성을 위한 스택 구조체
  • *top: (pointer field) 스택 최상단 노드의 주소

함수 (추천 구현 순서)

• BTNode *createBTNode(int item): 새로운 트리 노드를 생성하여 반환
• void push(Stack *stk, BTNode *node): 스택에 노드를 삽입
• BTNode *pop(Stack *stk): 스택에서 노드를 꺼내고 제거한 뒤 값을 반환
• BTNode *createTree(): 사용자 입력을 통해 이진 트리를 생성
• void printTree(BTNode *node): 중위 순회로 트리를 출력
• void removeAll(BTNode *node): 트리 전체를 삭제

 

전체 실습 코드

이진 트리 구현 실습용 뼈대 코드입니다. 각 함수에는 간단한 힌트가 주석으로 포함되어 있어, 스스로 고민하고 구현해볼 수 있게끔 되어 있습니다. 칠판이나 노트에 그림을 그려 보면서 기본 함수들을 하나씩 구현해 보세요.

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

// ===== 이진 트리 노드 구조체 ===== //
typedef struct _btnode {
    int item;
    struct _btnode *left;
    struct _btnode *right;
} BTNode;

// ===== 스택 구조체 (트리 생성을 위한 보조 도구) ===== //
typedef struct _stackNode {
    BTNode *btnode;
    struct _stackNode *next;
} StackNode;

typedef struct _stack {
    StackNode *top;
} Stack;

// ===== 함수 선언 ===== //
BTNode *createBTNode(int item);
void push(Stack *stk, BTNode *node);
BTNode *pop(Stack *stk);
BTNode *createTree();
void printTree(BTNode *node);
void removeAll(BTNode **node);

// ===== 메인 함수: 메뉴 기반 이진 트리 테스트 ===== //
int main() {
    BTNode *root = NULL;
    int choice = 1;

    printf("===== 이진 트리 실습 프로그램 =====\n");

    while (choice != 0) {
        printf("\n1: 트리 생성\n");
        printf("2: 중위 순회 출력\n");
        printf("3: 트리 메모리 해제\n");
        printf("0: 종료\n");

        printf("메뉴 선택 (0~3): ");
        scanf("%d", &choice);

        switch (choice) {
        case 1:
            removeAll(&root);
            printf("[트리 생성]\n");
            root = createTree();
            break;

        case 2:
            printf("[중위 순회 출력]\n");
            printTree(root);
            printf("\n");
            break;

        case 3:
            printf("[트리 전체 삭제]\n");
            removeAll(&root);
            break;

        case 0:
            removeAll(&root);
            printf("프로그램 종료.\n");
            break;

        default:
            printf("잘못된 선택입니다.\n");
        }
    }

    return 0;
}

// ===== 기본 함수 구현 (힌트 주석 포함) ===== //

// 새로운 트리 노드를 생성하여 반환하는 함수
BTNode *createBTNode(int item) {
    /*  힌트: 메모리 동적 할당 + 값 설정 + 왼쪽/오른쪽 NULL
        add your code here  */
}

// 스택에 노드를 삽입하는 함수
void push(Stack *stk, BTNode *node) {
    /*  힌트: 새로운 StackNode를 만들고 top 앞에 연결
        add your code here  */
}

// 스택에서 노드를 꺼내고 제거한 뒤 값을 반환하는 함수
BTNode *pop(Stack *stk) {
    /*  힌트: top이 가리키는 StackNode를 제거하고 해당 노드 반환
        add your code here  */
}

// 사용자 입력을 통해 이진 트리를 생성하는 함수
// 사용자가 자식 노드 생성을 원하지 않는 경우 문자를 입력
BTNode *createTree() {
    /*  힌트:
        1. 루트 노드 입력 → 스택에 push
        2. 스택에서 pop하면서 왼쪽/오른쪽 자식 입력
        3. 값 입력 실패 시(NULL 처리) → scanf로 문자 소비
        add your code here  */
}

// 중위 순회로 트리를 출력하는 함수
// 출력 순서: 왼쪽 자식 → 현재 노드 → 오른쪽 자식
void printTree(BTNode *node) {
    /*  힌트: 재귀 - 왼쪽 → 루트 → 오른쪽
        add your code here  */
}

// 트리 전체를 삭제하는 함수
void removeAll(BTNode **node) {
    /*  힌트: 후위 순회 방식 - 왼쪽, 오른쪽 먼저 삭제 후 현재 노드 free
        add your code here  */
}

 

 

이진 트리 구현하기

함수마다 주어진 매개변수(parameter)를 바탕으로, 해당 함수가 어떤 기능을 수행해야 하는지 먼저 논리적으로 생각해보고, 그 후에 실제로 직접 구현해봅니다.

 

각 함수는 어떤 기본 동작 흐름을 따르는지, 어떤 포인터 변수를 새로 만들어야 할지, 그리고 예외 상황(스택이 비어있는 경우 등)에는 어떻게 대응해야 할지도 함께 고민해보면 더 좋습니다.

 

createBTNode 함수

새로운 트리 노드를 생성하여 반환하는 함수

• item: (int) 새 트리 노드의 값

createBTNode 구현하기

// 새로운 트리 노드를 생성하여 반환하는 함수
BTNode *createBTNode(int item) {
    // 노드 하나에 대한 메모리를 동적 할당
    // ※ 실제 환경에서는 malloc 실패(NULL 반환)도 고려해야 함
    BTNode *new_node = malloc(sizeof(BTNode));

    // 노드에 값 저장, 자식 노드들은 NULL로 초기화
    new_node->item = item;
    new_node->left = NULL;
    new_node->right = NULL;

    // 생성한 노드의 주소를 반환
    return new_node;
}

 

 

push 함수

스택에 노드를 삽입하는 함수

• *stk: (pointer) 스택 주소
• *node: (pointer) 노드 주소

push 구현하기

// 스택에 노드를 삽입하는 함수
void push(Stack *stk, BTNode *node) {
    // 새로운 StackNode를 동적 할당
    StackNode *new_stack_node = malloc(sizeof(StackNode));

    // 전달받은 트리 노드를 스택 노드에 저장
    new_stack_node->btnode = node;

    // 새 노드의 next는 현재 스택의 top을 가리키게 변경
    // (새 노드가 기존 top 위에 쌓이는 형태)
    new_stack_node->next = stk->top;

    // 스택의 top을 새 노드로 변경
    stk->top = new_stack_node;
}

 

 

pop 함수

스택에서 노드를 꺼내고 제거한 뒤 값을 반환하는 함수

• *stk: (pointer) 스택 주소

pop 구현하기

// 스택에서 노드를 꺼내고 제거한 뒤 해당 트리 노드 반환
BTNode *pop(Stack *stk) {
    // 스택이 비어 있으면 NULL 반환
    if (stk->top == NULL) return NULL;

    // 현재 스택의 top을 임시 포인터에 저장
    StackNode *top = stk->top;
    // 스택의 top이 담고 있는 트리 노드 주소를 추출
    BTNode *node = top->btnode;
    
    // 스택의 top을 top의 다음 노드로 변경
    stk->top = stk->top->next;
    // 기존 top 제거(메모리 해제)
    free(top);
    
    // 꺼낸 트리 노드 주소 반환
    return node;
}

 

createTree 함수

사용자 입력을 통해 이진 트리를 생성하는 함수.

 

먼저 사용자로부터 루트 노드의 값을 입력받아 노드를 생성하고, 이를 스택에 push합니다. 이후 스택에서 노드를 하나씩 꺼내면서 해당 노드의 왼쪽 자식과 오른쪽 자식 값을 순서대로 입력받아 트리에 연결하고, 생성된 자식 노드들을 다시 스택에 push하면 되는데요. 이 과정을 스택이 빌 때까지 반복하며 트리를 구성하고, 과정 종료 후에 출력이나 삭제 함수에서 사용할 수 있도록 처음 생성된 루트 노드를 반환합니다.

createTree 구현하기

// 사용자 입력을 통해 이진 트리를 생성하는 함수
// 사용자가 자식 노드 생성을 원하지 않는 경우 문자를 입력
BTNode *createTree() {
    Stack stk;                   // 트리 생성을 위한 스택
    BTNode *root, *temp;        // 루트 노드 및 현재 처리 중인 노드
    char dummy;                 // 잘못된 입력 처리용 문자 버퍼
    int item;                   // 사용자로부터 입력받을 노드 값

    stk.top = NULL;             // 스택 초기화
    root = NULL;                // 루트 초기화

    // 루트 노드 입력 받기
    printf("루트 노드 값: ");
    if (scanf("%d", &item)) {
        root = createBTNode(item);   // 루트 노드 생성
        push(&stk, root);            // 루트를 스택에 push
    } else {
        // 숫자 입력이 아닌 경우 → 입력 실패 처리
        scanf("%c", &dummy);
        return NULL;
    }

    // 스택이 빌 때까지 반복하며 트리 구성
    while ((temp = pop(&stk)) != NULL) {
        // 왼쪽 자식 노드 입력 받기
        printf("노드 %d의 왼쪽 자식 노드 값(자식을 만들지 않으려면 아무 문자나 입력): ", temp->item);
        if (scanf("%d", &item)) {
            temp->left = createBTNode(item);   // 왼쪽 자식 노드 생성
        } else {
            scanf("%c", &dummy);               // 입력 실패 시 '\n' 제거
        }

        // 오른쪽 자식 노드 입력 받기
        printf("노드 %d의 오른쪽 자식 노드 값(자식을 만들지 않으려면 아무 문자나 입력): ", temp->item);
        if (scanf("%d", &item)) {
            temp->right = createBTNode(item);  // 오른쪽 자식 노드 생성
        } else {
            scanf("%c", &dummy);               // 입력 실패 시 '\n' 제거
        }

        // 생성된 자식 노드를 스택에 push
        // 왼쪽이 먼저 pop되도록 오른쪽을 먼저 push
        if (temp->right) push(&stk, temp->right);
        if (temp->left)  push(&stk, temp->left);
    }

    // 트리의 루트 노드 반환
    return root;
}

 

printTree 함수

중위 순회로 트리를 출력하는 함수

• node: (pointer) 이진 트리 루트 노드 주소

printTree 구현하기

// 중위 순회(inorder traversal)로 트리를 출력하는 함수
// 출력 순서: 왼쪽 자식 → 현재 노드 → 오른쪽 자식
void printTree(BTNode *node) {
    // 현재 노드가 NULL이면 재귀 호출 종료
    if (node == NULL) return;

    // 왼쪽 서브트리 먼저 출력 (재귀 호출)
    printTree(node->left);
    // 현재 노드의 값 출력
    printf("%d ", node->item);
    // 오른쪽 서브트리 출력 (재귀 호출)
    printTree(node->right);
}

 

removeAll 함수

트리 전체를 삭제하는 함수.

 

이진 트리의 루트는 노드를 가리키는 포인터이므로, 루트 자체를 NULL로 바꾸려면 그 포인터의 주소, 즉 이중 포인터를 전달해야 합니다.

• **node: (double pointer) 이진 트리 루트 노드 주소의 주소

removeAll 구현하기

// 트리 전체를 삭제하는 함수
void removeAll(BTNode **node) {
    // 현재 노드가 NULL이면 재귀 호출 종료
    if (*node == NULL) return;

    // 왼쪽 서브트리 삭제 (재귀 호출)
    removeAll(&((*node)->left));
    // 오른쪽 서브트리 삭제 (재귀 호출)
    removeAll(&((*node)->right));
    // 현재 노드의 메모리 해제
    free(*node);
    // 해제된 포인터를 NULL로 초기화 (안전한 종료 처리)
    *node = NULL;
}