数据结构之二叉树序列化/反序列化详解与示例（C, C++）

🕗 发布于 2024-07-19 08:58 数据结构 c语言 c++

文章目录

一、二叉树的基本概念与特性
- 1.1 二叉树的定义
- 1.2 二叉树的特性
二、序列化与反序列化的定义及方法
三、序列化过程的代码示例
四、反序列化过程的代码示例
五、总结与反思
- 5.1 总结
- 5.2 反思

在计算机科学中，二叉树是一种基本的数据结构，广泛应用于各种算法和应用中。二叉树的序列化和反序列化是将二叉树结构转换为字符串形式，以便存储或传输，然后再从字符串形式恢复为二叉树结构的过程。本文将详细介绍二叉树的基本概念、序列化与反序列化的定义及方法，并提供C++代码示例。

一、二叉树的基本概念与特性

1.1 二叉树的定义

二叉树是一种树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树的根节点没有父节点，而其他节点有一个父节点。

1.2 二叉树的特性

有序性：二叉树的左子节点值小于或等于父节点值，右子节点值大于或等于父节点值。
层次性：二叉树的节点按照层次排列，根节点位于第一层，其子节点位于第二层，依此类推。
递归性：二叉树可以递归地定义为一个节点和两个子树，其中每个子树本身也是一个二叉树。

二、序列化与反序列化的定义及方法

2.1 序列化的定义

序列化是将对象的状态信息转换为可以存储或传输的形式的过程。在二叉树的序列化中，通常将二叉树转换为一个字符串，以便存储或通过网络传输。

2.2 反序列化的定义

反序列化是将序列化后的数据恢复为原始对象的过程。在二叉树的反序列化中，将字符串形式的数据转换回二叉树结构。

2.3 序列化方法

二叉树的序列化方法有多种，常见的有：

前序遍历：先访问根节点，然后访问左子树，最后访问右子树。
中序遍历：先访问左子树，然后访问根节点，最后访问右子树。
后序遍历：先访问左子树，然后访问右子树，最后访问根节点。

2.4 反序列化方法

反序列化通常基于序列化时使用的方法，例如：

前序遍历反序列化：根据前序遍历的序列重建二叉树。
中序遍历反序列化：结合前序遍历和中序遍历的序列重建二叉树。
后序遍历反序列化：根据后序遍历的序列重建二叉树。

三、序列化过程的代码示例

3.1 前序遍历序列化

以下是一个使用前序遍历进行二叉树序列化的C代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 辅助函数，将整型值转换为字符串，并添加到序列化字符串中
void serializeInt(char **str, int val) {
    char temp[50];
    sprintf(temp, "%d,", val);
    strcat(*str, temp);
}

// 前序遍历序列化
void serialize(TreeNode* root, char **str) {
    if (root == NULL) {
        strcat(*str, "#,");
        return;
    }
    serializeInt(str, root->val);
    serialize(root->left, str);
    serialize(root->right, str);
}

// 创建新节点
TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    char *serializedStr = (char*)malloc(1024 * sizeof(char));
    strcpy(serializedStr, "");
    serialize(root, &serializedStr);
    printf("Serialized Tree: %s\n", serializedStr);

    free(serializedStr);
    // 注意：这里没有释放树节点，实际使用时需要确保释放所有分配的内存

    return 0;
}

以下是一个使用前序遍历进行二叉树序列化的C++代码示例：

#include <iostream>
#include <string>
#include <queue>
#include <sstream>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

std::string serialize(TreeNode* root) {
    std::ostringstream oss;
    if (root == NULL) {
        oss << "# ";
        return oss.str();
    }
    oss << root->val << " ";
    oss << serialize(root->left);
    oss << serialize(root->right);
    return oss.str();
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    std::string serialized = serialize(root);
    std::cout << "Serialized binary tree: " << serialized << std::endl;

    return 0;
}

代码解释
TreeNode结构：定义二叉树的节点结构，包含节点值和左右子节点指针。
serialize函数：使用递归实现前序遍历序列化，遇到空节点输出"#"。

四、反序列化过程的代码示例

4.1 前序遍历反序列化
以下是一个使用前序遍历反序列化的C代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 辅助函数，用于从字符串中解析出下一个整数值
int deserializeInt(char **str) {
    char *endptr;
    int val = strtol(*str, &endptr, 10);
    *str = endptr + 1; // 跳过逗号
    return val;
}

// 前序遍历反序列化
TreeNode* deserialize(char **str) {
    if (**str == '#') {
        (*str)++; // 跳过井号
        (*str)++; // 跳过逗号
        return NULL;
    }
    TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = deserializeInt(str);
    root->left = deserialize(str);
    root->right = deserialize(str);
    return root;
}

以下是一个使用前序遍历反序列化的C++代码示例：

#include <iostream>
#include <sstream>
#include <queue>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* deserialize(std::string data) {
    std::istringstream iss(data);
    return deserializeHelper(iss);
}

TreeNode* deserializeHelper(std::istringstream& iss) {
    char ch;
    iss >> ch;
    if (ch == '#') {
        return NULL;
    }
    int val = ch - '0';
    TreeNode* node = new TreeNode(val);
    node->left = deserializeHelper(iss);
    node->right = deserializeHelper(iss);
    return node;
}

int main() {
    std::string data = "1 2 4 # # 5 # # 3 # #";
    TreeNode* root = deserialize(data);
    
    // 打印重建的二叉树
    std::cout << "Deserialized binary tree: ";
    printTree(root);

    return 0;
}

void printTree(TreeNode* node) {
    if (node == NULL) {
        std::cout << "# ";
        return;
    }
    std::cout << node->val << " ";
    printTree(node->left);
    printTree(node->right);
}

代码解释
deserialize函数：从字符串中读取数据并调用辅助函数进行反序列化。
deserializeHelper函数：使用递归实现前序遍历反序列化，遇到"#"时返回NULL。

五、总结与反思

在本文中，我们探讨了二叉树的基本概念、序列化与反序列化的定义及方法，并提供了C++代码示例。通过这些示例，我们可以看到序列化和反序列化在实际应用中的重要性，尤其是在需要存储或传输二叉树数据时。

5.1 总结

二叉树：是一种基本的数据结构，具有有序性和层次性。
序列化：将二叉树转换为字符串形式，便于存储或传输。
反序列化：将字符串形式的数据恢复为二叉树结构。

5.2 反思

效率问题：序列化和反序列化的过程可能会影响程序的运行效率，特别是在处理大型二叉树时。
数据一致性：在序列化和反序列化过程中，需要确保数据的一致性和准确性。
应用场景：序列化和反序列化在网络通信、数据存储等领域有广泛的应用。

通过本文的学习，希望读者能够更好地理解和掌握二叉树的序列化与反序列化技术，并在实际项目中灵活应用。

原文地址：https://blog.csdn.net/qq_35320456/article/details/140529582

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：NLP教程：1 词袋模型和TFIDF模型
下一篇：TikTok内嵌跨境商城全开源_搭建教程/前端uniapp+后端源码

【go从零单排】上下文（context）
在 Go 语言中，上下文（context）是一个重要的概念，主要用于管理请求的生命周期、传递取消信号、超时控制以及传递请求范围内的值。上下文通常与并发编程相关，尤其是在处理 HTTP 请求和其他 I/
阅读更多2024-11-15
Ubuntu 20.04 配置开发环境(持续更新)
搜狗输入法不能显示中文。
阅读更多2024-11-15
在ubuntu上安装ubuntu22.04并ros2 humble版本的docker容器记录
"registry-mirrors" : ["https://你的.mirror.swr.myhuaweicloud.com"],4、已经打包了ubuntu22
阅读更多2024-11-15
如何在 Ubuntu 22.04 上安装 ownCloud
ownCloud 是一个开源的个人云存储平台，它允许用户在本地服务器上存储和同步文件，提供了一个类似于 Dropbox 或 Google Drive 的服务，但是更加注重隐私和数据控制。文件存储：用户
阅读更多2024-11-15
idea 删除本地分支后，弹窗 delete tracked brank
在 IntelliJ IDEA 中，删除本地分支后弹出 “Delete tracked branch” 的提示，这表示删除的是一个跟踪分支（tracked branch）。具体来说，当前删除的本地分
阅读更多2024-11-15
「JVM详解」
JVM：全称 Java Virtual Machine，即 Java 虚拟机，一种规范，本身是一个虚拟计算机，直接和操作系统进行交互，与硬件不直接交互，而操作系统可以帮我们完成和硬件进行交互的工作
阅读更多2024-11-15
WPF中Prism框架的简单使用
自动匹配导入4.写Login.XAML代码和LoginViewModel代码LoginViewModel如下：5.创建其他的UserControl 并学好MainWindow.XAML和MainWin
阅读更多2024-11-15
Linux——GPIO输入输出裸机实验
在程序启动时，BSS段会被清零，并且其大小会被计算到程序的总内存占用中，尽管它在磁盘上的表示可能非常小或甚至没有。在程序启动时，BSS段会被清零，并且其大小会被计算到程序的总内存占用中，尽管它在磁盘上
阅读更多2024-11-15
planRAG运行记录
运行planRAG过程记录
阅读更多2024-11-15
vue面试题8|[2024-11-14]
vue面试题
阅读更多2024-11-15