十六.二叉樹的序列化和反序列化

【題目】

二叉樹的序列化和反序列化

【定義】

二叉樹的序列化是指：把一棵二叉樹按照某種周遊方式的結果以某種格式儲存為字元串，進而使得記憶體中建立起來的二叉樹可以持久儲存。

二叉樹的反序列化是指：根據某種周遊順序得到的序列化字元串結果str，重構二叉樹。

【思路】

一.先序周遊二叉樹序列化（遞歸）

1.中間結點的值加入到字元串中

2.左邊節點的值加入到字元串中（遞歸）（左邊節點作為左子樹的中間結點，加入順序是中左右，是遞歸）

3.右邊節點的值加入到字元串中（遞歸）（右邊節點作為右子樹的中間結點，加入順序是中左右，是遞歸）

二.層級周遊二叉樹序列化（需要一個隊列儲存住左右順序）

1.中間結點的值加入到字元串中

2.建立一個隊列，把中間結點加進去

3.隊列不為空的時候，彈出一個（表示目前操作的是這個節點），如果他的左不為空，建構字元串，加入到隊列（為了保證下一個操作的是第二層左節點），如果他的右不為空，建構字元串，加入到隊列（操作的是第二層右節點），結束條件是隊列中沒有節點了，表示所有的節點都操作完了。

三.先序周遊二叉樹反序列化（遞歸）

1.字元串拆分為字元串數組，

2.建立一個隊列儲存住這個字元串數組（因為涉及到裡面節點的操作，需要彈出，同時還要保證先後順序）

3.彈出元素，不為空的話說明是一個結點，第一個彈出的是頭結點，建立左子樹（彈出來的是頭結點的左子樹上），建立右子樹（遞歸調用）

四.層級周遊二叉樹反序列化

1.字元串拆分為字元串數組，

2.建立好第一個節點，加入到隊列中；

3.如果目前隊列不為空，彈出一個，建構好他的左右節點；壓入棧，下一個操作的是左節點。

【序列化代碼實作】

//中左右(先序周遊序列化)
	public static String serialByPre(Node head) {
		if (head==null) {
			return "#_";
		}
		String res=head.value+"_";
		res+=serialByPre(head.left);
		res+=res+serialByPre(head.right);
		return res;
		}
	
	//層級周遊序列化
	public static String serialByLevel(Node head) {
		if (head==null) {
			return "#_";
		}
		String res=head.value+"_";
		Queue<Node> queue=new LinkedList<>();
		queue.offer(head);
		while(!queue.isEmpty()) {
		head=queue.poll();//彈出隊列的第一個元素就是頭結點，第二次是頭結點的左，第三次是頭結點的右
			if(head.left!=null) {
				res+=head.left.value+"_";
				queue.offer(head.left);//隊列尾部插入元素
			}else {
				res+="#_";
			}
			if(head.right!=null) {
				res+=head.right.value+"_";
				queue.offer(head.right);
			}else {
				res+="#_";
			}
		}
		return res;		
	}
           

【反序列化代碼實作】

//先序周遊反序列化
//1.根據_拆分為字元串數組,存到一個隊列中
public static Node reconByPreString(String res) {
		String[] values=res.split("_");
		Queue<String> queue=new LinkedList<>();
		for (int i = 0; i < values.length; i++) {
			queue.offer(values[i]);
		}
		return reconPreOrder(queue);
	}
//2.構造二叉樹
	public  static Node reconPreOrder(Queue<String> queue) {
		String value=queue.poll();
		if (value.equals("#")) {
			return null;
		}
		Node head=new Node(Integer.valueOf(value));//隊列中第一個彈出來的是還原頭結點
		head.left=reconPreOrder(queue);//去掉頭結點後下一個就是左子樹的頭結點（遞歸調用）
		head.right=reconPreOrder(queue);//去掉左邊的頭結點後，就是右子樹的頭結點（遞歸調用）
		return head;	
	}
           

//層級周遊反序列化
	public static Node reconByLevelString(String res) {
		String[] values=res.split("_");
		int index=0;
		Node head=generateNodeByString(values[index++]);//頭結點生成了
		Queue<Node> queue=new LinkedList<>();
		if (head!=null) {
			queue.offer(head);//頭結點壓入棧
		}
		Node node=null;
		if(!queue.isEmpty()) {
			node=queue.poll();//棧不為空，彈出來的是頭結點
			node.left=generateNodeByString(values[index++]);//頭結點的左構造成功
			node.right=generateNodeByString(values[index++]);//頭結點的右構造成功
			//左右節點都存在的話，都壓入隊列中，使隊列不為空，在彈出來的就是頭結點的左節點，構造他的左右，第三次彈出來的是頭結點的右節點，構造他的左右
			if (node.left!=null) {
				queue.offer(node.left);
			}
			if (node.right!=null) {
				queue.offer(node.right);
			}
		}
		return head;
	}


	public static Node generateNodeByString(String val) {
		if(val.equals("#")) {
			return null;
		}
		return new Node(Integer.valueOf(val));
	}