Java版本和C++版本的二叉樹序列化與反序列化
更新時(shí)間：2022年06月21日 09:38:20 作者：明朗晨光
這篇文章主要介紹了Java版本和C++版本的二叉樹序列化與反序列化，二叉樹就是節(jié)點(diǎn)在內(nèi)存區(qū)域中串聯(lián)起來的，但是如果掉電，內(nèi)存上的數(shù)據(jù)就沒有了。為了保存這種結(jié)構(gòu)，將二叉樹用字符串的形式保存到硬盤中，這就是序列化；從字符串形式轉(zhuǎn)換為二叉樹，這就是反序列化
1、什么是二叉樹的序列化與反序列化
二叉樹就是節(jié)點(diǎn)在內(nèi)存區(qū)域中串聯(lián)起來的，但是如果掉電，內(nèi)存上的數(shù)據(jù)就沒有了。為了保存這種結(jié)構(gòu)，將二叉樹用字符串的形式保存到硬盤中，這就是序列化；從字符串形式轉(zhuǎn)換為二叉樹，這就是反序列化。
唯一的字符串會對應(yīng)唯一的結(jié)構(gòu)，唯一的結(jié)構(gòu)也會對應(yīng)唯一的字符串，即字符串和二叉樹是一一對應(yīng)的。
【思路】首先認(rèn)為 NULL 是不可忽略的，遇到 NULL 就用 # 或者其他字符代替。且每訪問結(jié)束一個(gè)節(jié)點(diǎn)，用分隔符隔開。
2、先序方式序列化和反序列化
【例子】
上圖紅色數(shù)字就是先序遍歷的順序，所以得到的字符串就是 “1，1，#，1，#，#，#”。
之所以要用分隔符隔開，是為了防止二義性，比如如下兩棵樹：
【代碼實(shí)現(xiàn)】
//先序序列化二叉樹
void preS(TreeNode *root, queue<string> &ans) {
if (root == nullptr)
ans.push("#");
else {
//每個(gè)節(jié)點(diǎn)轉(zhuǎn)成的字符串保存到隊(duì)列中
ans.push(to_string(root->value));
preS(root->lchild, ans);
preS(root->rchild, ans);
}
}
queue<string> preOrderSerial(TreeNode *root) {
queue<string> ans;
preS(root, ans);
return ans;
}
TreeNode *preb(queue<string> &prelist) {
string value = prelist.front();
prelist.pop();
//空樹
if (value == "#") return nullptr;
TreeNode *root = new TreeNode(stoi(value)); //每個(gè)節(jié)點(diǎn)字符串轉(zhuǎn)成整數(shù)
root->lchild = preb(prelist);
root->rchild = preb(prelist);
return root;
}
//以先序序列化還原二叉樹, 即反序列化
TreeNode *buildByPreQueue(queue<string> &prelist) {
if (prelist.size() == 0) return nullptr;
return preb(prelist);
}3、后序方式序列化和反序列化
//后序序列化
void posS(TreeNode *root, queue<string> &ans) {
if (root == nullptr)
ans.push("#");
else {
posS(root->lchild, ans);
posS(root->rchild, ans);
ans.push(to_string(root->value));
}
}
queue<string> posOrderSerial(TreeNode *root) {
queue<string> ans;
posS(root, ans);
return ans;
}
//后序反序列化
TreeNode *posB(stack<string> &posstack) {
string value = posstack.top();
posstack.pop();
if (value == "#") return nullptr;
TreeNode *root = new TreeNode(stoi(value));
root->rchild = posB(posstack);
root->lchild = posB(posstack);
return root;
}
TreeNode *buildByPosQueue(queue<string> &poslist) {
if (poslist.size() == 0)
return nullptr;
stack<string> sta; //棧中的順序?yàn)椋褐杏易?
while (!poslist.empty()) {
sta.push(poslist.front());
poslist.pop();
}
return posB(sta);
}4、層序方式序列化和反序列化
//層序序列化
queue<string> levelSerial(TreeNode *root) {
queue<string> ans;
if (root == nullptr) {
ans.push("#");
} else {
ans.push(to_string(root->value));
//準(zhǔn)備隊(duì)列，用于層序遍歷
queue<TreeNode *> que;
que.push(root);
while (!que.empty()) {
TreeNode *cur = que.front();
que.pop();
if (cur->lchild != nullptr) {
ans.push(to_string(cur->lchild->value));
que.push(cur->lchild);
} else {
ans.push("#");
}
if (cur->rchild != nullptr) {
ans.push(to_string(cur->rchild->value));
que.push(cur->rchild);
} else {
ans.push("#");
}
}
}
return ans;
}
//層序反序列化
TreeNode *generateTreeNode(string str) {
if (str == "#") return nullptr;
return new TreeNode(stoi(str));
}
TreeNode *buildByLevelQueue(queue<string> &levelList) {
if (levelList.size() == 0) {
return nullptr;
}
TreeNode *root = generateTreeNode(levelList.front());
levelList.pop();
queue<TreeNode *> que;
if (root != nullptr) {
que.push(root);
}
TreeNode *cur = nullptr;
while (!que.empty()) {
cur = que.front();
que.pop();
cur->lchild = generateTreeNode(levelList.front());
levelList.pop();
cur->rchild = generateTreeNode(levelList.front());
levelList.pop();
if (cur->lchild != nullptr) {
que.push(cur->lchild);
}
if (cur->rchild != nullptr) {
que.push(cur->rchild);
}
}
return root;
}5、完整代碼 C++ 版
/*************************************************************************
> File Name: 029.二叉樹的序列化與反序列化.cpp
> Author: Maureen
> Mail: Maureen@qq.com
> Created Time: 一 6/20 17:40:56 2022
************************************************************************/
#include <iostream>
#include <cstring>
#include <queue>
#include <ctime>
#include <stack>
using namespace std;
/*
* 二叉樹可以通過先序、后序或者按層遍歷的方式序列化和反序列化，
* 以下代碼全部實(shí)現(xiàn)了。
* 但是，二叉樹無法通過中序遍歷的方式實(shí)現(xiàn)序列化和反序列化
* 因?yàn)椴煌膬煽脴?，可能得到同樣的中序序列，即便補(bǔ)了空位置也可能一樣。
* 比如如下兩棵樹
* __2
* /
* 1
* 和
* 1__
* \
* 2
* 補(bǔ)足空位置的中序遍歷結(jié)果都是{ null, 1, null, 2, null}
*
* */
class TreeNode {
public:
int value;
TreeNode *lchild;
TreeNode *rchild;
TreeNode(int data) : value(data) {}
};
//先序序列化二叉樹
void preS(TreeNode *root, queue<string> &ans) {
if (root == nullptr)
ans.push("#");
else {
//每個(gè)節(jié)點(diǎn)轉(zhuǎn)成的字符串保存到隊(duì)列中
ans.push(to_string(root->value));
preS(root->lchild, ans);
preS(root->rchild, ans);
}
}
queue<string> preOrderSerial(TreeNode *root) {
queue<string> ans;
preS(root, ans);
return ans;
}
//以先序序列化還原二叉樹, 即反序列化
TreeNode *preb(queue<string> &prelist) {
string value = prelist.front();
prelist.pop();
//空樹
if (value == "#") return nullptr;
TreeNode *root = new TreeNode(stoi(value)); //每個(gè)節(jié)點(diǎn)字符串轉(zhuǎn)成整數(shù)
root->lchild = preb(prelist);
root->rchild = preb(prelist);
return root;
}
TreeNode *buildByPreQueue(queue<string> &prelist) {
if (prelist.size() == 0) return nullptr;
return preb(prelist);
}
//后序序列化
void posS(TreeNode *root, queue<string> &ans) {
if (root == nullptr)
ans.push("#");
else {
posS(root->lchild, ans);
posS(root->rchild, ans);
ans.push(to_string(root->value));
}
}
queue<string> posOrderSerial(TreeNode *root) {
queue<string> ans;
posS(root, ans);
return ans;
}
//后序反序列化
TreeNode *posB(stack<string> &posstack) {
string value = posstack.top();
posstack.pop();
if (value == "#") return nullptr;
TreeNode *root = new TreeNode(stoi(value));
root->rchild = posB(posstack);
root->lchild = posB(posstack);
return root;
}
TreeNode *buildByPosQueue(queue<string> &poslist) {
if (poslist.size() == 0)
return nullptr;
stack<string> sta; //棧中的順序?yàn)椋褐杏易?
while (!poslist.empty()) {
sta.push(poslist.front());
poslist.pop();
}
return posB(sta);
}
//層序序列化
queue<string> levelSerial(TreeNode *root) {
queue<string> ans;
if (root == nullptr) {
ans.push("#");
} else {
ans.push(to_string(root->value));
//準(zhǔn)備隊(duì)列，用于層序遍歷
queue<TreeNode *> que;
que.push(root);
while (!que.empty()) {
TreeNode *cur = que.front();
que.pop();
if (cur->lchild != nullptr) {
ans.push(to_string(cur->lchild->value));
que.push(cur->lchild);
} else {
ans.push("#");
}
if (cur->rchild != nullptr) {
ans.push(to_string(cur->rchild->value));
que.push(cur->rchild);
} else {
ans.push("#");
}
}
}
return ans;
}
//層序反序列化
TreeNode *generateTreeNode(string str) {
if (str == "#") return nullptr;
return new TreeNode(stoi(str));
}
TreeNode *buildByLevelQueue(queue<string> &levelList) {
if (levelList.size() == 0) {
return nullptr;
}
TreeNode *root = generateTreeNode(levelList.front());
levelList.pop();
queue<TreeNode *> que;
if (root != nullptr) {
que.push(root);
}
TreeNode *cur = nullptr;
while (!que.empty()) {
cur = que.front();
que.pop();
cur->lchild = generateTreeNode(levelList.front());
levelList.pop();
cur->rchild = generateTreeNode(levelList.front());
levelList.pop();
if (cur->lchild != nullptr) {
que.push(cur->lchild);
}
if (cur->rchild != nullptr) {
que.push(cur->rchild);
}
}
return root;
}
//for test
TreeNode *generate(int level, int maxLevel, int maxValue) {
if (level > maxLevel || rand() % 100 < 0.5) return nullptr;
TreeNode *root = new TreeNode(rand() % maxValue);
root->lchild = generate(level + 1, maxLevel, maxValue);
root->rchild = generate(level + 1, maxLevel, maxValue);
return root;
}
TreeNode *generateRandomBST(int maxLen, int maxVal) {
return generate(1, maxLen, maxVal);
}
bool isSameValueStructure(TreeNode *root1, TreeNode *root2) {
if (root1 == nullptr && root2 != nullptr)
return false;
if (root1 != nullptr && root2 == nullptr)
return false;
if (root1 == nullptr && root2 == nullptr)
return true;
if (root1->value != root2->value)
return false;
return isSameValueStructure(root1->lchild, root2->lchild) && isSameValueStructure(root1->rchild, root2->rchild);
}
string getSpace(int num) {
string space = "";
for (int i = 0; i < num; i++) {
space += " ";
}
return space;
}
void printInOrder(TreeNode *root, int height, string to, int len) {
if (root == nullptr) return ;
printInOrder(root->rchild, height + 1, "v", len);
string val = to + to_string(root->value) + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
cout << getSpace(height * len) + val << endl;
printInOrder(root->lchild, height + 1, "^", len);
}
void printTree(TreeNode *root) {
cout << "Binary Tree:" << endl;
printInOrder(root, 0, "H", 7);
cout << endl;
}
int main() {
srand(time(0));
int maxLevel = 5;
int maxValue = 100;
int testTime = 1000000;
cout << "test begin" << endl;
for (int i = 0; i < testTime + 1; i++) {
TreeNode *root = generateRandomBST(maxLevel, maxValue);
queue<string> pre = preOrderSerial(root);
queue<string> post = posOrderSerial(root);
queue<string> level = levelSerial(root);
TreeNode *preBuild = buildByPreQueue(pre);
TreeNode *posBuild = buildByPosQueue(post);
TreeNode *levelBuild = buildByLevelQueue(level);
/*bool isPreBuildisSuccess = isSameValueStructure(root, preBuild);
bool isPosBuildisSuccess = isSameValueStructure(root, posBuild);
bool isLevelBuildSuccess = isSameValueStructure(root, levelBuild);
cout << isPreBuildisSuccess << ", " << isPosBuildisSuccess << ", " << isLevelBuildSuccess << endl;*/
if (!isSameValueStructure(preBuild, posBuild) || !isSameValueStructure(posBuild, levelBuild)) {
cout << "Oops!" << endl;
break;
}
if (i && i % 100 == 0) cout << i << " cases passed!" << endl;
}
cout << "test finish!" << endl;
return 0;
}Java 版
package class11;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Code02_SerializeAndReconstructTree {
/*
* 二叉樹可以通過先序、后序或者按層遍歷的方式序列化和反序列化，
* 以下代碼全部實(shí)現(xiàn)了。
* 但是，二叉樹無法通過中序遍歷的方式實(shí)現(xiàn)序列化和反序列化
* 因?yàn)椴煌膬煽脴?，可能得到同樣的中序序列，即便補(bǔ)了空位置也可能一樣。
* 比如如下兩棵樹
* __2
* /
* 1
* 和
* 1__
* \
* 2
* 補(bǔ)足空位置的中序遍歷結(jié)果都是{ null, 1, null, 2, null}
*
* */
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static Queue<String> preSerial(Node head) {
Queue<String> ans = new LinkedList<>();
pres(head, ans);
return ans;
}
public static void pres(Node head, Queue<String> ans) {
if (head == null) {
ans.add(null);
} else {
ans.add(String.valueOf(head.value));
pres(head.left, ans);
pres(head.right, ans);
}
}
public static Queue<String> inSerial(Node head) {
Queue<String> ans = new LinkedList<>();
ins(head, ans);
return ans;
}
public static void ins(Node head, Queue<String> ans) {
if (head == null) {
ans.add(null);
} else {
ins(head.left, ans);
ans.add(String.valueOf(head.value));
ins(head.right, ans);
}
}
public static Queue<String> posSerial(Node head) {
Queue<String> ans = new LinkedList<>();
poss(head, ans);
return ans;
}
public static void poss(Node head, Queue<String> ans) {
if (head == null) {
ans.add(null);
} else {
poss(head.left, ans);
poss(head.right, ans);
ans.add(String.valueOf(head.value));
}
}
public static Node buildByPreQueue(Queue<String> prelist) {
if (prelist == null || prelist.size() == 0) {
return null;
}
return preb(prelist);
}
public static Node preb(Queue<String> prelist) {
String value = prelist.poll();
if (value == null) {
return null;
}
Node head = new Node(Integer.valueOf(value));
head.left = preb(prelist);
head.right = preb(prelist);
return head;
}
public static Node buildByPosQueue(Queue<String> poslist) {
if (poslist == null || poslist.size() == 0) {
return null;
}
// 左右中 -> stack(中右左)
Stack<String> stack = new Stack<>();
while (!poslist.isEmpty()) {
stack.push(poslist.poll());
}
return posb(stack);
}
public static Node posb(Stack<String> posstack) {
String value = posstack.pop();
if (value == null) {
return null;
}
Node head = new Node(Integer.valueOf(value));
head.right = posb(posstack);
head.left = posb(posstack);
return head;
}
public static Queue<String> levelSerial(Node head) {
Queue<String> ans = new LinkedList<>();
if (head == null) {
ans.add(null);
} else {
ans.add(String.valueOf(head.value));
Queue<Node> queue = new LinkedList<Node>();
queue.add(head);
while (!queue.isEmpty()) {
head = queue.poll(); // head 父 子
if (head.left != null) {
ans.add(String.valueOf(head.left.value));
queue.add(head.left);
} else {
ans.add(null);
}
if (head.right != null) {
ans.add(String.valueOf(head.right.value));
queue.add(head.right);
} else {
ans.add(null);
}
}
}
return ans;
}
public static Node buildByLevelQueue(Queue<String> levelList) {
if (levelList == null || levelList.size() == 0) {
return null;
}
Node head = generateNode(levelList.poll());
Queue<Node> queue = new LinkedList<Node>();
if (head != null) {
queue.add(head);
}
Node node = null;
while (!queue.isEmpty()) {
node = queue.poll();
node.left = generateNode(levelList.poll());
node.right = generateNode(levelList.poll());
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
return head;
}
public static Node generateNode(String val) {
if (val == null) {
return null;
}
return new Node(Integer.valueOf(val));
}
// for test
public static Node generateRandomBST(int maxLevel, int maxValue) {
return generate(1, maxLevel, maxValue);
}
// for test
public static Node generate(int level, int maxLevel, int maxValue) {
if (level > maxLevel || Math.random() < 0.5) {
return null;
}
Node head = new Node((int) (Math.random() * maxValue));
head.left = generate(level + 1, maxLevel, maxValue);
head.right = generate(level + 1, maxLevel, maxValue);
return head;
}
// for test
public static boolean isSameValueStructure(Node head1, Node head2) {
if (head1 == null && head2 != null) {
return false;
}
if (head1 != null && head2 == null) {
return false;
}
if (head1 == null && head2 == null) {
return true;
}
if (head1.value != head2.value) {
return false;
}
return isSameValueStructure(head1.left, head2.left) && isSameValueStructure(head1.right, head2.right);
}
// for test
public static void printTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}
public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1, "^", len);
}
public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
public static void main(String[] args) {
int maxLevel = 5;
int maxValue = 100;
int testTimes = 1000000;
System.out.println("test begin");
for (int i = 0; i < testTimes; i++) {
Node head = generateRandomBST(maxLevel, maxValue);
Queue<String> pre = preSerial(head);
Queue<String> pos = posSerial(head);
Queue<String> level = levelSerial(head);
Node preBuild = buildByPreQueue(pre);
Node posBuild = buildByPosQueue(pos);
Node levelBuild = buildByLevelQueue(level);
if (!isSameValueStructure(preBuild, posBuild) || !isSameValueStructure(posBuild, levelBuild)) {
System.out.println("Oops!");
}
}
System.out.println("test finish!");
}
}到此這篇關(guān)于Java版本和C++版本的二叉樹序列化與反序列化的文章就介紹到這了,更多相關(guān)Java與C++二叉樹序列化 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了批量上傳Jar包到Maven私服的工具的方法，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-12-12
idea的更新版本比較特殊，需要重新安裝一下，這篇文章給大家介紹idea版本更新安裝教程詳解，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友參考下吧2020-11-11
數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存儲的方式，算法是數(shù)據(jù)計(jì)算的方式。所以在開發(fā)中，算法和數(shù)據(jù)結(jié)構(gòu)息息相關(guān)。本文為大家整理了Java中常見的查找與排序算法的實(shí)現(xiàn)，需要的可以參考一下2023-03-03
Java流程控制之循環(huán)結(jié)構(gòu)for,增強(qiáng)for循環(huán)
這篇文章主要介紹了Java流程控制之循環(huán)結(jié)構(gòu)for,增強(qiáng)for循環(huán)，for循環(huán)是編程語言中一種循環(huán)語句，而循環(huán)語句由循環(huán)體及循環(huán)的判定條件兩部分組成，其表達(dá)式為：for（單次表達(dá)式;條件表達(dá)式;末尾循環(huán)體）{中間循環(huán)體；}，下面我們倆看看文章內(nèi)容的詳細(xì)介紹2021-12-12
這篇文章主要為大家詳細(xì)介紹了java圖片壓縮工具類，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-02-02
原因分析IDEA導(dǎo)入Spring-kafka項(xiàng)目Gradle編譯失敗
這篇文章主要為大家介紹分析了IDEA導(dǎo)入Spring-kafka項(xiàng)目Gradle中編譯失敗原因及解決，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步2022-02-02
這篇文章主要介紹了springboot如何解決前后端分離時(shí)的跨域問題，幫助大家更好的理解和學(xué)習(xí)使用springboot，感興趣的朋友可以了解下2021-04-04
Java鏈表中元素刪除的實(shí)現(xiàn)方法詳解【只刪除一個(gè)元素情況】
這篇文章主要介紹了Java鏈表中元素刪除的實(shí)現(xiàn)方法,結(jié)合實(shí)例形式分析了java只刪除鏈表中一個(gè)元素的相關(guān)操作原理、實(shí)現(xiàn)方法與注意事項(xiàng),需要的朋友可以參考下2020-03-03
淺談Java虛擬機(jī)對內(nèi)部鎖的四種優(yōu)化方式
這篇文章主要介紹了淺談Java虛擬機(jī)對內(nèi)部鎖的四種優(yōu)化方式，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-10-10
Springboot入門案例及部署項(xiàng)目的詳細(xì)過程
Spring Boot是由Pivotal團(tuán)隊(duì)提供的全新框架，其設(shè)計(jì)目的是用來簡化新Spring應(yīng)用的初始搭建以及開發(fā)過程，本文給大家分享一個(gè)入門案例使用Springboot1.5.9搭建，具體配置部署過程跟隨小編一起看看吧2021-07-07