C++로 구현하는 이진 트리 전위(Preorder) 순회 재귀 프로그램

트리 순회(Tree Traversal)는 그래프 순회의 한 형태로, 트리에 속한 모든 노드를 정확히 한 번씩 방문하며 값을 확인하거나 출력하는 과정을 말합니다. 이진 탐색 트리(Binary Search Tree)의 전위 순회(Preorder Traversal)는 루트(Root) → 왼쪽(Left) → 오른쪽(Right) 순서로 각 노드를 방문하는 방식입니다.

전위 순회 예시

다음과 같은 이진 트리가 주어졌다고 가정해 보겠습니다.

이 트리에 대한 전위 순회 결과는 다음과 같습니다.

Preorder Traversal: 6 4 1 5 8

C++ 전위 순회 재귀 구현 코드

아래는 이진 탐색 트리를 전위 순회하는 재귀 함수를 포함한 완전한 C++ 프로그램입니다.

#include<iostream>
using namespace std;
struct node {
    int data;
    struct node *left;
    struct node *right;
};
struct node *createNode(int val) {
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = val;
    temp->left = temp->right = NULL;
    return temp;
}
void preorder(struct node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preorder(root->left);
        preorder(root->right);
    }
}
struct node* insertNode(struct node* node, int val) {
    if (node == NULL) return createNode(val);
    if (val < node->data)
        node->left = insertNode(node->left, val);
    else if (val > node->data)
        node->right = insertNode(node->right, val);
    return node;
}
int main() {
    struct node *root = NULL;
    root = insertNode(root, 4);
    insertNode(root, 5);
    insertNode(root, 2);
    insertNode(root, 9);
    insertNode(root, 1);
    insertNode(root, 3);
    cout<<"Pre-Order traversal of the Binary Search Tree is: ";
    preorder(root);
    return 0;
}

실행 결과

Pre-Order traversal of the Binary Search Tree is: 4 2 1 3 5 9

코드 상세 설명

1. 노드 구조체 정의

구조체 node는 트리의 개별 노드를 표현합니다. 자기 자신과 동일한 타입인 struct node 포인터를 멤버로 가지므로 자기 참조 구조체(self-referential structure)라고 부릅니다.

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

2. createNode() 함수 — 노드 생성

createNode() 함수는 새로운 노드 temp를 생성하고 malloc으로 메모리를 할당합니다. 전달받은 값 val을 data에 저장하며, 왼쪽과 오른쪽 자식 포인터는 NULL로 초기화합니다.

struct node *createNode(int val) {
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = val;
    temp->left = temp->right = NULL;
    return temp;
}

3. preorder() 함수 — 재귀적 전위 순회

preorder() 함수는 이진 트리의 루트 노드를 인자로 받아 전위 순회 순서대로 트리의 모든 요소를 출력하는 재귀 함수입니다. 먼저 현재 노드의 데이터를 출력한 뒤, 왼쪽 서브트리와 오른쪽 서브트리를 차례로 재귀 호출하여 순회합니다.

void preorder(struct node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preorder(root->left);
        preorder(root->right);
    }
}

4. insertNode() 함수 — 노드 삽입

insertNode() 함수는 주어진 값을 이진 탐색 트리에서 올바른 위치에 삽입합니다. 노드가 NULL이면 createNode()를 호출하여 새 노드를 만들고, 그렇지 않으면 값의 크기를 비교해가며 트리 내 적절한 위치를 찾아 재귀적으로 삽입을 진행합니다.

struct node* insertNode(struct node* node, int val) {
    if (node == NULL) return createNode(val);
    if (val < node->data)
        node->left = insertNode(node->left, val);
    else if (val > node->data)
        node->right = insertNode(node->right, val);
    return node;
}

5. main() 함수 — 트리 구성 및 순회 실행

main() 함수에서는 먼저 루트 노드를 NULL로 초기화한 후, 여러 값을 이진 탐색 트리에 순서대로 삽입합니다.

struct node *root = NULL;
root = insertNode(root, 4);
insertNode(root, 5);
insertNode(root, 2);
insertNode(root, 9);
insertNode(root, 1);
insertNode(root, 3);

마지막으로 트리의 루트 노드를 인자로 preorder() 함수를 호출하면, 트리의 모든 값이 전위 순회 순서대로 화면에 출력됩니다.

cout<<"Pre-Order traversal of the Binary Search Tree is: ";
preorder(root);