乐趣区

关于算法:二叉树的序列化和反序列化

序列化的定义:

序列化(serialization)是指将数据结构或对象状态转换成可取用格局(例如存成文件,存于缓冲,或经由网络中发送),以留待后续在雷同或另一台计算机环境中,能复原原先状态的过程。按照序列化格局从新获取字节的后果时,能够利用它来产生与原始对象雷同语义的正本。

从一系列字节提取数据结构的反向操作,是反序列化。

先序形式序列化和反序列化

1、先序形式序列化

按先序遍历的形式,挨个将二叉树的各个节点,存储为一个以指定分隔符分隔的字符串,为空的节点也须要存储。

/**
 * 先序形式序列化
 *
 * @author Java 和算法学习:周一
 */
public static Queue<String> preSerial(Node head) {Queue<String> ans = new LinkedList<>();
    pre(head, ans);
    return ans;
}

private static void pre(Node head, Queue<String> ans) {if (head == null) {ans.add(null);
    } else {ans.add(String.valueOf(head.value));
        pre(head.left, ans);
        pre(head.right, ans);
    }
}

2、先序形式反序列化

按先序遍历的形式,挨个以指定分隔符切分之前的字符串,还原为原始二叉树。

/**
 * 先序形式反序列化
 *
 * @author Java 和算法学习:周一
 */
public static Node buildByPre(Queue<String> queue) {if (queue == null || queue.size() == 0) {return null;}
    return preB(queue);
}

private static Node preB(Queue<String> queue) {String value = queue.poll();
    if (value == null) {return null;}
    Node head = new Node(Integer.parseInt(value));
    head.left = preB(queue);
    head.right = preB(queue);
    return head;
}

后序形式序列化和反序列化

1、后序形式序列化和反序列化和先序形式的思路和过程是一样的。

须要留神的是在反序列化时,得先把原始序列化的程序颠倒一下(颠倒后的程序即是头右左 ),再以头右左的形式进行反序列化,因为要先有头才有孩子( 先结构头能力结构孩子),这样反序列化的后果才是对的

/**
 * 后序形式序列化
 *
 * @author Java 和算法学习:周一
 */
public static Queue<String> posSerial(Node head) {Queue<String> ans = new LinkedList<>();
    pos(head, ans);
    return ans;
}

public static void pos(Node head, Queue<String> ans) {if (head == null) {ans.add(null);
    } else {pos(head.left, ans);
        pos(head.right, ans);
        ans.add(String.valueOf(head.value));
    }
}
/**
 * 后序形式反序列化
 *
 * @author Java 和算法学习:周一
 */
public static Node buildByPos(Queue<String> queue) {if (queue == null || queue.size() == 0) {return null;}
    Stack<String> stack = new Stack<>();
    while (!queue.isEmpty()) {stack.push(queue.poll());
    }
    return posB(stack);
}

public static Node posB(Stack<String> posStack) {String value = posStack.pop();
    if (value == null) {return null;}
    Node head = new Node(Integer.parseInt(value));
    head.right = posB(posStack);
    head.left = posB(posStack);
    return head;
}

2、为啥没有中序形式的序列化?

二叉树无奈通过中序遍历的形式实现序列化和反序列化,因为不同的两棵树,可能失去同样的中序序列,这时候就无奈确定此中序序列代表哪个二叉树了。

按层形式序列化和反序列化

1、序列化

(1)筹备一个放后果的队列(放的是节点的字符串值),筹备一个辅助队列(放的是节点)

(2)往后果队列放入头节点的值,往辅助队列放入头节点

(3)弹出辅助队列的头节点,

1)此节点左孩子不为空,往后果队列放入左孩子节点的值,往辅助队列放入左孩子;如果此节点左孩子为空,往后果队列放入 null 值,辅助队列不变。

2)此节点右孩子不为空,往后果队列放入右孩子节点的值,往辅助队列放入右孩子;如果此节点右孩子为空,往后果队列放入 null 值,辅助队列不变。

(4)始终执行第 3 步,直到辅助队列为空。

/**
 * 按层形式序列化
 *
 * @author Java 和算法学习:周一
 */
public static Queue<String> levelSerial(Node head) {Queue<String> ans = new LinkedList<>();
    if (head == null) {ans.offer(null);
    } else {
        // 往后果队列放入头节点的值
        ans.add(String.valueOf(head.value));
        // 筹备一个辅助队列
        Queue<Node> help = new LinkedList<>();
        // 辅助队列放入头节点
        help.offer(head);
        while (!help.isEmpty()) {Node current = help.poll();
            // 辅助队列头节点的左孩子不为空
            if (current.left != null) {
                // 往后果队列放左孩子的值
                ans.offer(String.valueOf(current.left.value));
                // 往辅助队列放左孩子
                help.offer(current.left);
            } else {
                // 往后果队列放 null,辅助队列不变
                ans.offer(null);
            }

            // 右孩子同理
            if (current.right != null) {ans.offer(String.valueOf(current.right.value));
                help.offer(current.right);
            } else {ans.offer(null);
            }
        }
    }
    return ans;
}

2、反序列化

(1)从原队列弹出第一个值,反序列化生成头节点

(2)筹备一个辅助队列(放的是节点),放入头节点

(3)弹出辅助队列的第一个节点 current,从原队列里弹出一个值,反序列化做为 current 的左孩子;再从原队列里弹出一个值,反序列化做为 current 的右孩子

(4)current 的左孩子不是空,则放入辅助队列;current 的右孩子不是空,则放入辅助队列

(5)始终循环执行 3、4 步,直到辅助队列为空

/**
 * 按层形式反序列化
 *
 * @author Java 和算法学习:周一
 */
public static Node buildByLevel(Queue<String> queue) {if (queue == null || queue.size() == 0) {return null;}
    // 反序列化构建头节点
    Node head = generateNode(queue.poll());
    // 筹备一个辅助队列
    Queue<Node> help = new LinkedList<>();
    // 避免队列里就只有一个 null,如果队列里就只有一个 null,则整个办法就间接完结了
    if (head != null) {
        // 辅助队列放入头节点
        help.offer(head);
    }
    Node current;
    while (!help.isEmpty()) {
        // 弹出辅助队列的第一个节点
        current = help.poll();
        // 反序列化构建左孩子
        current.left = generateNode(queue.poll());
        // 反序列化构建右孩子
        current.right = generateNode(queue.poll());

        if (current.left != null) {
            // 左孩子不为空,往辅助队列放入左孩子
            help.offer(current.left);
        }
        if (current.right != null) {
            // 右孩子不为空,往辅助队列放入右孩子
            help.offer(current.right);
        }
    }
    return head;
}

本文所有代码地址:https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/SerializeAndDeserializeTree.java

退出移动版