Java与C++实现二叉树序列化与反序列化的通用方法

序列化原理与必要性

二叉树是一种基于节点的引用结构，存储在内存中。当进程结束或断电时，这些数据会丢失。为了保存这种层次结构，需要将二叉树转换为线性序列存储到硬盘或传输到网络中，这个过程称为序列化；反之，从字符串恢复出原始树结构的过程称为反序列化。

核心难点：仅凭节点的访问顺序无法唯一确定树的结构，例如两棵形状不同但叶子节点相同的树可能产生相同的非空节点序列。因此，必须将空指针（NULL）视为有效节点参与遍历，并用特殊字符（如 # 或 null）表示，同时使用分隔符隔开每个元素，以防止整数位数不同造成的解析歧义（如 “1, 2” 可能被误读为 “12”）。

策略一：先序方式序列化和反序列化

先序遍历遵循 根 → 左 → 右 的顺序。序列化时依次记录节点值，遇到空节点记录占位符。反序列化时，因为根节点总是序列的第一个元素，我们可以根据这个顺序递归地重建左右子树。

第1步：定义节点结构与辅助函数

首先建立基础的树节点类。在C++中使用指针操作，Java中使用对象引用。注意Java版代码中将空节点显式添加 null 字符串以便区分。

// C++ 节点定义
class TreeNode {
public:
    int value;
    TreeNode *lchild;
    TreeNode *rchild;
    TreeNode(int data) : value(data), lchild(nullptr), rchild(nullptr) {}
};

// Java 节点定义
public static class Node {
    public int value;
    public Node left;
    public Node right;
    public Node(int data) { this.value = data; }

第2步：实现先序序列化

目的：生成唯一的先序字符串队列。

1. 入口： 根节点与用于存储结果的队列/列表。
2. 动作： 若节点为空，推入占位符；否则推入节点值的字符串形式，并递归调用左子树和右子树。

// C++ 先序序列化
void preS(TreeNode *root, queue<string> &ans) {
    if (root == nullptr) 
        ans.push("#");
    else {
        ans.push(to_string(root->value));
        preS(root->lchild, ans);
        preS(root->rchild, ans);
    }
}

第3步：实现先序反序列化

目的：根据队列前端数据重构树。

1. 入口： 序列化产生的队列。
2. 动作： 取出队首值。如果是占位符，返回空指针；否则创建新节点，并递归构建其左子节点和右子节点（递归过程中会自动消耗队列中的后续元素）。

// C++ 先序反序列化
TreeNode *buildByPreQueue(queue<string> &prelist) {
    if (prelist.empty()) return nullptr;
    string val = prelist.front(); prelist.pop();
    if (val == "#") return nullptr;
    TreeNode *node = new TreeNode(stoi(val));
    node->lchild = buildByPreQueue(prelist); // 递归消耗左侧
    node->rchild = buildByPreQueue(prelist); // 递归消耗右侧
    return node;
}

策略二：层序方式序列化和反序列化

层序遍历（BFS）通常配合队列使用，按照从上到下、从左到右的顺序访问节点。这种方式能直观反映树的广度层级。

第1步：层序序列化

利用辅助队列进行广度优先搜索。每次从队列取出当前节点，将其左右子节点的值（或占位符）加入结果队列，并将有效的子节点加入处理队列。

// C++ 层序序列化
queue<string> levelSerial(TreeNode *root) {
    queue<string> ans;
    if (!root) { ans.push("#"); return ans; }
    ans.push(to_string(root->value));
    queue<TreeNode*> que; que.push(root);
    while (!que.empty()) {
        TreeNode *cur = que.front(); que.pop();
        cur->lchild ? (ans.push(to_string(cur->lchild->value)), que.push(cur->lchild)) : ans.push("#");
        cur->rchild ? (ans.push(to_string(cur->rchild->value)), que.push(cur->rchild)) : ans.push("#");
    }
    return ans;
}

第2步：层序反序列化

采用“双指针”或同步队列的思想：一个队列存放已确定的父节点，另一个队列（或迭代器）提供子节点数据。

1. 入口： 层序序列列。
2. 动作： 弹出第一个元素建树头。随后循环处理已建成的节点：依次从输入队列取两个值分别作为左、右孩子，若非空则加入待处理队列。

// C++ 层序反序列化
TreeNode *buildByLevelQueue(queue<string> &levelList) {
    if (levelList.empty()) return nullptr;
    TreeNode *root = generateTreeNode(levelList.front()); levelList.pop();
    queue<TreeNode*> que;
    root ? que.push(root) : nullptr;

    while (!que.empty()) {
        TreeNode *cur = que.front(); que.pop();
        cur->lchild = generateTreeNode(levelList.front()); levelList.pop();
        cur->rchild = generateTreeNode(levelList.front()); levelList.pop();
        cur->lchild ? que.push(cur->lchild) : nullptr;
        cur->rchild ? que.push(cur->rchild) : nullptr;
    }
    return root;
}

关于中序遍历的局限

虽然理论上可以使用中序遍历（左 → 根 → 右），但由于根节点位于中间，若不预先知道分割点或深度信息，很难直接从单一的中序序列中唯一确定左右子树的边界。相比之下，先序和后序序列天然包含了明确的根节点位置（前/后），更适合直接转化为重建逻辑。

总结

通过以上分析可知，二叉树的序列化与反序列化是数据结构与算法中的经典场景。关键在于引入占位符明确空节点位置。上述提供的C++与Java实现覆盖了最常见的先序与层序方案，在实际工程中（如LeetCode解题或分布式系统状态存储），层序方案因符合视觉直觉且便于按层扩展而常被选用。以上就是Java与C++版本二叉树序列化与反序列化的详细内容，更多关于C++与Java树结构算法的资料请关注本站其它相关文章！