資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中N元樹的序列化和反序列化
假設我們有一棵N元樹，我們需要對其進行序列化和反序列化。眾所周知，序列化是將資料結構或物件轉換為一系列位元的過程，以便我們可以將其儲存在檔案或記憶體緩衝區中，並在以後在相同或不同的計算機環境中重建它。
這裡我們需要設計一個演算法來序列化和反序列化N元樹。N元樹是一棵根樹，其中每個節點最多有N個子節點。
因此，如果輸入如下所示：
則輸出將是序列化：1 #3 2 4 #5 6 ##### 反序列化樹：1[3[5, 6, ], 2, 4, ]
為了解決這個問題，我們將遵循以下步驟：
定義一個函式`createVector()`，它將接收s作為引數。
定義一個二維陣列`ret`
定義一個數組`tempv`
`temp :=`空字串
從`i := 0`開始迴圈，當`i < s`的長度時，更新（將i加1），執行：
如果`s[i]`不等於空格並且`s[i]`不等於'#'，則：
`temp := temp + s[i]`
否則，如果`s[i]`等於空格，則：
將`temp`轉換為整數，並將其新增到`tempv`的末尾。
`temp :=`空字串
否則，如果`s[i]`等於'#'，則：
將`tempv`新增到`ret`的末尾。
`temp :=`空字串
清空`tempv`。
當`ret`不為空且`ret`的最後一個元素等於0時，執行：
從`ret`中刪除最後一個元素。
返回`ret`。
定義一個函式`serialize()`，它將接收根節點作為引數。
`ret :=`空字串
如果根節點不為空，則：
返回`ret`。
定義一個佇列`q`。
將根節點插入到`q`中。
`rret := ret`連線根節點的值。
`ret := ret`連線空格。
`ret := ret`連線"#"
當`q`不為空時，執行：
`curr = q`的第一個元素。
從`q`中刪除元素。
從`i := 0`開始迴圈，當`i < curr`的子節點陣列的大小時，更新（將i加1），執行：
如果`curr`的`children[i]`存在，則：
`ret := ret`連線`curr`的`children[i]`。
將`curr`的`children[i]`插入到`q`中。
`ret := ret +`空格
`ret := ret`連線"#"
返回`ret`。
定義一個函式`deserialize()`，它將接收資料作為引數。
如果資料的長度等於0，則：
返回`null`。
定義一個二維陣列`v := createVector(data)`。
`ret :=`一個值為`v[0, 0]`的新節點。
定義一個佇列`q`。
將`ret`插入到`q`中。
`i := 1`
當`q`不為空且`i − v`的長度時，執行：
`curr = q`的第一個元素。
從`q`中刪除元素。
從`j := 0`開始迴圈，當`j − v[i]`的長度時，更新（將j加1），執行：
`node := v[i, j]`
`temp =`一個值為`node`的新節點。
將`temp`新增到`curr`的子節點的末尾。
將`temp`插入到`q`中。
將`i`加1。
返回`ret`。
示例
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _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:
vector<vector<int>>createVector(string s) {
vector<vector<int>> ret;
vector<int> tempv;
string temp = "";
for (int i = 0; i < s.size(); i++) {
if (s[i] != ' ' && s[i] != '#') {
temp += s[i];
}
else if (s[i] == ' ') {
tempv.push_back(stoi(temp));
temp = "";
}
else if (s[i] == '#') {
ret.push_back(tempv);
temp = "";
tempv.clear();
}
}
while (!ret.empty() && ret.back().size() == 0)
ret.pop_back();
return ret;
}
string serialize(Node *root) {
string ret = "";
if (!root)
return ret;
queue<Node *> q;
q.push(root);
ret += to_string(root->val);
ret += " ";
ret += "#";
while (!q.empty()) {
Node *curr = q.front();
q.pop();
for (int i = 0; i < curr->children.size(); i++) {
if (curr->children[i]) {
ret += to_string(curr->children[i]->val);
q.push(curr->children[i]);
}
ret += " ";
}
ret += "#";
}
return ret;
}
Node *deserialize(string data) {
Node *ret;
if (data.size() == 0)
return NULL;
vector<vector<int>> v = createVector(data);
ret = new Node(v[0][0]);
queue<Node *> q;
q.push(ret);
int i = 1;
while (!q.empty() && i < v.size()) {
Node *curr = q.front();
q.pop();
for (int j = 0; j < v[i].size(); j++) {
int node = v[i][j];
Node *temp = new Node(node);
curr->children.push_back(temp);
q.push(temp);
}
i++;
}
return ret;
}
};
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;
string ser = ob.serialize(&n1);
cout << "Serialize: " << ser << endl;
Node *deser = ob.deserialize(ser);
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, ] Serialize: 1 #3 2 4 #5 6 ##### Deserialized Tree: 1[3[5, 6, ], 2, 4, ]
341 次瀏覽
