大家好，都吃晚饭了吗？我是Kaiqisan,是一个已经走出社恐的一般生徒
为什么引入这个概念
在计算机中，如果我们如果想要可视化一棵树，那会是非常困难的工作，所以，我们就想到了一种最简单的方法来表示一棵树，而且只使用字符串，也可以区分每一颗树的不同
现在有两棵树
1
/
2
/
3
1
\
2
\
3
如果我们使用同样的遍历方法，结果都是123,如果一个二叉树的结构未知，我们只是使用遍历的方法，我们将永远无法获取一棵树的结构。
所以我们在遍历的时候使用序列化，也就是使用分隔符来代替空节点填充进去，那么现在的树结构是这样的
那么我们重新遍历一遍（使用先序遍历）结果分别为 123#### 1#2#3##，为防止歧义，我们也可以在每一个元素都使用分隔符(1 _ 2 _ 3_ # _ # _ # _ # )，这样就可以找到两个数的区别了，这也是最简单的树的表达方法
1
/ \
2 #
/ \
3 #
/ \
# #
1
/ \
# 2
/ \
# 3
/ \
# #
/* 序列化参考代码 */
public static void main(String[] args) {
Tree head = new Tree(1);
Tree a2 = new Tree(2);
Tree a3 = new Tree(3);
Tree a4 = new Tree(4);
Tree a5 = new Tree(5);
Tree a6 = new Tree(6);
Tree a7 = new Tree(7);
Tree a8 = new Tree(8);
// 链接树
head.left = a2;
head.right = a3;
a2.left = a4;
a2.right = a5;
a3.left = a6;
a3.right = a7;
a6.right = a8;
// 序列化
doOrderify(head, head);
}
static void doOrderify(Tree head, Tree realHead) {
if (head == null) {
System.out.print("_" + "#");
return;
}
if (head == realHead) {
// 对输出的工整性进行调整，第一个元素不输出下划线
System.out.print(head.val);
} else {
System.out.print("_" + head.val);
}
doOrderify(head.left, null);
doOrderify(head.right, null);
}
正如编码一般，我们还需要反编码，这个序列化也需要反序列化，重新把它转化为一棵树
以上面的 1#2#3## 为例，我们如何把它转化为一颗真正的树呢？
还是遍历把，这里提供两种方法
方法1
投机取巧法（非递归）
先把第一个元素入栈（因为一开始序列化使用先序遍历，所以这里的第一个元素必定不是#）
然后查看这个栈中第一个元素是否有左节点，如果有，就判断序列化字符串的下一个元素是否为#,如果不为#，就新建一个节点，连接，作为自己的左孩子，指针转向这个左孩子，如果遍历元素为#，就跳过。如果头结点的左孩子已经有元素了，就重复上面的操作，只不过把左都换成右就行了。
在遍历之前，先判断当前遍历的序列元素和它下一个元素是否都为#,如果都是#,就代表当前的指针指向的节点无左孩子，也无右孩子（因为null节点无孩子指针，不可能有 null.left -> null，所以只可能是node.left = null node.right = null）,此时，出栈一个元素，指针指向当前节点的父节点，回到上一层
static Tree startBuild(String[] arr) {
Stack<Tree> temp = new Stack<>();
Tree head = new Tree(arr[0]);
temp.push(head);
Tree res = head; // 临时变量
for (int i = 1; i < arr.length - 1; i++) {
if (arr[i].equals("#") && arr[i + 1].equals("#")) {
while (head.left != null && head.right != null) {
temp.pop();
head = temp.peek();
}
continue;
}
if (temp.peek().left == null) {
if (arr[i].equals("#")) {
continue;
}
temp.peek().left = new Tree(arr[i]);
head = temp.peek().left;
temp.push(head);
} else if (temp.peek().right == null) {
if (arr[i].equals("#")) {
continue;
}
temp.peek().right = new Tree(arr[i]);
head = temp.peek().right;
temp.push(head);
}
}
return res;
}
方法2
频繁挪动法（非递归）
不使用栈，树节点有额外指针parent会指向父亲节点。
先利用序列的第一个元素来生成根节点，也让指针指向这个根节点。
每次遍历序列，判断当前的指针指向的节点的左右孩子是否为空，（先判断左孩子，再判断右孩子），如果有不为空的，就开始生成新节点，然后焊接成当前节点的孩子，然后指针指向这个孩子，如果左右节点都有了，那就往上钻，回到父亲节点，如果父亲节点也是左右节点都有了，那就接着往往上钻，直到找到有空档（子节点没有满）的父节点，然后继续前面的操作。
static Tree startBuild2(String[] arr) {
Stack<Tree> temp = new Stack<>();
Tree head = new Tree(arr[0]);
temp.push(head);
Tree res = head; // 临时变量
for (int i = 1; i < arr.length - 1; i++) {
if (arr[i].equals("#") && arr[i + 1].equals("#")) {
while (head.left != null && head.right != null) {
temp.pop();
head = temp.peek();
}
continue;
}
if (temp.peek().left == null) {
if (arr[i].equals("#")) {
continue;
}
temp.peek().left = new Tree(arr[i]);
head = temp.peek().left;
temp.push(head);
} else if (temp.peek().right == null) {
if (arr[i].equals("#")) {
continue;
}
temp.peek().right = new Tree(arr[i]);
head = temp.peek().right;
temp.push(head);
}
}
return res;
}
方法3
递归法
很简单就不用讲解思路了
public static void main(String[] args) {
String str = "1_2_4_#_#_5_#_#_3_6_#_8_#_#_7_#_#";
String[] arr = str.split("_");
Queue<String> temp = new LinkedList<>();
for (int i = 0; i < arr.length; i++) {
temp.offer(arr[i]);
}
Tree head = startBuild3(temp);
TestSearch(head);
}
static TreeHasParent startBuild3(Queue<String> queue) {
String a = queue.poll();
if (a.equals("#")) {
return null;
}
TreeHasParent head = new TreeHasParent(Integer.valueOf(a));
head.left = startBuild3(queue);
head.right = startBuild3(queue);
return head;
}
总结
没有总结，上面的序列化非序列化都是建立在先序遍历的机制上面，如果您想要使用其他的遍历方法的话请参考上面的思维，可以自己再写出中序遍历，后序遍历的序列化和反序列化的代码！
