序列化二叉树

编程练习

题目：请实现两个函数，分别用来序列化和反序列化二叉树

思路：序列化二叉树即将二叉树转换为某一表达存入永久存储设备，比如硬盘上，反序列化就是将硬盘上代表二叉树的文件利用程序读入，并将一模一样的二叉树在内存中再次重现。

　　题目中给出的序列化后的格式是一个字符串，所以能想到用二叉树的某一遍历结果转为符合条件的字符串即完成了二叉树的序列化，为了方便起见。我们采用了层序遍历，将为空的结点的序列化字符设为“#”，并将每个节点间用逗号隔开。反序列化的时候采用相反的思想重现二叉树即可。
java代码如下：

import java.util.LinkedList;
import java.util.Queue;

public class SerializeTree {
	/**
	 * 层序遍历来形成序列化的二叉树字符串，用#来表示空
	 * @param root
	 * @return
	 */
    static String Serialize(TreeNode root) {
        StringBuilder sb=new StringBuilder();
        Queue<TreeNode> treeQueue=new LinkedList<TreeNode>();
        if(root!=null) {
        	treeQueue.add(root);
        }
        while(!treeQueue.isEmpty()) {
    		TreeNode node=treeQueue.poll();
    		if(node!=null) {
    			sb.append(node.val+",");
        		treeQueue.add(node.left);
        		treeQueue.add(node.right);
    		}else {
    			sb.append("#"+",");
    		}
        }
        if(sb.length()!=0) {
        	sb.deleteCharAt(sb.length()-1);
        }
    	return sb.toString();
  }
    /**
     * 反序列化二叉树，注意二叉树层序遍历序列中的父子关系的规律
     * @param str
     * @return
     */
    static TreeNode Deserialize(String str) {
    	
    	if(str==null ||str.length()==0) {
    		return null;
    	}
    	String [] nodes=str.split(",");
    	TreeNode [] treeNodes=new TreeNode[nodes.length];
    	//将不为#的字符转换为不为空的二叉树结点
    	for(int i=0;i<nodes.length;i++) {
    		if(!nodes[i].equals("#")) {
    			treeNodes[i]=new TreeNode(Integer.valueOf(nodes[i]));
    		}
    	}
    	//根据层序遍历的规则，添加结点间的父子关系
    	for(int i=0,j=1;j<treeNodes.length;i++) {
    		if(treeNodes[i]!=null) {
    			treeNodes[i].left=treeNodes[j++];
        		treeNodes[i].right=treeNodes[j++];
    		}
    	}
    	return treeNodes[0];
    }
  	public static void main(String[] args) {
	  	TreeNode root=new TreeNode(0);
  		TreeNode node1=new TreeNode(1);
		TreeNode node2=new TreeNode(2);
		TreeNode node3=new TreeNode(3);
		TreeNode node4=new TreeNode(4);
		TreeNode node5=new TreeNode(5);
		
		root.left=node1;
		root.right=node2;
		node1.left=node3;
		node1.right=null;
		node2.left=node5;
		String s=Serialize(root);
		System.out.println(s);
		System.out.println(Deserialize(s).val);
  	}

}