[c++] 레벨 순회(Level Order Traversal)

12 Dec 2023

이번에는 이진 트리의 각 레벨을 순회하는 방법에 대해 알아보겠습니다. 레벨 순회(Level Order Traversal)는 트리 구조를 각 레벨별로 순차적으로 방문하는 방법입니다.

#include <iostream>
#include <queue>

struct Node {
    int value;
    Node* left;
    Node* right;
    Node(int v) : value(v), left(nullptr), right(nullptr) {}
};

void levelOrderTraversal(Node* root) {
    if (root == nullptr)
        return;

    std::queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* current = q.front();
        q.pop();

        std::cout << current->value << " ";

        if (current->left != nullptr)
            q.push(current->left);

        if (current->right != nullptr)
            q.push(current->right);
    }
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    std::cout << "레벨 순회(Level Order Traversal): ";
    levelOrderTraversal(root);

    return 0;
}

위의 코드는 이진 트리를 생성하고, 레벨 순회를 수행하는 간단한 C++ 예제입니다. Node 구조체를 통해 이진 트리를 정의하고, levelOrderTraversal 함수를 사용하여 레벨 순회를 구현하였습니다. 실제로 실행하면 다음과 같은 결과를 얻을 수 있습니다.

레벨 순회(Level Order Traversal): 1 2 3 4 5

위의 예제를 참고하여 이진 트리의 레벨 순회를 구현할 수 있습니다.

이상으로 C++의 이진 트리 레벨 순회에 대해 알아보았습니다.

참고문헌:

GeeksforGeeks: Level Order Traversal