C++序列化与反序列化二叉树

C++序列化与反序列化二叉树

首先我们定义树节点的数据结构

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

序列化函数

inline std::string serialize(TreeNode* root) {
  if (root == nullptr) {
    return "null";
  }
  std::vector<TreeNode*> queue;
  std::vector<std::vector<std::string>> result;
  queue.push_back(root);
  int height = 0;
  while (!queue.empty() &&
    !std::all_of(queue.begin(), queue.end(),
      [](const TreeNode* node) { return node == nullptr; })) {
    std::vector<std::string> temp;
    int count = static_cast<int>(std::pow(2, height));
    while (count-- != 0) {
      auto front = queue.front();
      queue.erase(queue.begin());
      if (front == nullptr) {
        temp.push_back("null");
        queue.push_back(nullptr);
        queue.push_back(nullptr);
      }
      else {
        temp.push_back(std::to_string(front->val));
        queue.push_back(front->left);
        queue.push_back(front->right);
      }
    }
    result.push_back(temp);
    ++height;
  }

  std::string str = "[";
  /// 组装字符串
  for (auto& it : result) {
    for (auto& it1 : it) {
      str += it1 + ",";
    }
  }
  if (str.back() == ',') {
    str.erase(std::prev(str.end()));
    str += "]";
  }
  return str;
}

反序列化函数

inline void split(const std::string& s, std::vector<std::string>& tokens,
  const std::string& delimiters = " ") {
  std::string::size_type lastPos = s.find_first_not_of(delimiters, 0);
  std::string::size_type pos = s.find_first_of(delimiters, lastPos);
  while (std::string::npos != pos || std::string::npos != lastPos) {
    tokens.push_back(s.substr(lastPos, pos - lastPos));
    lastPos = s.find_first_not_of(delimiters, pos);
    pos = s.find_first_of(delimiters, lastPos);
  }
}
// Decodes your encoded data to tree.
inline TreeNode* deserialize(std::string data) {
  if (data.front() != '[' || data.back() != ']') {
    return nullptr;
  }
  data.erase(data.begin());
  data.erase(std::prev(data.end()));
  std::vector<std::string> vec_str;
  split(data, vec_str, ",");
  if (vec_str.empty() || vec_str.front() == "null") {
    return nullptr;
  }

  std::vector<TreeNode*> result;
  for (const auto& it : vec_str) {
    if (it == "null") {
      result.push_back(nullptr);
    }
    else {
      result.push_back(new TreeNode(std::stoi(it)));
    }
  }

  for (size_t i = 0; i < result.size(); ++i) {
    if(result.at(i) != nullptr){
      if (result.size() > i * 2 + 2) {
      result.at(i)->left = result.at(i*2+1);
      result.at(i)->right = result.at(i*2+2);
      }
    }
  }

  return result.at(0);
}

例子

#include <cassert>

int main(){

  auto result = deserialize("[5,null,7,null,null,6,8]");
  assert(serialize(result) == "[5,null,7,null,null,6,8]");

  auto string =
      "[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,"
      "27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,"
      "51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,"
      "75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,"
      "99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,"
      "117,118,119,120,121,122,123,124,125,126]";
  auto result3 = deserialize(string);
  assert(serialize(result3) == string);
}

序列化改进版

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
 public:
  // Encodes a tree to a single string.
  string serialize(TreeNode* root) {
    std::string res = "[";
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
      auto temp = q.front();
      q.pop();
      if (temp == nullptr) {
        res += "null,";
      } else {
        res += std::to_string(temp->val) + ",";
        q.push(temp->left);
        q.push(temp->right);
      }
    }
    res += "]";
    return res;
  }

  // Decodes your encoded data to tree.
  TreeNode* deserialize(string data) {
    /// 去除首尾的'[]'
    data.erase(data.begin());
    data.erase(std::prev(data.end()));
    /// 把字符串解析成数组
    auto begin = 0;
    auto lastPos = data.find_first_not_of(',', 0);
    auto pos = data.find_first_of(',', lastPos);
    std::queue<std::string> q;
    while (pos != std::string::npos || std::string::npos != lastPos) {
      q.push(data.substr(lastPos, pos - lastPos));
      lastPos = data.find_first_not_of(',', pos);
      pos = data.find_first_of(',', lastPos);
    }
    /// 遍历数组建立树
    auto head = q.front();
    std::queue<TreeNode*> q_ceng;
    std::queue<TreeNode*> q_next_ceng;
    TreeNode* r = nullptr;
    if (head != "null") {
      auto thead = new TreeNode(std::atoi(head.c_str()));
      q_ceng.push(thead);
      r = thead;
    }
    q.pop();
    while (!q.empty()) {
      while (!q_ceng.empty()) {
        auto t = q_ceng.front();
        q_ceng.pop();
        auto l_t = q.front();
        q.pop();
        auto r_t = q.front();
        q.pop();
        if (l_t != "null") {
          t->left = new TreeNode(std::atoi(l_t.c_str()));
          q_next_ceng.push(t->left);
        }
        if (r_t != "null") {
          t->right = new TreeNode(std::atoi(r_t.c_str()));
          q_next_ceng.push(t->right);
        }
      }
      while (!q_next_ceng.empty()) {
        q_ceng.push(q_next_ceng.front());
        q_next_ceng.pop();
      }
    }
    return r;
  }
};