C++实现类似Java的字符串分割功能以及在二叉树序列化与反序列化中的应用

在搞二叉树序列化和反序列化这活儿的时候，C++和Java比起来，就少了个像Java字符串split那样能直接分割字符串的函数，属实有点不方便。不过别慌，咱用流的思路，也能模拟出这个功能。实现这个功能，主要得用到<sstream>和<string>这俩头文件。

<string>里的getline函数挺好用的，它不仅能读取整行输入，还有个构造函数，能从流里按你指定的任意字符把内容分割成一个个小片段（token）。std::istream &std::getline<char, std::char_traits<char>, std::allocator<char>>(std::istream &Istr, std::string &_Str, char _Delim)，这个函数还有4个重载，要是想深入了解，可以去搜索一下。

<sstream>里的istringstream也很关键，它能把字符串包装成输入流。就像这样：

程序员导航

优网导航旗下整合全网优质开发资源，一站式IT编程学习与工具大全网站

立即访问

istringstream stream(str); // 将字符串包装为输入流

有了这俩“神器”，咱们就能动手实现类似Javasplit的功能啦，代码如下：

class serializationAndDeserialiation {
public:
    class Node {
    public:
        int value;
        Node* left;
        Node* right;

        Node(int data) : value(data), left(nullptr), right(nullptr) {};
    };

    // 前序遍历序列化二叉树
    string serialByPre(Node* head) {
        if (head == nullptr) {
            return "#_";
        }
        string res = to_string(head->value) + "_";
        res += serialByPre(head->left);
        res += serialByPre(head->right);
        return res;
    }

    // 前序遍历反序列化二叉树，这里用到了模拟的split功能
    Node* deserialByPre(string prestr) {
        // C++实现split
        vector<string> tokens;
        istringstream stream(prestr); // 将字符串包装为输入流
        string token;

        // 按分隔符'_'读取
        while (getline(stream, token, '_')) {
            tokens.push_back(token);
        }
        return deserialPre(tokens);
    }

    // 辅助反序列化的递归函数
    Node* deserialPre(vector<string>tokens) {
        if (tokens.empty()) {
            return nullptr;
        }
        string value = tokens.front();
        tokens.erase(tokens.begin());
        if (value == "#") {
            return nullptr;
        }
        // 注意这里用new动态分配内存创建节点
        Node* head = new Node(stoi(value));
        head->left = deserialPre(tokens);
        head->right = deserialPre(tokens);
        return head;
    }
};

代码里的serialByPre函数，是用前序遍历的方式序列化二叉树，要是节点为空，就返回"#_"；不为空的话，就把节点值转成字符串，再加上"_"，然后递归处理左子树和右子树。

deserialByPre函数则是负责反序列化。先把输入的字符串包装成输入流，再用getline按"_"把字符串分割开，存到tokens这个vector里，最后调用deserialPre进行递归反序列化。

deserialPre函数是反序列化的核心递归函数，它从tokens里取出节点值，要是值为"#"或者tokens为空，就返回nullptr；否则就创建新节点，继续递归构建左右子树。