如何序列化二叉树

Question

我今天去接受采访,要求我序列化一棵二叉树.我实现了一种基于数组的方法,其中节点i的子节点(在水平顺序遍历中编号)处于左子节点的2*i索引和右子节点的2*i + 1.面试官似乎或多或少都很高兴,但我想知道序列化究竟意味着什么？它是否专门用于展平树以写入磁盘,或者序列化树还包括将树转换为链表,比方说.另外,我们如何将树扁平化为(双重)链表,然后重构它？您可以从链表重新创建树的确切结构吗？

Answer 1

所有这些文章主要讨论序列化部分.反序列化部分在一次通过中有点棘手.

我也为反序列化实现了一个有效的解决方案.

问题:序列化和反序列化包含正数的二叉树.

序列化部分:

1. 使用0表示null.
2. 使用preorder遍历序列化为整数列表.

反序列化部分:

1. 获取整数列表并使用递归辅助方法进行反序列化.
2. 递归解串器返回一对(BTNode节点,int nextIndexToRead),其中节点是到目前为止构造的树节点,而nextIndexToRead是要在序列化的数字列表中读取的下一个数字的位置.

以下是Java中的代码:

public final class BinaryTreeSerializer
{
    public static List<Integer> Serialize(BTNode root)
    {
        List<Integer> serializedNums = new ArrayList<Integer>();

        SerializeRecursively(root, serializedNums);

        return serializedNums;
    }

    private static void SerializeRecursively(BTNode node, List<Integer> nums)
    {
        if (node == null)
        {
            nums.add(0);
            return;
        }

        nums.add(node.data);
        SerializeRecursively(node.left, nums);
        SerializeRecursively(node.right, nums);
    }

    public static BTNode Deserialize(List<Integer> serializedNums)
    {
        Pair pair = DeserializeRecursively(serializedNums, 0);

        return pair.node;
    }

    private static Pair DeserializeRecursively(List<Integer> serializedNums, int start)
    {        
        int num = serializedNums.get(start);

        if (num == 0)
        {
            return new Pair(null, start + 1);
        }

        BTNode node = new BTNode(num);

        Pair p1 = DeserializeRecursively(serializedNums, start + 1);
        node.left = p1.node;

        Pair p2 = DeserializeRecursively(serializedNums, p1.startIndex);
        node.right = p2.node;

        return new Pair(node, p2.startIndex);
    }

    private static final class Pair
    {
        BTNode node;
        int startIndex;

        private Pair(BTNode node, int index)
        {
            this.node = node;
            this.startIndex = index;
        }
    }
}

public class BTNode 
{
    public int data;
    public BTNode left;
    public BTNode right;

    public BTNode(int data)
    {
        this.data = data;
    }
}

Answer 2

方法1:同时执行Inorder和Preorder遍历以对树数据进行分类.在反序列化时,使用预订并按顺序执行BST以正确形成树.

你需要两者,因为即使结构可能不同,A - > B - > C也可以表示为预订.

方法2:使用#作为左撇子或右孩子无效的哨兵.....

Answer 3

使用预订序遍历,序列化二叉树.使用相同的预先遍历遍历来反序列化树.边缘情况要小心.这里的空节点用"#"表示

public static String serialize(TreeNode root){
            StringBuilder sb = new StringBuilder();
            serialize(root, sb);
            return sb.toString();
        }

    private static void serialize(TreeNode node, StringBuilder sb){
        if (node == null) {
            sb.append("# ");
        } else {
            sb.append(node.val + " ");
            serialize(node.left, sb);
            serialize(node.right, sb);
        }
    }

    public static TreeNode deserialize(String s){
        if (s == null || s.length() == 0) return null;
        StringTokenizer st = new StringTokenizer(s, " ");
        return deserialize(st);
    }

    private static TreeNode deserialize(StringTokenizer st){
        if (!st.hasMoreTokens())
            return null;
        String val = st.nextToken();
        if (val.equals("#"))
            return null;
        TreeNode root = new TreeNode(Integer.parseInt(val));
        root.left = deserialize(st);
        root.right = deserialize(st);
        return root;
    }