[c++] 트리의 직렬화(Serialize a Tree)

12 Dec 2023

이번 블로그에서는 C++를 사용하여 트리의 직렬화에 대해 알아보겠습니다. 트리를 직렬화하는 것은 트리의 구조를 문자열 또는 배열로 표현하는 것을 의미합니다. 이는 트리를 저장하거나 네트워크를 통해 전송할 때 유용합니다.

트리의 직렬화(Serialize)

트리의 직렬화는 다양한 방법으로 수행할 수 있지만, 여기서는 전위 순회(preorder traversal)를 사용하여 직렬화하는 방법을 다룰 것입니다. 전위 순회는 노드를 방문한 후에 왼쪽 서브트리를 방문하고 오른쪽 서브트리를 방문하는 방식으로 순회하는 방법입니다.

아래는 트리의 노드를 표현하는 C++ 클래스의 예시입니다.

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

전위 순회를 사용하여 트리를 직렬화하는 코드는 다음과 같습니다.

class Solution {
public:
    string serialize(TreeNode* root) {
        if (root == nullptr) {
            return "null,";
        }
        return to_string(root->val) + "," + serialize(root->left) + serialize(root->right);
    }
};

트리의 역직렬화(Deserialize a Tree)

트리의 역직렬화는 직렬화된 트리를 다시 원래의 트리 구조로 복원하는 과정을 말합니다. 이를 위해 직렬화된 문자열을 분석하여 트리를 재구성해야 합니다.

아래는 트리의 역직렬화를 수행하는 C++ 코드의 예시입니다.

class Solution {
public:
    TreeNode* deserialize(string data) {
        istringstream iss(data);
        return buildTree(iss);
    }
    
    TreeNode* buildTree(istringstream& iss) {
        string val;
        getline(iss, val, ',');
        if (val == "null") {
            return nullptr;
        }
        else {
            TreeNode* node = new TreeNode(stoi(val));
            node->left = buildTree(iss);
            node->right = buildTree(iss);
            return node;
        }
    }
};

마무리

이제 C++를 사용하여 트리의 직렬화와 역직렬화에 대해 간단히 살펴보았습니다. 트리의 직렬화와 역직렬화는 데이터 구조를 다루는 많은 애플리케이션에서 유용하게 활용될 수 있으며, 이러한 기술을 통해 데이터를 효과적으로 저장하고 전송할 수 있습니다.

더 자세한 내용은 아래의 참고 자료를 참고하시기 바랍니다.