[数据结构与算法]7. 树的序列化与反序列化( 二叉树 和 N叉树 )

一，序列化

????????概念：序列化(Serialization) 是将对象的状态信息转化为可以存储或传输的形式过程。
????????作用：以存储形式使对象持久化; 将对象从一个地方传递到另一个地方。
????????本文讨论的是对于树的序列化问题，即将一棵树序列化成一个字符串，然后再通过反序列化恢复这棵树。

?

二，方法

????????通过树的层序遍历来进行序列化。
????????当然，也有其他方法。

三，头文件

#ifndef __TREE_NODE_H__
#define __TREE_NODE_H__

#include <time.h>
#include <stdlib.h>
#include <vector>

#define LEVEL_NUM 3
#define CHILD_NUM 3

#define TREE_SERIALIZE 0
#define NTREE_SERIALIZE !TREE_SERIALIZE

#define PRINT_VEC(vec) \
	do {	\
		std::cout << #vec << " : " << std::endl;	\
		for (auto it = (vec).begin(); it != (vec).end(); it++) {	\
			std::cout << *it << " ";	\
		}	\
		std::cout << std::endl << std::endl;	\
	} while (0)

// 二叉树
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;

	TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
	TreeNode(int v, TreeNode* l, TreeNode* r) : val(v), left(l), right(r) {}
};

// N 叉树
struct NTreeNode {
	int val;
	std::vector<NTreeNode*> children;

	NTreeNode(int v) : val(v) {}
	NTreeNode(int v, std::vector<NTreeNode*> c) : val(v), children(c) {}
};

static TreeNode* getRandomTree();		// 获取一棵二叉树
static std::vector<NTreeNode*> getChildrenVec(int& beginNum);
static NTreeNode* getRandomNTree();		// 获取一棵 N 叉树

// 二叉树的 前/后 序遍历
static void preorder(TreeNode* root, std::vector<int>& vec);
static void postorder(TreeNode* root, std::vector<int>& vec);

// N叉树的 前/后 序遍历
static void preorder(NTreeNode* root, std::vector<int>& vec);
static void postorder(NTreeNode* root, std::vector<int>& vec);

// 验证序列化与反序列化后树的结构是否一致
static bool verifyTree(void* originalT, void* deserializeT, bool isNTree);

TreeNode* getRandomTree() {
	srand((unsigned)time(NULL));
	int count = 0;

	TreeNode* root = new TreeNode(count++);
	root->left = new TreeNode(count++);
	root->right = new TreeNode(count++);
	TreeNode* left = root->left;
	TreeNode* right = root->right;

	for (int i = 0; i < LEVEL_NUM; i++) {
		int seed = rand() % 3;
		switch (seed) {
		case 0:
			left->right = new TreeNode(count++);
			left = left->right;
			break;
		case 1:
			right->left = new TreeNode(count++);
			right = right->left;
			break;
		case 2:
			left->left = new TreeNode(count++);
			right->right = new TreeNode(count++);
			left = left->left;
			right = right->right;
			break;
		}
	}

	return root;
}

std::vector<NTreeNode*> getChildrenVec(int& beginNum) {
	std::vector<NTreeNode*> vec;
	for (int i = 0; i < CHILD_NUM; i++) {
		vec.emplace_back(new NTreeNode(beginNum++));
	}
	return vec;
}

NTreeNode* getRandomNTree() {
	srand((unsigned)time(NULL));
	int count = 0;

	NTreeNode* root = new NTreeNode(count++);
	NTreeNode* ret = root;
	root->children = getChildrenVec(count);

	for (int i = 0; i < LEVEL_NUM; i++) {
		int seed = rand() % CHILD_NUM;
		root->children[seed]->children = getChildrenVec(count);
		root = root->children[seed];
	}

	return ret;
}

// 树的遍历
void preorder(TreeNode* root, std::vector<int>& vec) {
	if (root) {
		vec.emplace_back(root->val);
		preorder(root->left, vec);
		preorder(root->right, vec);
	}
}

void postorder(TreeNode* root, std::vector<int>& vec) {
	if (root) {
		postorder(root->left, vec);
		postorder(root->right, vec);
		vec.emplace_back(root->val);
	}
}

void preorder(NTreeNode* root, std::vector<int>& vec) {
	if (root) {
		vec.emplace_back(root->val);
		for (auto it = root->children.begin(); it != root->children.end(); it++) {
			preorder(*it, vec);
		}
	}
}

void postorder(NTreeNode* root, std::vector<int>& vec) {
	if (root) {
		for (auto it = root->children.begin(); it != root->children.end(); it++) {
			postorder(*it, vec);
		}
		vec.emplace_back(root->val);
	}
}

// 树的验证
bool verifyTree(void* originalT, void* deserializeT, bool isNTree) {

	std::vector<int> original, deserialize;

	if (isNTree) {
		preorder((NTreeNode*)originalT, original);
		preorder((NTreeNode*)deserializeT, deserialize);
	}
	else {
		preorder((TreeNode*)originalT, original);
		preorder((TreeNode*)deserializeT, deserialize);
	}

	if (original.size() != deserialize.size()) {
		return false;
	}

	for (int i = 0; i < original.size(); i++) {
		if (original[i] != deserialize[i]) {
			return false;
		}
	}

	original.clear();	deserialize.clear();

	if (isNTree) {
		postorder((NTreeNode*)originalT, original);
		postorder((NTreeNode*)deserializeT, deserialize);
	}
	else {
		postorder((TreeNode*)originalT, original);
		postorder((TreeNode*)deserializeT, deserialize);
	}

	if (original.size() != deserialize.size()) {
		return false;
	}

	for (int i = 0; i < original.size(); i++) {
		if (original[i] != deserialize[i]) {
			return false;
		}
	}
	return true;
}

#endif // __TREE_NODE_H__

四，二叉树的序列化与反序列化

#include "TreeNode.h"

#if TREE_SERIALIZE

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

using namespace std;

/*
序列化一棵二叉树
	利用层序遍历对二叉树进行存储
	注意，对于非空节点的空子节点，也需要用占位符存储
	比如，树的结构如下：
			1
		  /   \
		 2	   3
		/ \	  / \
	   #  4  #   #
	     / \
		#   #
	序列化后字符串为 ： 1/2/3/#/4/#/#/#/#
	注 : '#' 代表空节点
*/
string serialize(TreeNode* root) {
	string str = (root == nullptr) ? "#/" : "";		// 若是一棵空树，也需返回 "#/"
	if (root) {
		queue<TreeNode*> queue;		// 层序遍历是使用队列进行辅助遍历的
		queue.emplace(root);

		/*
			注意，与正常的层序遍历不同的是，不需要一层一层的弹出节点
			即 
			while (!queue.empty()) {
				int size = queue.size();
				for (int i=0; i<size; i++) {
					...
				}
			}
			因为最后需要的结果是一个字符串，而不是类似于 vector<vector<int>> 每层的节点信息。
		*/
		while (!queue.empty()) {
			root = (TreeNode*)queue.front();
			queue.pop();

			if (root == nullptr) {		// 因为非空节点的空子节点也需要加入队列，故弹出时需要进行判空
				str += "#/";	// 若是空，则需要添加占位符
			}
			else {
				str += to_string(root->val) + "/";		// 该节点的值序列化
				queue.emplace(root->left);				// 这里也与正常层序遍历不同，不需要判空，因为非空节点的空子节点也需要加入
				queue.emplace(root->right);
			}
		}
	}
	return str;
}

/*
反序列化
	利用字符串和序列化的规则，将序列化过程再模拟一遍，从而还原二叉树的结构
	这里需要注意的是对字符串的处理: 分割，字符串转数字
	用到了 stringstream 和 getline 。
	stringstream 是可以将一个 string 作为一个输入流，提供给一些从流中获取数据的函数，比如 getline
	getline 则可以用于从流中分割字符串，即读到指定字符后就停止
*/
TreeNode* deserialize(string str) {
	stringstream s(str);		// 将 序列化后的字符串 变成一个输入流

	string val;
	getline(s, val, '/');		// 以 '/' 为分隔符获取第一个值，比如 "1/2/3/#/4/#/#/#/#",则第一次 val 的值便是 "1"
	if (val == "#") {			// 若开始就为 "#" 则表明是空树
		return nullptr;
	}

	queue<TreeNode*> queue;		// 仍然以队列结构模拟序列化过程
	TreeNode* root = new TreeNode(stoi(val));	// stoi() 函数是将 string 变成 int 
	queue.emplace(root);

	while (!queue.empty()) {
		TreeNode* front = (TreeNode*)queue.front();		// 每当一个非空节点弹出来时，必定会有2个子节点
		queue.pop();

		if (getline(s, val, '/') && val != "#") {		// 只有当子节点不为空时，才加入到队列中
			front->left = new TreeNode(stoi(val));
			queue.emplace(front->left);					// 先左节点
		}

		if (getline(s, val, '/') && val != "#") {
			front->right = new TreeNode(stoi(val));
			queue.emplace(front->right);				// 再右节点
		}
	}
	return root;
}

int main() {
	TreeNode* root = getRandomTree();

	vector<int> preVec, postVec;
	preorder(root, preVec);	postorder(root, postVec);
	PRINT_VEC(preVec);		PRINT_VEC(postVec);
	preVec.clear();		postVec.clear();

	string str = serialize(root);
	cout << "serialize str : " << str << endl << endl;

	TreeNode* newRoot = deserialize(str);
	preorder(newRoot, preVec);	postorder(newRoot, postVec);
	PRINT_VEC(preVec);		PRINT_VEC(postVec);

	cout << "success : " << verifyTree((void*)root, (void*)newRoot, false) << endl;

	return 0;
}

#endif // TREE_SERIALIZE

五，N叉树的序列化与反序列化

#include "TreeNode.h"

#if NTREE_SERIALIZE

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

using namespace std;

/*
N 叉树的序列化
	N叉树与二叉树不同，它的孩子可能有多个，所以不能单纯的像二叉树那样标记
	比如，以下两棵树：
			1					1
		  /  \				  /  \
		 2    3				 2    3
		/    / \            / \    \
	   4    5   6          4   5    6
	  /    /   /          /   /    /
	 #    #    #         #   #    #
	
	若按二叉树的序列化方式，二者都是 ： "1/2/3/4/5/6/#/#/#/"

根本原因在于：
	我们无法知道N叉树某个节点的孩子有多少个。

解决方法：
	将某个节点的所有孩子放在一起，比如上图可以变成：
		"[1#]/[2#3#]/[4#]/[5#6#]/[]/[]/[]/"  -- 简化 -->  "1#/2#3#/4#/5#6#"
		"[1#]/[2#3#]/[4#5#]/[6#]/[]/[]/[]/"  -- 简化 -->  "1#/2#3#/4#5#/6#"
*/
string serialize(NTreeNode* root) {
	string str = (root == nullptr) ? "/" : "";	// 空树则直接返回 "/"

	if (root) {
		queue<NTreeNode*> queue;
		queue.emplace(root);
		str += to_string(root->val) + "#/";		// 与二叉树序列化不同的是，在加入节点的时候进行序列化

		while (!queue.empty()) {
			root = (NTreeNode*)queue.front();
			queue.pop();

			// 当弹出一个节点的时候，需要将其所有子节点序列化并加入队列中
			for (auto it = root->children.begin(); it != root->children.end(); it++) {
				str += to_string((*it)->val) + "#";
				queue.emplace(*it);
			}
			str += "/";
		}
	}
	return str;
}

/*
反序列化：
	因为某个节点的所有孩子节点都在一起，所以和二叉树处理起来大致一样

代码看起来比较乱，因为 root 节点需要单独处理。
*/
NTreeNode* deserialize(string str) {
	stringstream s(str);	// s 作为整个序列化字符串的输入

	string children;		// 用来记录孩子节点的序列串，比如 1#2#3#
	string val;				// 用来记录节点的值，比如 1

	getline(s, children, '/');		// 获取 第一个 节点, "1#" 或 ""

	if (children == "") {	// 若 第一个 节点为空，则直接返回 nullptr
		return nullptr;
	}

	stringstream tmp(children);	// tmp 作为 children 的流
	getline(tmp, val, '#');		// 获取 root 节点所对应的值

	
	NTreeNode* root = new NTreeNode(stoi(val));

	queue<NTreeNode*> queue;	// 将 root 节点加入队列
	queue.emplace(root);
	
	while (!queue.empty()) {
		NTreeNode* front = (NTreeNode*)queue.front();		// 弹出队头节点
		queue.pop();

		getline(s, children, '/');		// 获取队头节点的所有孩子的序列化字符串
		if (children != "") {			// 若孩子不为空
			vector<NTreeNode*> vec;
			stringstream tmp(children);
			while (getline(tmp, val, '#')) {
				NTreeNode* node = new NTreeNode(stoi(val));
				vec.emplace_back(node);
				queue.emplace(node);
			}
			front->children = vec;
		}
	}

	return root;
}


int main() {

	NTreeNode* root = getRandomNTree();

	vector<int> preVec, postVec;
	preorder(root, preVec);	postorder(root, postVec);
	PRINT_VEC(preVec);		PRINT_VEC(postVec);
	preVec.clear();		postVec.clear();

	string str = serialize(root);

	cout << "serialize str : " << str << endl << endl;

	NTreeNode* newRoot = deserialize(str);
	preorder(newRoot, preVec);	postorder(newRoot, postVec);
	PRINT_VEC(preVec);		PRINT_VEC(postVec);

	cout << "success : " << verifyTree((void*)root, (void*)newRoot, true) << endl;

	return 0;
}

#endif // NTREE_SERIALIZEs