Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 이진 트리 레벨 순서 순회(Level Order Traversal)

이진 트리 레벨 순서 순회란?

이진 트리가 하나 있다고 가정해 보겠습니다. 이 트리를 레벨 순서 순회(Level Order Traversal), 즉 너비 우선 탐색(BFS) 방식으로 탐색해야 합니다. 레벨 순서 순회는 루트 노드부터 시작하여 같은 깊이(레벨)에 있는 노드들을 왼쪽에서 오른쪽 순서로 차례대로 방문하는 기법입니다.

예를 들어 다음과 같은 이진 트리가 있다고 합시다.

C++로 구현하는 이진 트리 레벨 순서 순회(Level Order Traversal)

이 트리를 레벨 순서로 순회하면 결과는 다음과 같습니다.

[10, 5, 16, 8, 15, 20, 23]

알고리즘 접근 방법

레벨 순서 순회는 큐(Queue) 자료구조를 활용하면 매우 간단하게 구현할 수 있습니다. 큐의 선입선출(FIFO) 특성 덕분에 위쪽 레벨의 노드를 먼저 처리하고, 그 자식들을 순서대로 다음에 처리할 수 있습니다. 단계별 절차는 다음과 같습니다.

  1. 노드를 저장할 큐(que)를 정의합니다.
  2. 루트 노드를 큐에 삽입합니다.
  3. 큐가 비어 있지 않은 동안 아래 작업을 반복합니다.
    • 큐의 맨 앞(front)에 있는 요소를 가져와 item에 저장합니다.
    • item의 값을 출력합니다.
    • item의 왼쪽 자식이 NULL이 아니라면 왼쪽 자식을 큐에 삽입합니다.
    • item의 오른쪽 자식이 NULL이 아니라면 오른쪽 자식을 큐에 삽입합니다.
    • 큐의 맨 앞 요소를 제거합니다.

C++ 구현 예제

아래의 전체 소스 코드를 통해 실제 구현 과정을 더 자세히 이해해 보겠습니다.

#include<iostream>
#include<queue>
using namespace std;
class node{
    public:
        int h_left, h_right, bf, value;
        node *left, *right;
};
class tree{
    private:
        node *get_node(int key);
    public:
        node *root;
        tree(){
            root = NULL; // 처음에 루트를 NULL로 설정
        }
        void levelorder_traversal(node *r);
        node *insert_node(node *root, int key);
};
node *tree::get_node(int key){
    node *new_node;
    new_node = new node; // 동적으로 새 노드 생성
    new_node->h_left = 0; new_node->h_right = 0;
    new_node->bf = 0;
    new_node->value = key; // 주어진 키 값을 저장
    new_node->left = NULL; new_node->right = NULL;
    return new_node;
}
void tree::levelorder_traversal(node *root){
    queue <node*> que;
    node *item;
    que.push(root); // 먼저 루트를 큐에 삽입
    while(!que.empty()){
        item = que.front(); // 큐의 맨 앞에서 요소를 가져옴
        cout << item->value << " ";
        if(item->left != NULL) // 왼쪽 자식이 있으면 큐에 삽입
            que.push(item->left);
        if(item->right != NULL) // 오른쪽 자식이 있으면 큐에 삽입
            que.push(item->right);
        que.pop(); // 큐에서 해당 항목을 제거
    }
}
node *tree::insert_node(node *root, int key){
    if(root == NULL){
        return (get_node(key)); // 트리가 비어 있으면 새 노드를 루트로 생성
    }
    if(key < root->value){ // 키가 루트 값보다 작으면 왼쪽으로 이동
        root->left = insert_node(root->left, key);
    }
    else if(key > root->value){ // 키가 루트 값보다 크면 오른쪽으로 이동
        root->right = insert_node(root->right, key);
    }
    return root; // 키가 이미 존재하면 다시 삽입하지 않음
}
main(){
    node *root;
    tree my_tree;
    // 트리에 여러 키를 삽입합니다.
    my_tree.root = my_tree.insert_node(my_tree.root, 10);
    my_tree.root = my_tree.insert_node(my_tree.root, 5);
    my_tree.root = my_tree.insert_node(my_tree.root, 16);
    my_tree.root = my_tree.insert_node(my_tree.root, 20);
    my_tree.root = my_tree.insert_node(my_tree.root, 15);
    my_tree.root = my_tree.insert_node(my_tree.root, 8);
    my_tree.root = my_tree.insert_node(my_tree.root, 23);
    cout << "Level-Order Traversal: ";
    my_tree.levelorder_traversal(my_tree.root);
}

실행 결과

입력

[10,5,16,null,8,15,20,null,null,null,null,null,null,null,23]

출력

Level-Order Traversal: 10 5 16 8 15 20 23

시간 및 공간 복잡도

이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 또한 최악의 경우(완전 이진 트리) 마지막 레벨의 노드 수만큼 큐에 노드를 저장해야 하므로 공간 복잡도 역시 O(n)입니다.