Mã hóa N-ary Tree thành Binary Tree trong C ++

Giả sử chúng ta có một cây N-ary. Chúng ta phải mã hóa cây đó thành một bản nhị phân. Chúng tôi cũng phải tạo deserializer để giải không khí từ cây nhị phân thành cây N-ary.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một mã hóa hàm (), mã này sẽ bắt nguồn từ gốc,

• nếu root hợp lệ, thì -

  • trả về null

• node =nút cây mới với giá trị gốc

• nếu kích thước con của root không phải là 0, thì -

  • left of node:=encode (con [0] of root)

• curr =bên trái của nút

• để khởi tạo i:=1, khi tôi

  • bên phải của nút:=encode (con [i] của gốc)

  • curr:=right of curr

• nút trả lại

• Xác định một hàm decode (), hàm này sẽ bắt nguồn từ gốc,

• nếu root không có mặt, thì -

  • trả về NULL

• node:=new node với val of root

• curr:=left of root

• trong khi curr khác 0, do -

  • chèn giải mã (curr) vào cuối nút con của nút

  • curr:=right of curr

• nút trả lại

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

 #include  using namespace std; class TreeNode {public:int val; TreeNode * left, * right; TreeNode (int data) {val =data; trái =NULL; phải =NULL; }}; void inord (TreeNode * root) {if (root! =NULL) {inord (root-> left); cout < val <<""; inord (root-> right); }} Node lớp {public:int val; vector  con; Node () {} Node (int _val) {val =_val; } Node (int _val, vector  _children) {val =_val; con cái =_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  children.size (); i ++) {curr-> right =encode (root-> children [i]); curr =curr-> đúng; } nút trả về; } 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-> đúng; } nút trả về; }}; main () {Codec ob; Nút n5 (5), n6 (6); Nút n3 (3); n3.children.push_back (&​​n5); n3.children.push_back (&​​n6); Nút n2 (2), n4 (4); Nút n1 (1); n1.children.push_back (&​​n3); n1.children.push_back (&​​n2); n1.children.push_back (&​​n4); cout <<"Cho cây:" < 
 Đầu vào 
 
 Nút n5 (5), n6 (6); Nút n3 (3); n3.children.push_back (&​​n5); n3.children.push_back (&​​n6); Nút n2 (2), n4 (4); Nút n1 (1); n1.children.push_back (&​​n3); n1.children.push_back (&​​n2); n1.children.push_back (&​​n4); 
 
 Đầu ra 
 
 Given Tree:1 [3 [5, 6,], 2, 4,] Serialized Binary Tree:5 6 3 2 4 1Deserialized Tree:1 [3 [5, 6,], 2, 4,]