เข้ารหัสต้นไม้ N-ary เป็นต้นไม้ไบนารีใน C++

สมมติว่าเรามีต้นไม้ N-ary เราต้องเข้ารหัสต้นไม้นั้นให้กลายเป็นต้นไม้ไบนารี และยังต้องทำ deserializer เพื่อคืนค่าต้นไม้ N-ary จากต้นไม้ไบนารี

เช่น ถ้าอินพุตเป็นรูปภาพดังนี้:

ผลลัพธ์จะเป็น:

ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:

• กำหนดฟังก์ชัน encode() รับ root: ถ้า root ว่าง คืนค่า null; สร้างโหนดไบนารีใหม่ค่าเท่า root; ถ้ามีลูก ให้ left ของโหนด = encode(ลูกตัวแรก); curr = left; ลูปลูกที่เหลือ: right ของ curr = encode(ลูกถัดไป); curr = right ของ curr; คืนค่าโหนด
• กำหนดฟังก์ชัน decode() รับ root: ถ้า root ว่าง คืนค่า NULL; สร้างโหนด N-ary ใหม่ค่าเท่า root; curr = left ของ root; while curr ไม่ว่าง: เพิ่ม decode(curr) เข้า children ของโหนด; curr = right ของ curr; คืนค่าโหนด

ตัวอย่าง

ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

#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 != NULL) { 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 = ret + to_string(root->val);
        if(root->children.size() > 0){
            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.size()){
            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;
    }
};
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 << "Given Tree: " << n_ary_to_str(&n1) << endl;
    cout << "Serialized Binary Tree: ";
    TreeNode *root = ob.encode(&n1);
    inord(root);
    cout << endl;
    Node *deser = ob.decode(root);
    cout << "Deserialized Tree: " << n_ary_to_str(deser);
}

อินพุต

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);

เอาต์พุต

Given Tree: 1[3[5, 6, ], 2, 4, ] Serialized Binary Tree: 5 6 3 2 4 1 Deserialized Tree: 1[3[5, 6, ], 2, 4, ]