Serialization and Deserialization of a Binary Tree in Java

2025 年 5 月 7 日 | 阅读 10 分钟

序列化是将数据结构（如二叉树）转换为可以存储或传输的格式，然后稍后重新构造的过程。反序列化是相反的过程，将序列化格式转换回原始数据结构。

对于二叉树来说，关键挑战在于如何编码树的结构（包括值和不存在节点的 null 值），以便能够准确地重新构造它。

序列化

以特定的顺序遍历树（通常是前序遍历：根 → 左 → 右）。
将节点的值附加到一个字符串（或列表）中，对缺失的子节点使用特殊标记（例如“null”）。
使用分隔符（例如逗号）分隔值。

反序列化

读取序列化字符串或列表。
通过逐个读取值来重新创建二叉树，并考虑遍历顺序。
使用递归以正确的结构连接节点。

方法 1：使用“Null 标记”进行序列化和反序列化的前序遍历

算法

步骤 1. 序列化算法

输入：二叉树的根节点。

输出：表示树的序列化字符串。

步骤 1.1：初始化一个空的 StringBuilder 来存储序列化结果。

步骤 1.2：定义一个辅助函数 `serializeHelper(node, sb)`

如果节点为 null
将“null,” 附加到 StringBuilder。
从函数返回。
将当前节点的值后跟一个逗号 (,) 附加到 StringBuilder。
递归调用当前节点的左子节点的 `serializeHelper`。
递归调用当前节点的右子节点的 `serializeHelper`。
1. 调用 `serializeHelper(root, sb)` 开始从根节点遍历。
2. 将 StringBuilder 内容转换为字符串并返回。

步骤 2. 反序列化算法

输入：表示二叉树的序列化字符串。

输出：重构二叉树的根节点。

步骤 2.1：按逗号分隔符分割输入字符串，创建节点值列表。

步骤 2.2：定义一个辅助函数 `deserializeHelper(list)`

如果列表中的第一个元素是“null”
从列表中移除该元素。
返回 null。
将列表的第一个元素转换为整数，并用该值创建一个新的 TreeNode。
从列表中移除该元素。
递归调用 `deserializeHelper` 来构造当前节点的左子节点。
递归调用 `deserializeHelper` 来构造当前节点的右子节点。
返回构造好的 TreeNode。
调用 `deserializeHelper(list)` 来重构树并返回根节点。

步骤 3. 可选的树打印算法

输入：二叉树的根节点。

输出：树的层序表示，用于调试或可视化。

步骤 3.1：初始化一个队列，并将根节点添加到其中。

步骤 3.2：当队列不为空时

出队队首节点。
如果节点为 null，则打印“null”。
否则，打印节点的值。
将节点的左子节点和右子节点添加到队列。

步骤 3.3：处理完所有节点后停止。

步骤 3.4：清理和优化树的表示

完成层序遍历并打印节点值后，生成的输出可能包含不必要的占位符，例如遍历末尾的“null”值，这些值代表非存在的子节点。为了使树的表示更清晰、更简洁，可以移除这些多余的值。

识别不必要的 Null 值：检查打印的输出，找出末尾的“null”值。这些是树底层不存在的节点的占位符。

移除冗余 Null 值：从输出末尾开始，移除这些末尾的“null”条目，直到遇到最后一个有意义的节点（非 null 值）。这样可以确保表示反映树的实际结构。

组织和呈现输出：将清理后的值以易于阅读的格式组织起来。例如

为了简单起见，使用一个由逗号分隔的单行。

或者，按层级对值进行分组，以更清晰地显示树结构。

增强可视化：如果需要用于调试，可以添加每个层级的简短描述，或在对应于每个树层级的节点组之间提供视觉间隔。

文件名：BinaryTreeSerializer.java

import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}
public class BinaryTreeSerializer {
    // Serialize a binary tree to a string
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }
    private void serializeHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("null,");
            return;
        }
        sb.append(node.val).append(",");
        serializeHelper(node.left, sb);
        serializeHelper(node.right, sb);
    }
    // Deserialize a string back to a binary tree
    public TreeNode deserialize(String data) {
        String[] values = data.split(",");
        List<String> list = new LinkedList<>(Arrays.asList(values));
        return deserializeHelper(list);
    }
    private TreeNode deserializeHelper(List<String> list) {
        if (list.get(0).equals("null")) {
            list.remove(0);
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(list.remove(0)));
        node.left = deserializeHelper(list);
        node.right = deserializeHelper(list);
        return node;
    }
    // Print tree in a readable way (Optional)
    public void printTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            if (current == null) {
                System.out.print("null ");
            } else {
                System.out.print(current.val + " ");
                queue.add(current.left);
                queue.add(current.right);
            }
        }
        System.out.println();
    }
    // Test the code
    public static void main(String[] args) {
        BinaryTreeSerializer serializer = new BinaryTreeSerializer();
        // Create a sample tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);
        // Serialize the tree
        String serializedData = serializer.serialize(root);
        System.out.println("Serialized Tree: " + serializedData);
        // Deserialize the string back to a tree
        TreeNode deserializedRoot = serializer.deserialize(serializedData);
        System.out.print("Deserialized Tree (Level-order): ");
        serializer.printTree(deserializedRoot);
    }
}   

输出

 
Serialized Tree: 1,2,null,null,3,4,null,null,5,null,null,
Deserialized Tree (Level-order): 1 2 3 null null 4 5 null null null null

时间和空间复杂度分析

时间复杂度

序列化

在一次前序遍历中恰好访问每个节点一次。
O(n)，其中 n 是树中的节点数。

反序列化

在构造树时处理每个节点一次。
O(n)。

空间复杂度

序列化

使用 StringBuilder 来存储序列化输出。
结果字符串的空间与节点数及其值成正比。
O(n)。

反序列化

使用列表来存储分割后的字符串值和递归栈。
在最坏的情况下，递归栈的深度可以达到树的高度。
列表为 O(n)，递归为 O(h)，其中 h 是树的高度。
总空间：O(n)。

方法 2：用于序列化和反序列化的层序遍历

算法

序列化算法

步骤 1：初始化：检查 Null 树：在开始序列化过程之前，首先检查树是否为 null。如果树为空（即根节点为 null），则直接返回“null”作为序列化输出。

步骤 2：创建 StringBuilder：为了存储序列化数据，初始化一个 StringBuilder。这将使我们能够高效地将值附加到序列化字符串。

步骤 3：层序遍历：用于遍历的队列：为了按层序（广度优先）遍历树，我们使用队列。队列遵循先进先出（FIFO）原则，这对于层序遍历非常理想。

入队根节点：首先将根节点添加到队列。

遍历树：当队列不为空时，重复以下步骤

出队一个节点：从队列中移除队首节点。将处理此节点。

步骤 4：检查 Null 节点：如果当前节点为 null，则将“null,” 附加到 StringBuilder。这表示树中该位置缺少一个节点。

添加非 Null 节点的值：如果节点不为 null，则将节点的值后跟一个逗号，附加到 StringBuilder。

处理完节点后，将其左子节点和右子节点添加到队列（无论它们是 null 还是非 null）。这确保我们在序列化输出中正确地表示所有子节点。

步骤 4.1：修剪末尾的逗号：一旦所有节点（包括表示缺失节点的 null 节点）都已处理并添加到 StringBuilder 中，序列化字符串的末尾可能会有一个额外的末尾逗号。为了清理结果，移除末尾的逗号。这确保最终字符串格式正确，没有不必要的字符。

步骤 5：完成序列化：继续此层序遍历，直到处理完所有节点，包括表示缺失子节点的 null 节点。遍历完成后，将 StringBuilder 的内容转换为字符串并返回，作为树的序列化表示。

反序列化算法

步骤 1：初始设置：检查 Null 输入：首先检查输入字符串是否为“null”。如果是，则返回 null，因为这表示一个空树。

步骤 1.1：分割输入字符串：按逗号分隔符分割输入字符串，以获取节点值列表。此列表将用于逐个节点地重构树。

步骤 2：重构树：创建根节点：使用列表中的第一个值来创建根节点。如果该值为“null”，则表示树为空，应返回 null。

步骤 3：用于树构造的队列：初始化一个队列并将根节点添加到其中。此队列将帮助逐层构建树，类似于序列化中使用的队列。

步骤 3.1：构建树：逐层节点构造：当队列中有节点时，重复以下步骤

出队一个节点：从队列中移除队首节点。分配左子节点：从列表中取下一个值并检查

如果该值为“null”，则当前节点的左子节点为 null。否则，用当前值创建一个新节点并将其添加到队列。

步骤 4：分配右子节点：同样，从列表中取下一个值并检查

如果该值为“null”，则当前节点的右子节点为 null。否则，用当前值创建一个新节点并将其添加到队列。

步骤 5：返回重构的树：一旦列表中的所有值都已处理完毕，并且整个树已重构，则返回根节点。该节点表示已完全重构的二叉树。

可选的树打印算法

此步骤是可选的，但有助于调试或可视化树结构。

步骤 1：用于打印的层序遍历：使用队列按层序遍历树。这意味着从上到下，从左到右访问节点。

打印节点值：对于每个节点

如果节点为 null，则打印“null”。

如果节点不为 null，则打印其值。

步骤 2：将子节点添加到队列：打印当前节点后，将其左子节点和右子节点添加到队列。如果它们是 null，我们仍然会添加它们，以确保正确表示缺失的子节点。

`printTree` 函数将继续执行，直到所有节点都被处理，并将显示树的层序表示，这对于可视化非常有用。

步骤 3：后遍历清理（人工解释）

在按层级遍历完整个树后，打印的表示在末尾可能会包含额外的“null”值。这些“null”值通常代表树的最后一级中不存在的子节点，对于理解其结构不是必需的。为了清理输出

识别末尾的 Null 值：检查遍历过程中收集的值列表的最后一个节点。这些将是标记为“null”的节点。

移除冗余 Null 值：从列表末尾开始反向工作，删除连续的“null”值，直到遇到一个具有实际值的节点。

结果：这确保树的输出不包含不必要的占位符，使其更简洁易读。

步骤 4：格式化并打印最终输出

在从层序遍历中清理了不必要的末尾“null”值后，以清晰有序的格式呈现树结构，以便于可视化或调试。

合并值：使用清理后的节点值列表创建一个单一的字符串表示形式的树，并用逗号分隔。例如，[1,2,3,null,4]。

添加括号：将字符串放在方括号 ([]) 中，使其在视觉上与编码平台或讨论中的典型树表示一致。

输出树：打印或返回格式化的字符串。此最终表示提供了树结构的易于理解的概述，其中缺失的节点由“null”表示。

文件名：TreeNode.java

import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
TreeNode(int val) {
        this.val = val;
    }
}
public class BinaryTreeLevelOrderSerializer {
// Serialize a binary tree using level-order traversal
    public String serialize(TreeNode root) {
        if (root == null) return "null";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            if (current == null) {
                sb.append("null,");
            } else {
                sb.append(current.val).append(",");
                queue.add(current.left);
                queue.add(current.right);
            }
        }
        return sb.toString();
    }
// Deserialize a string back to a binary tree
    public TreeNode deserialize(String data) {
        if (data.equals("null")) return null;
String[] values = data.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        queue.add(root);
int i = 1; // Pointer for array elements
        while (!queue.isEmpty() && i < values.length) {
            TreeNode current = queue.poll();
            // Process left child
            if (!values[i].equals("null")) {
                current.left = new TreeNode(Integer.parseInt(values[i]));
                queue.add(current.left);
            }
            i++;
     // Process right child
            if (i < values.length && !values[i].equals("null")) {
                current.right = new TreeNode(Integer.parseInt(values[i]));
                queue.add(current.right);
            }
            i++;
        }
        return root;
    }
    // Test the implementation
    public static void main(String[] args) {
        BinaryTreeLevelOrderSerializer serializer = new BinaryTreeLevelOrderSerializer();
// Create a sample tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);
// Serialize the tree
        String serializedData = serializer.serialize(root);
        System.out.println("Serialized Tree: " + serializedData);
// Deserialize the string back to a tree
        TreeNode deserializedRoot = serializer.deserialize(serializedData);
        System.out.print("Deserialized Tree (Level-order): ");
        serializer.printTree(deserializedRoot);
    }
// Optional: Print tree in level-order for debugging
    public void printTree(TreeNode root) {
        if (root == null) {
            System.out.println("null");
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            if (current == null) {
                System.out.print("null ");
            } else {
                System.out.print(current.val + " ");
                queue.add(current.left);
                queue.add(current.right);
            }
        }
        System.out.println();
    }
}   

输出

 
Serialized Tree: 1,2,null,null,3,4,null,null,5,null,null,
Deserialized Tree (Level-order): 1 2 3 null null 4 5 null null null null.

复杂度分析

时间复杂度

序列化和反序列化的时间复杂度均为 O(n)，其中 n 是树中的节点数。序列化涉及访问每个节点一次，而反序列化在列表中处理每个节点一次以重构树，确保两者都是线性时间。

空间复杂度

序列化的空间复杂度为 O(n)，因为需要存储序列化字符串，其中 n 是节点数。反序列化需要 O(n) 的空间来存储包含节点值的列表，以及 O(h) 的空间用于递归栈，其中 h 是树的高度，因此总体为 O(n)。

下一个主题Java 中的 Pell 数

Serialization and Deserialization of a Binary Tree in Java

序列化

反序列化

方法 1：使用“Null 标记”进行序列化和反序列化的前序遍历

算法

时间和空间复杂度分析

方法 2：用于序列化和反序列化的层序遍历

算法

序列化算法

反序列化算法

可选的树打印算法

复杂度分析

时间复杂度

空间复杂度

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Serialization and Deserialization of a Binary Tree in Java

序列化

反序列化

方法 1：使用“Null 标记”进行序列化和反序列化的前序遍历

算法

时间和空间复杂度分析

方法 2：用于序列化和反序列化的层序遍历

算法

序列化算法

反序列化算法

可选的树打印算法

复杂度分析

时间复杂度

空间复杂度

相关帖子

如何在 Java 中将登录页面连接到数据库

Java public keyword

Java 中的引用变量是什么

哪个组件负责运行 Java 程序

Java 程序生成二进制数

Java 中 ToIntFunction 接口及示例

Java 中的架构中立是什么

Pell Number in Java

Java 静态类型与动态类型

Which Package is Imported by Default in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器