使用队列层序遍历，序列化二叉树

                                           序列化二叉树
1

题目描述：

1.将二叉树以一定的规则(先序、中序、后续、层序)进行遍历，将节点数据保存到字符串中，每个节点数据保存到字符串中用"!“分割，空节点用”#"代替。

2.将得到的字符串按照一定的规则(先序、中序、后续、层序)构建二叉树。

题解
对于第一题，本文以层序遍历为例进行讲解：
层序遍历二叉树，首先考虑使用什么工具保存遍历的到的数据，层序遍历是从根节点开始，每层从左到右依次访问，直至遍历整个二叉树，其中最适合的便是队列，先进先出。
对于第一题的解题思路与代码，我详细的加到了代码段中，如下所示：

//这是定义二叉树的结构体，以及构造函数
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
1
2
3
4
5
6
7
8
9

char* Serialize(TreeNode *root) {   
	//定义结构体类型的队列，用来存储得到的二叉树节点数据
    queue<TreeNode*> q;
    //定义一个字符串，保存遍历的节点数据
    string s;
    //使用层序遍历得到字符串
	//由于节点为空需要返回#，因此需要考虑为空的情况
	//首先，根节点进队
	q.push(root);
	//循环的进队和出队操作，直到队列为空结束循环
	while (!q.empty()) {
		//将队头出队
		TreeNode *head = q.front();
		//删除队头的元素
		q.pop();
		//判断出队的是个空节点，还是有左右子节点，有左右子节点的话需要对左右子节点进队操作
		//为空的情况
		if (head == nullptr) {
			s.push_back('#');
			s.push_back('!');
			continue;
		}
		//不为空的情况，把存取的数据提出来
		s = s + to_string(head->val);
        s.push_back('!');
		//有左子树
		q.push(head->left);
		//有右子树
		q.push(head->right);
	}
	//函数是char类型，最后需要把string转换为char
	char *str = new char[s.length() + 1];
	strcpy(str, s.c_str());
	return str;
    }
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

对于第二个题目，本文仍然使用层序遍历，但不同于直接构造二叉树的是需要对字符串进行分割，按照第一个题目中的分割标记"!"，将字符串中的数字取出转换为整数类型，然后才能给节点赋值数据。

TreeNode* Deserialize(char *str) {
    //拷贝一个串备用，别后面把值改没了
	string ss(str);
	//搞一个二叉树节点类型的队列，存储恢复出来的节点
	queue<TreeNode *>node;
	//重构二叉树要确定两个标志，#和！
	//先看一下字符串是否为空
	if (str == nullptr)return nullptr;
	//确定返回的字符串是不是有根节点，没有根节点同样为空
	if (str[0] == '#')return nullptr;
	//程序能到这里就说明返回的字符串不为空，可以构建二叉树
	//首先，构建二叉树的根节点，开始还在考虑如何依据结束符取值，没想到c++有可以用的函数
	//接用构造函数直接初始化
	//atoi(s.c_str())直接取出第一个!号之前的数组，省时省力。
	TreeNode *root = new TreeNode(atoi(ss.c_str()));
	//既然前面的已经赋值，可以舍取，得到除去第一个节点值的剩下值
	ss = ss.substr(ss.find_first_of('!') + 1);
	//根节点进队
	node.push(root);
	//只要字符串不为空，就循环处理吧，至于后面那个条件暂时没看明白
	while (!ss.empty() && !node.empty()) {
		TreeNode *temp = node.front();
		node.pop();
		//这里就不用判断字符串是不是空了，要是空的他也进不来
		//根节点没有左子树
		if (ss[0] == '#') {
			temp->left = nullptr;
			//里面放2是为了跳过结束标识符
			ss = ss.substr(2);
		}
		else {
			//把左子树进队
			temp->left = new TreeNode(atoi(ss.c_str()));
			node.push(temp->left);
			ss = ss.substr(ss.find_first_of('!') + 1);
		}
		//处理右子树的情况
		if (ss[0] == '#') {
			temp->right = nullptr;
			ss = ss.substr(2);
		}
		else {
			temp->right = new TreeNode(atoi(ss.c_str()));
			node.push(temp->right);
			ss = ss.substr(ss.find_first_of('!') + 1);
		}
	}
	return root;
    }
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

代码可以直接copy，在主函数中调用即可，主要是理解层序遍历的原理。目前我也在学习的路上探索，如果有理解错误的地方，希望看到的大佬能给本文指出，我一定抓紧改正。