Mã hóa cây N-ary thành cây nhị phân trong C++

Cho một cây N-ary (mỗi nút có nhiều con). Hãy mã hóa cây đó thành cây nhị phân, và giải mã ngược lại.

Ví dụ minh họa:

Phương pháp giải

Mã hóa (encode): Nút gốc của cây nhị phân = nút gốc N-ary. Con trái = mã hóa của con đầu tiên. Các con em của nút nhị phân = các con tiếp theo của nút N-ary (liên kết bằng con phải).

Giải mã (decode): Nút gốc N-ary = nút gốc nhị phân. Duyệt qua danh sách con phải của con trái để giải mã từng con.

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 inord(TreeNode* root) {
    if (root) {
        inord(root->left);
        cout << root->val << " ";
        inord(root->right);
    }
}

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:
    TreeNode* encode(Node* root) {
        if (!root) return NULL;
        TreeNode* node = new TreeNode(root->val);
        if (!root->children.empty()) {
            node->left = encode(root->children[0]);
        }
        TreeNode* curr = node->left;
        for (int i = 1; i < root->children.size(); i++) {
            curr->right = encode(root->children[i]);
            curr = curr->right;
        }
        return node;
    }
    
    Node* decode(TreeNode* root) {
        if (!root) return NULL;
        Node* node = new Node(root->val);
        TreeNode* curr = root->left;
        while (curr) {
            node->children.push_back(decode(curr));
            curr = curr->right;
        }
        return node;
    }
};

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 N-ary: " << n_ary_to_str(&n1) << endl;
    cout << "Cây nhị phân (duyệt in-order): ";
    TreeNode* root = ob.encode(&n1);
    inord(root);
    cout << endl;
    Node* deser = ob.decode(root);
    cout << "Cây giải mã: " << n_ary_to_str(deser);
    return 0;
}

Đầu vào

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

Đầu ra

Cây N-ary: 1[3[5, 6], 2, 4]
Cây nhị phân (in-order): 5 6 3 2 4 1
Cây giải mã: 1[3[5, 6], 2, 4]