Straight hóa và giải mã cây N-ary trong C++

Cho một cây N-ary, hãy serialize (chuyển thành chuỗi) và deserialize (khôi phục từ chuỗi). Serialization là quá trình chuyển cấu trúc dữ liệu thành chuỗi bit để lưu trữ.

Ví dụ:

Kết quả: Serialize: "1 #3 2 4 #5 6 #####" và Deserialized Tree: 1[3[5, 6], 2, 4]

Phương pháp giải

Serialize: Duyệt BFS (theo cấp). Ghi giá trị gốc, rồi "#". Với mỗi nút, ghi giá trị các con cách nhau bởi khoảng trắng, kết thúc bằng "#".

Deserialize: Phân tích chuỗi thành mảng 2D (mỗi hàng là một cấp). Khôi phục cây theo cấp: nút gốc từ hàng 0, các con từ hàng 1, 2, ...

Ví dụ chương trình

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int val;
    vector children;
    Node() {}
    Node(int _val) : val(_val) {}
    Node(int _val, vector _children) : val(_val), children(_children) {}
};

string n_ary_to_str(Node* root) {
    string ret = "";
    if (root) {
        ret += to_string(root->val);
        if (!root->children.empty()) {
            ret += "[";
            for (Node* child : root->children) ret += n_ary_to_str(child) + ", ";
            ret += "]";
        }
    }
    return ret;
}

class Codec {
public:
    vector> createVector(string s) {
        vector> ret;
        vector tempv;
        string temp = "";
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != ' ' && s[i] != '#') temp += s[i];
            else if (s[i] == ' ') {
                tempv.push_back(stoi(temp));
                temp = "";
            } else if (s[i] == '#') {
                ret.push_back(tempv);
                temp = "";
                tempv.clear();
            }
        }
        while (!ret.empty() && ret.back().empty()) ret.pop_back();
        return ret;
    }
    
    string serialize(Node* root) {
        string ret = "";
        if (!root) return ret;
        queue q;
        q.push(root);
        ret += to_string(root->val) + " #";
        while (!q.empty()) {
            Node* curr = q.front(); q.pop();
            for (int i = 0; i < curr->children.size(); i++) {
                if (curr->children[i]) {
                    ret += to_string(curr->children[i]->val);
                    q.push(curr->children[i]);
                }
                ret += " ";
            }
            ret += "#";
        }
        return ret;
    }
    
    Node* deserialize(string data) {
        if (data.empty()) return NULL;
        vector> v = createVector(data);
        Node* ret = new Node(v[0][0]);
        queue q;
        q.push(ret);
        int i = 1;
        while (!q.empty() && i < v.size()) {
            Node* curr = q.front(); q.pop();
            for (int j = 0; j < v[i].size(); j++) {
                Node* temp = new Node(v[i][j]);
                curr->children.push_back(temp);
                q.push(temp);
            }
            i++;
        }
        return ret;
    }
};

int main() {
    Codec ob;
    Node n5(5), n6(6);
    Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6);
    Node n2(2), n4(4);
    Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2); n1.children.push_back(&n4);
    
    cout << "Cây gốc: " << n_ary_to_str(&n1) << endl;
    string ser = ob.serialize(&n1);
    cout << "Serialize: " << ser << endl;
    Node* deser = ob.deserialize(ser);
    cout << "Deserialized: " << n_ary_to_str(deser);
    return 0;
}

Đầu vào

Cây N-ary: 1[3[5, 6], 2, 4]

Đầu ra

Serialize: 1 #3 2 4 #5 6 #####
Deserialized: 1[3[5, 6], 2, 4]