เข้ารหัส N-ary Tree เป็น Binary Tree ใน C++

สมมุติว่าเรามีต้น N-ary เราต้องเข้ารหัสต้นไม้นั้นเป็นหนึ่งไบนารี นอกจากนี้เรายังต้องทำดีซีเรียลไลเซอร์เพื่อทำการดีซีเรียลไลซ์ไบนารีทรีเป็นทรี N-ary

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์ที่ได้จะเป็น

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน encode() ซึ่งจะเริ่มต้น

• หากรูทถูกต้อง −

  • คืนค่า null

• node =โหนดต้นไม้ใหม่ที่มีค่ารูท

• ถ้าขนาดของรูทไม่ใช่ 0 ดังนั้น −

  • ด้านซ้ายของโหนด :=เข้ารหัส (ลูก[0] ของรูท)

• curr =ด้านซ้ายของโหนด

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <ขนาดของลูกของรูท ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • ทางขวาของโหนด :=เข้ารหัส (ลูก[i] ของรูท)

  • curr :=ด้านขวาของสกุลเงิน

• โหนดกลับ

• กำหนดฟังก์ชัน decode() ซึ่งจะเริ่มต้น

• หากไม่มีรูทอยู่ −

  • คืนค่า NULL

• node :=โหนดใหม่ที่มี val ของรูท

• curr :=เหลือราก

• ในขณะที่ค่าเงินไม่เป็นศูนย์ ให้ทำ -

  • แทรก decode(curr) ที่ส่วนท้ายของลูกของโหนด

  • curr :=ด้านขวาของสกุลเงิน

• โหนดกลับ

ตัวอย่าง

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

#include ใช้เนมสเปซ std;คลาส TreeNode {สาธารณะ:int val; TreeNode *ซ้าย *ขวา; TreeNode (ข้อมูล int) { val =data; ซ้าย =NULL; ขวา =NULL; }};โมฆะ inord (TreeNode *root) { if (root !=NULL) { inord (root->left); cout <val <<" "; inord(root->right); }} class Node { สาธารณะ:int val; เวกเตอร์<โหนด*> ลูก; โหนด () {} โหนด (int _val) { val =_val; } โหนด (int _val, เวกเตอร์<โหนด*> _children) { val =_val; เด็ก =_เด็ก; }};string n_ary_to_str(โหนด *root){ string ret =""; if(root){ ret =ret + to_string(root->val); if(root->children.size()> 0){ ret +="["; สำหรับ (โหนด* ลูก :รูท->ลูก){ ret +=n_ary_to_str(ลูก) + ","; } ret +="]"; } } return ret;} คลาส Codec {สาธารณะ:TreeNode* เข้ารหัส (โหนด* root) { if(!root) คืนค่า NULL; โหนด TreeNode* =ใหม่ TreeNode(root->val); if(root->children.size()){ node->left =encode(root->children[0]); } TreeNode* curr =node->left; for(int i =1; i children.size(); i++){ curr->right =encode(root->children[i]); curr =curr->ขวา; } โหนดกลับ; } Node* ถอดรหัส (TreeNode* root) { if(!root) คืนค่า NULL; โหนด* โหนด =โหนดใหม่(root->val); TreeNode*curr =root->left; ในขณะที่ (สกุลเงิน) { โหนด->children.push_back (ถอดรหัส (สกุลเงิน)); curr =curr->ขวา; } โหนดกลับ; }};main() { Codec ob; โหนด n5(5), n6(6); โหนด n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6); โหนด n2(2), n4(4); โหนด n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2); n1.children.push_back(&n4); cout <<"ให้ต้นไม้:" < 
อินพุต
 
โหนด n5(5), n6(6);โหนด n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6);โหนด n2(2), n4(4);โหนด n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2);n1.children.push_back(&n4);
 
ผลลัพธ์
 
ต้นไม้ที่กำหนด:1[3[5, 6, ], 2, 4, ]ต้นไม้ไบนารีแบบอนุกรม:5 6 3 2 4 1 ต้นไม้ดีซีเรียลไลซ์:1[3[5, 6, ], 2, 4, ]