資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中二叉樹的序列化與反序列化
假設我們有一棵二叉樹，我們需要對其進行序列化和反序列化。眾所周知，序列化是將資料結構或物件轉換為一系列位流的過程，以便可以將其儲存在檔案或記憶體緩衝區中，並在以後在相同或不同的計算機環境中重建。
這裡，我們需要設計一種演算法來序列化和反序列化二叉樹。二叉樹是一種根樹，其中每個節點最多有兩個子節點。
因此，如果輸入是這樣的：
那麼輸出將是：序列化 - 1 2 3 4 5 N N N N N N 反序列化樹：4 2 5 1 3。
為了解決這個問題，我們將遵循以下步驟：
定義一個序列化函式`serialize()`，它將接收根節點作為引數。
ret := 空字串
定義一個佇列q
將根節點插入到q中
當(q不為空)時，執行：
curr = q的第一個元素
從q中刪除該元素
如果curr不可用，則：
ret := ret + "N"
ret := ret + 空格
忽略以下部分，跳到下一個迭代
ret := ret + curr的值
ret := ret + 空格
將curr的左子節點新增到q的末尾
將curr的右子節點新增到q的末尾
返回ret
定義一個反序列化函式`deserialize()`，它將接收資料作為引數。
如果data[0] == 'N'，則：
返回NULL
temp := 空字串
定義一個數組v
for i := 0 to data.length -1:
如果data[i] == 空格，則：
將temp新增到v的末尾
temp := 空字串
忽略以下部分，跳到下一個迭代
temp := temp + data[i]
newRoot = 新節點，值為v[0]
定義一個佇列q
將newRoot插入到q中
i := 1
當(q不為空且i < v.length)時，執行：
parent = q的第一個元素
從q中刪除該元素
如果v[i] != "N"，則：
parent的左子節點 := 新節點，值為v[i]
將parent的左子節點插入到q中
i++
如果v[i] != "N"，則：
parent的右子節點 := 新節點，值為v[i]
將parent的右子節點插入到q中
i++
返回newRoot
示例
讓我們來看下面的實現，以便更好地理解：
#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 insert(TreeNode **root, int val) {
queue<TreeNode *> q;
q.push(*root);
while (q.size()) {
TreeNode *temp = q.front();
q.pop();
if (!temp->left) {
if (val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}
else {
q.push(temp->left);
}
if (!temp->right) {
if (val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}
else {
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v) {
TreeNode *root = new TreeNode(v[0]);
for (int i = 1; i < v.size(); i++) {
insert(&root, v[i]);
}
return root;
}
void inord(TreeNode *root) {
if (root != NULL) {
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Codec {
public:
string serialize(TreeNode *root) {
string ret = "";
queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
TreeNode *curr = q.front();
q.pop();
if (!curr) {
ret += "N";
ret += " ";
continue;
}
ret += to_string(curr->val);
ret += " ";
q.push(curr->left);
q.push(curr->right);
}
return ret;
}
TreeNode *deserialize(string data) {
if (data[0] == 'N')
return NULL;
string temp = "";
vector<string> v;
for (int i = 0; i < data.size(); i++) {
if (data[i] == ' ') {
v.push_back(temp);
temp = "";
continue;
}
temp += data[i];
}
TreeNode *newRoot = new TreeNode(stoi(v[0]));
queue<TreeNode *> q;
q.push(newRoot);
int i = 1;
while (!q.empty() && i < v.size()) {
TreeNode *parent = q.front();
q.pop();
if (v[i] != "N") {
parent->left = new TreeNode(stoi(v[i]));
q.push(parent->left);
}
i++;
if (v[i] != "N") {
parent->right = new TreeNode(stoi(v[i]));
q.push(parent->right);
}
i++;
}
return newRoot;
}
};
main() {
Codec ob;
vector<int> v = {1,2,3,4,5};
TreeNode *root = make_tree(v);
cout << "Given Tree: ";
inord(root);
cout << endl;
string ser = ob.serialize(root);
cout << "Serialize: " << ser << endl;
TreeNode *deser = ob.deserialize(ser);
cout << "Deserialized Tree: ";
inord(root);
}輸入
1,2,3,4,5
輸出
Given Tree: 4 2 5 1 3 Serialize: 1 2 3 4 5 N N N N N N Deserialized Tree: 4 2 5 1 3
766 次瀏覽
