当前位置：首页 > news >正文

二叉树的序列化与反序列化详解

news 2026/5/21 19:19:51

一、什么是序列化与反序列化？

在计算机中，很多数据结构都是存在于内存里的，比如链表、二叉树、图等。

这些结构在程序运行时很好使用，但如果我们想把它们：

保存到文件中
存入数据库
通过网络发送给另一台电脑
程序退出后下次还能恢复

就不能直接保存内存中的指针关系。

这时就需要用到序列化和反序列化。

二、序列化的概念

序列化，就是把一个对象或数据结构转换成一种可以存储、传输的格式。

比如一棵二叉树：

1 / \ 2 3 / \ 4 5

它在内存中是由很多节点和指针连接起来的。

但是指针地址不能直接保存，因为程序重新运行后，内存地址会改变。

所以我们需要把这棵树转换成字符串，例如：

1,2,#,#,3,4,#,#,5,#,#

这个字符串就可以保存到文件中，也可以通过网络传输。

这个过程就叫做序列化。

三、反序列化的概念

反序列化，就是把序列化后的字符串重新还原成原来的数据结构。

例如我们拿到字符串：

1,2,#,#,3,4,#,#,5,#,#

可以重新构造出原来的二叉树：

1 / \ 2 3 / \ 4 5

这个过程就叫做反序列化。

四、为什么二叉树需要序列化？

普通数组的序列化很简单，例如：

[1, 2, 3, 4, 5]

可以直接转换成：

"1,2,3,4,5"

但是二叉树比较特殊。

二叉树不仅有节点值，还有结构关系：

1 / 2

和

1 \ 2

这两棵树的节点值都是1和2，但结构完全不同。

所以序列化二叉树时，不能只保存节点值，还必须保存空节点的位置。

五、为什么要记录空节点？

假设我们只用前序遍历保存节点值。

下面这棵树：

1 / 2

前序遍历结果是：

1,2

而下面这棵树：

1 \ 2

前序遍历结果也是：

1,2

这样就无法判断2是1的左孩子还是右孩子。

所以我们需要用一个特殊符号表示空节点，例如#。

第一棵树可以序列化成：

1,2,#,#,#

第二棵树可以序列化成：

1,#,2,#,#

这样结构就明确了。

六、题目分析：LeetCode 297

题目要求

给定一棵二叉树，要求我们设计两个函数：

string serialize(TreeNode* root); TreeNode* deserialize(string data);

其中：

serialize：把二叉树转换成字符串
deserialize：把字符串重新还原成二叉树

题目不要求必须使用 LeetCode 官方格式，只要能够保证：

deserialize(serialize(root))

可以还原原来的树结构即可。

七、解决思路：前序遍历 + 空节点标记

二叉树常见的遍历方式有：

前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
层序遍历：按层遍历

这道题可以用很多方式实现。

这里我们使用最经典的一种方法：

前序遍历 + 空节点标记

1. 序列化过程

按照前序遍历的顺序：

根节点 -> 左子树 -> 右子树

如果当前节点为空，就记录#。

例如二叉树：

1 / \ 2 3 / \ 4 5

前序序列化过程如下：

1 2 # # 3 4 # # 5 # #

最终得到字符串：

1,2,#,#,3,4,#,#,5,#,#

2. 反序列化过程

反序列化时，也按照前序顺序读取字符串。

遇到数字，就创建节点。

遇到#，说明当前位置是空节点，返回nullptr。

例如字符串：

1,2,#,#,3,4,#,#,5,#,#

解析过程如下：

1 作为根节点 2 作为 1 的左孩子 # 表示 2 的左孩子为空 # 表示 2 的右孩子为空 3 作为 1 的右孩子 4 作为 3 的左孩子 # 表示 4 的左孩子为空 # 表示 4 的右孩子为空 5 作为 3 的右孩子 # 表示 5 的左孩子为空 # 表示 5 的右孩子为空

这样就能完整还原原来的二叉树。

八、C++ 完整代码

#include <iostream> #include <sstream> #include <string> using namespace std; // LeetCode 中已经定义好了 TreeNode，这里写出来方便理解 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; class Codec { public: // 序列化：将二叉树转换成字符串 string serialize(TreeNode* root) { string result; dfsSerialize(root, result); return result; } // 反序列化：将字符串重新转换成二叉树 TreeNode* deserialize(string data) { stringstream ss(data); return dfsDeserialize(ss); } private: // 前序遍历序列化 void dfsSerialize(TreeNode* root, string& result) { if (root == nullptr) { result += "#,"; return; } // 先保存当前节点 result += to_string(root->val) + ","; // 再保存左子树 dfsSerialize(root->left, result); // 最后保存右子树 dfsSerialize(root->right, result); } // 前序遍历反序列化 TreeNode* dfsDeserialize(stringstream& ss) { string token; getline(ss, token, ','); // 如果是空节点标记，返回 nullptr if (token == "#") { return nullptr; } // 创建当前节点 TreeNode* root = new TreeNode(stoi(token)); // 递归构造左子树 root->left = dfsDeserialize(ss); // 递归构造右子树 root->right = dfsDeserialize(ss); return root; } };

九、代码详细解释

1. serialize 函数

string serialize(TreeNode* root) { string result; dfsSerialize(root, result); return result; }

这个函数负责把二叉树转换成字符串。

真正的递归逻辑在dfsSerialize中完成。

2. dfsSerialize 函数

void dfsSerialize(TreeNode* root, string& result) { if (root == nullptr) { result += "#,"; return; } result += to_string(root->val) + ","; dfsSerialize(root->left, result); dfsSerialize(root->right, result); }

这个函数使用前序遍历：

根节点 -> 左子树 -> 右子树

如果当前节点为空，就加入：

#,

如果当前节点不为空，就加入节点值。

例如节点值是3，就加入：

3,

3. deserialize 函数

TreeNode* deserialize(string data) { stringstream ss(data); return dfsDeserialize(ss); }

这个函数把字符串放入stringstream中，方便我们按照逗号逐个读取。

例如字符串：

1,2,#,#,3,#,#,

每次读取一个片段：

1 2 # # 3 # #

4. dfsDeserialize 函数

TreeNode* dfsDeserialize(stringstream& ss) { string token; getline(ss, token, ','); if (token == "#") { return nullptr; } TreeNode* root = new TreeNode(stoi(token)); root->left = dfsDeserialize(ss); root->right = dfsDeserialize(ss); return root; }

这个函数的核心思想是：