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

C++ 큐(Queue)를 활용해 이진 트리를 스레드 이진 트리로 변환하는 방법

이번 튜토리얼에서는 큐(queue) 자료구조를 활용하여 일반적인 이진 트리(binary tree)를 스레드 이진 트리(threaded binary tree)로 변환하는 프로그램을 다룹니다.

스레드 이진 트리란, 각 노드의 NULL 오른쪽 포인터를 해당 노드의 중위 순회(inorder) 후속자(successor)를 가리키도록 변경한 트리입니다. 이렇게 하면 스택이나 재귀 호출 없이도 빠른 중위 순회가 가능해집니다.

주어진 과제는 다음과 같습니다. 하나의 이진 트리가 제공되며, 우리는 큐 자료구조의 도움을 받아 중위 순회 속도를 높이기 위한 추가 링크(스레드)를 연결함으로써 해당 이진 트리를 스레드 이진 트리로 변환해야 합니다.

변환 절차 개요

전체 알고리즘은 크게 두 단계로 진행됩니다.

  1. 중위 순회 결과를 큐에 저장: 트리를 중위 순회하면서 각 노드를 순서대로 큐에 삽입합니다.
  2. 트리를 다시 순회하며 스레드 생성: 오른쪽 자식이 NULL인 노드를 만나면, 큐의 front에 있는 노드(즉, 중위 후속자)를 오른쪽 포인터에 연결하고 isThreaded 플래그를 true로 설정합니다.

예제 코드

#include <iostream>
#include <queue>
using namespace std;

// 스레드 트리용 노드 구조체
struct Node {
    int key;
    Node *left, *right;
    bool isThreaded;
};

// 중위 순회 패턴을 큐에 저장
void convert_queue(Node* root, std::queue<Node*>* q){
    if (root == NULL)
        return;
    if (root->left)
        convert_queue(root->left, q);
    q->push(root);
    if (root->right)
        convert_queue(root->right, q);
}

// 큐를 순회하며 스레드 트리 생성
void create_threadedtree(Node* root, std::queue<Node*>* q){
    if (root == NULL)
        return;
    if (root->left)
        create_threadedtree(root->left, q);
    q->pop();
    if (root->right)
        create_threadedtree(root->right, q);
    // 오른쪽 포인터가 NULL이면
    // 중위 후속자를 가리키도록 설정
    else {
        root->right = q->front();
        root->isThreaded = true;
    }
}

// 트리를 받아 최종적으로 스레드 트리로 변환
void createThreaded(Node* root){
    std::queue<Node*> q;
    convert_queue(root, &q);
    create_threadedtree(root, &q);
}

Node* leftMost(Node* root){
    while (root != NULL && root->left != NULL)
        root = root->left;
    return root;
}

// 스레드 트리의 중위 순회 수행
void inOrder(Node* root){
    if (root == NULL)
        return;
    Node* cur = leftMost(root);
    while (cur != NULL) {
        cout << cur->key << " ";
        // 스레드 노드라면 중위 후속자로 이동
        if (cur->isThreaded)
            cur = cur->right;
        else
            cur = leftMost(cur->right);
    }
}

Node* newNode(int key){
    Node* temp = new Node;
    temp->left = temp->right = NULL;
    temp->key = key;
    return temp;
}

int main(){
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    createThreaded(root);
    cout << "Traversing threaded tree :\n";
    inOrder(root);
    return 0;
}

실행 결과

Traversing threaded tree :
4 2 5 1 6 3 7

코드 설명

  • convert_queue(): 재귀적으로 중위 순회를 수행하며 노드들을 큐에 순서대로 넣습니다. 덕분에 큐에는 트리의 값들이 정렬된 순서(왼쪽 → 루트 → 오른쪽)로 저장됩니다.
  • create_threadedtree(): 동일한 중위 순회 경로를 따라가면서 큐에서 노드를 하나씩 꺼냅니다(pop). 이때 오른쪽 자식이 없는 노드는 큐의 front에 있는 노드, 즉 바로 다음에 방문할 노드와 연결되어 스레드가 생성됩니다.
  • inOrder(): 변환된 스레드 트리를 검증합니다. 가장 왼쪽 노드부터 시작해, 스레드 플래그가 설정된 노드는 오른쪽 포인터를 타고 후속자로 곧장 이동하고, 그렇지 않으면 일반적인 방식으로 가장 왼쪽 노드를 찾아 내려갑니다.

이처럼 큐를 활용하면 별도의 부모 포인터나 복잡한 포인터 조작 없이도 간단하게 스레드 이진 트리를 만들 수 있으며, 이후 순회 시 재귀나 스택 없이 선형 시간에 중위 순회를 수행할 수 있다는 장점이 있습니다.