C++에서 괄호가 포함된 문자열로 이진 트리 변환하기

문제 개요

이 문제에서는 하나의 이진 트리(Binary Tree)가 주어지며, C++를 사용하여 이 트리를 괄호가 포함된 문자열 형태로 변환하는 프로그램을 작성하는 것이 목표입니다.

이진 트리의 각 노드 값은 정수이며, 트리는 전위 순회(preorder traversal) 방식으로 프로그램에 입력됩니다. 최종적으로 만들어질 문자열에는 정수와 괄호 ()만 포함되어야 하며, 불필요한 요소를 제거하는 최적화도 필수입니다. 즉, 의미 없는 빈 괄호 쌍은 모두 삭제해야 합니다.

이진 트리란?

이진 트리는 각 노드가 최대 두 개의 자식 노드만 가질 수 있다는 특수한 조건을 만족하는 트리 자료구조입니다.

이진 트리 예시

위 트리의 전위 순회 결과 : [4, 1, 8, 3, 9, 2, 5]

입력 및 출력 예시

입력

preorder: [4, 1, 8, 3, 9, 2, 5]

출력 과정 설명

Root -> 4()() -> 4(1()())(9) -> 4(1(8()())())(9) -> 4(1(8(3)())())(9) -> 4(1(8(3)())())(9(2)(5))

여기서 모든 빈 괄호 쌍을 제거하면 다음과 같은 최종 문자열을 얻습니다.

4(1(8(3)))(9(2)(5))

문제 해결 접근 방법

이 문제는 재귀 호출을 활용한 전위 순회로 해결할 수 있습니다. 트리를 전위 순회하면서 필요한 위치에만 괄호를 배치하고, 불필요한 중첩 괄호는 제거합니다.

구체적으로는 노드의 값을 출력한 뒤, 해당 노드의 자식 노드들에 대해 재귀 함수를 호출합니다. 더 이상 호출할 자식이 없는 리프 노드(leaf node)에 도달하면 재귀를 종료합니다.

자식 노드 호출 시 발생하는 네 가지 경우

Case 1 − 양쪽 자식이 모두 있는 경우
왼쪽과 오른쪽 자식 각각에 대해 괄호를 붙이고, 그 안에 자식의 값을 넣습니다. 자식에게 하위 트리가 더 있으면 계속 재귀 호출합니다.
예시 − 루트 노드 4는 양쪽 자식이 모두 있으므로 4(1)(9) 형태가 됩니다.

Case 2 − 왼쪽 자식만 있는 경우
왼쪽 자식만 괄호로 감쌉니다. 오른쪽 자식이 없으므로 해당 괄호는 생략되며, 왼쪽 자식의 하위 트리만 재귀 호출합니다.
예시 − 값이 1인 노드는 왼쪽 자식만 있으므로 4(1(8()()))(9)처럼 표현됩니다.

Case 3 − 오른쪽 자식만 있는 경우
왼쪽 자식 자리에 빈 괄호를 유지해야 트리 구조가 유지됩니다. 오른쪽 자식의 값을 괄호 안에 넣고, 하위 트리가 있으면 계속 호출합니다.

Case 4 − 자식이 없는 경우(리프 노드)
괄호 없이 값만 출력합니다.
예시 − 값이 5인 노드는 자식이 없으므로 4(1(8(3)))(9(2)(5()()))에서 괄호가 제거된 형태로 표현됩니다.

C++ 구현 코드

다음은 위 접근 방식을 구현한 전체 프로그램입니다.

#include <iostream>
using namespace std;
struct Node {
    int data;
    Node *left, *right;
};
Node* insertNode(int data){
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
void ConveryBinaryTreeToString(Node* root, string& str){
    if (root == NULL)
    return;
    str.push_back(root->data + '0');
    if (!root->left && !root->right)
    return;
    str.push_back('(');
    ConveryBinaryTreeToString(root->left, str);
    str.push_back(')');
    if (root->right) {
        str.push_back('(');
        ConveryBinaryTreeToString(root->right, str);
        str.push_back(')');
    }
}
int main() {
    struct Node* root = insertNode(4);
    root->left = insertNode(1);
    root->right = insertNode(9);
    root->left->left = insertNode(8);
    root->left->left->left = insertNode(3);
    root->right->left = insertNode(2);
    root->right->right = insertNode(5);
    string binaryTreeString = "";
    ConveryBinaryTreeToString(root, binaryTreeString);
    cout<<"괄호가 포함된 이진 트리의 전위 순회 문자열: "<<binaryTreeString;
}

실행 결과

괄호가 포함된 이진 트리의 전위 순회 문자열: 4(1(8(3)))(9(2)(5))