Straight hóa và giải mã cây nhị phân trong C++

Cho một cây nhị phân, hãy serialize (chuyển thành chuỗi) và deserialize (khôi phục từ chuỗi). Cây nhị phân: mỗi nút tối đa 2 con.

Ví dụ:

Serialize: "1 2 3 4 5 N N N N N N", Deserialized Tree: 4 2 5 1 3 (in-order).

Phương pháp giải

Serialize: BFS (duyệt theo cấp). Dùng queue. Ghi giá trị nút, "N" cho null. Thêm con trái, con phải vào queue.

Deserialize: Tách chuỗi thành mảng token. Tạo gốc từ token đầu. Dùng queue: lấy nút cha, gán con trái/phải từ token tiếp theo, thêm con vào queue.

Ví dụ chương trình

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) : val(data), left(NULL), right(NULL) {}
};

void insert(TreeNode** root, int val) {
    queue q;
    q.push(*root);
    while (q.size()) {
        TreeNode* temp = q.front(); q.pop();
        if (!temp->left) {
            if (val != NULL) temp->left = new TreeNode(val);
            else temp->left = new TreeNode(0);
            return;
        } else q.push(temp->left);
        if (!temp->right) {
            if (val != NULL) temp->right = new TreeNode(val);
            else temp->right = new TreeNode(0);
            return;
        } else q.push(temp->right);
    }
}

TreeNode* make_tree(vector v) {
    TreeNode* root = new TreeNode(v[0]);
    for (int i = 1; i < v.size(); i++) insert(&root, v[i]);
    return root;
}

void inord(TreeNode* root) {
    if (root) {
        inord(root->left);
        cout << root->val << " ";
        inord(root->right);
    }
}

class Codec {
public:
    string serialize(TreeNode* root) {
        string ret = "";
        queue q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* curr = q.front(); q.pop();
            if (!curr) { ret += "N "; continue; }
            ret += to_string(curr->val) + " ";
            q.push(curr->left);
            q.push(curr->right);
        }
        return ret;
    }
    
    TreeNode* deserialize(string data) {
        if (data[0] == 'N') return NULL;
        string temp = "";
        vector v;
        for (int i = 0; i < data.size(); i++) {
            if (data[i] == ' ') { v.push_back(temp); temp = ""; continue; }
            temp += data[i];
        }
        TreeNode* newRoot = new TreeNode(stoi(v[0]));
        queue q;
        q.push(newRoot);
        int i = 1;
        while (!q.empty() && i < v.size()) {
            TreeNode* parent = q.front(); q.pop();
            if (v[i] != "N") { parent->left = new TreeNode(stoi(v[i])); q.push(parent->left); }
            i++;
            if (v[i] != "N") { parent->right = new TreeNode(stoi(v[i])); q.push(parent->right); }
            i++;
        }
        return newRoot;
    }
};

int main() {
    Codec ob;
    vector v = {1,2,3,4,5};
    TreeNode* root = make_tree(v);
    cout << "Cây gốc (in-order): "; inord(root); cout << endl;
    string ser = ob.serialize(root);
    cout << "Serialize: " << ser << endl;
    TreeNode* deser = ob.deserialize(ser);
    cout << "Deserialized (in-order): "; inord(deser);
    return 0;
}

Đầu vào

1,2,3,4,5

Đầu ra

Cây gốc: 4 2 5 1 3
Serialize: 1 2 3 4 5 N N N N N N
Deserialized: 4 2 5 1 3