【数据结构系列】——二叉树的各个遍历及序列化与反序列化

二叉树的各种遍历，序列化与反序列化

序列化与反序列化：将变成语言中的结构体序列化成JSON字符串，存入缓存或者通过网络发送给远程服务，消费者接受JSON字符串然后进行范徐丽恶化，就可以得到原始数据了。目的是，已某种固定格式组织字符串，使得数据可以独立于编程语言。

序列化：吧结构化的数据“打平”，其实就是在考察二叉树的遍历方式

反序列化，将字符串还原出二叉树

前序遍历

前序遍历框架：

void traverse(TreeNode root){
	if(root == null) return;
	//前序遍历的代码
	traverse(root.left);
	traverse(root.right);
}

序列化，需要将一颗二叉树打平成一个字符串

//代表分割符的字符
    String SEP = ",";
    //代表null空指针的字符
    String NULL = "#";
    /**
     * 主函数，将二叉树序列化为字符串
     */
    String serialize(TreeNode root){
        //用于拼接字符串
        StringBuilder sb = new StringBuilder();
        serialize(root,sb);
        return sb.toString();
    }
    /**
     * 将二叉树打平为字符串
     */
    void serialize(TreeNode root,StringBuilder sb){
        if (root == null){
            sb.append(NULL).append(SEP);
            return;
        }
        /**
         * 前序遍历
         */
        sb.append(root.val).append(SEP);
        serialize(root.left,sb);
        serialize(root.right,sb);
    }

反序列化

先确定根节点root，然后根据前序遍历的规则，递归生成左右子树

/**
     * 主函数，将字符串反序列化为二叉树结构
     * @param data
     * @return
     */
    TreeNode deserialize_pre(String data){
        //将字符串转化为列表
        LinkedList<String> nodes = new LinkedList<>();
        for (String s : data.split(SEP)) {
            nodes.addLast(s);
        }
        return deserialize(nodes);
    }

    /**
     * 辅助函数，通过nodes列表构造二叉树
     * @param nodes
     * @return
     */
    private TreeNode deserialize(LinkedList<String> nodes) {
        if (nodes.isEmpty())
            return null;
        /**
         * 前序遍历
         */
        //列表最左侧就是根节点
        String first = nodes.removeFirst();
        if (first.equals(NULL))
            return null;
        TreeNode root = new TreeNode(Integer.parseInt(first));
        root.left = deserialize(nodes);
        root.right = deserialize(nodes);
        return root;
    }

后序遍历

后序遍历框架

void traverse(TreeNode root){
    if(root == null)
        return;
    traverse(root.left);
    traverse(root.right);
}

序列化：

String SEP=",";
String NULL="#";
String serialize+post(TreeNode root){
    StringBuilder sb = new StringBuilder();
    serialize(root,sb);
    return sb.toString();
}
void serialize(TreeNode root,StringBuilder sb){
    if(root == null){
        sb.append(NULL).append(SEP);
        return;
    }
    serialize(root.left,sb);
    serialize(root.right,sb);
    sb.append(root.val).append(SEP);
}

反序列化：

从后往前取出列表元素，一定要先构造root.right子树，后构造root.left子树


    /**
     * 主函数，将字符串反序列化为二叉树结构
     * @param data
     * @return
     */
    TreeNode deserialize_post(String data){
        //将字符串转化为列表
        LinkedList<String> nodes = new LinkedList<>();
        for (String s : data.split(SEP)) {
            nodes.addLast(s);
        }
        return deserialize(nodes);
    }

    /**
     * 辅助函数，通过nodes列表构造二叉树
     * @param nodes
     * @return
     */
    private TreeNode deserialize(LinkedList<String> nodes) {
        if (nodes.isEmpty())
            return null;
        //从后往前取出元素
        String last = nodes.removeLast();
        if (last.equals(NULL))
            return null;
        TreeNode root = new TreeNode(Integer.parseInt(last));
        root.right = deserialize(nodes);
        root.left = deserialize(nodes);

        return root;
    }

中序遍历

中序遍历不能反序列化，因为root的值被夹在两颗子树的中间，我们不知道确切的索引位置，无法找到root节点，无法进行反序列化

中序遍历序列化：

void serialize(TreeNode root,StringBuilder sb){
    if(root == null){
        sb.append(NULL).append(SEP);
        return;
    }
    serialize(root.left,sb);
    sb.append(root.val).append(SEP);
    serialize(root.right,sb);
}

层序遍历

层序遍历框架：

void traverse(TreeNode root){
	if(root == null) return;
	//初始化列表，将root加入队列
	Queue<TreeNode> q = new LinkedList<>();
	q.offer(root);
	while(!q.isEmpty()){
		TreeNode cur = q.poll();
		
        /**
        层序遍历代码位置
        */
        if(cur == null) continue;
        System.out.prontlin(cur.val);
        q.offer(cur.left);
        q.offer(cur.right);
	}
}