如何序列化二叉树 [英] How to Serialize Binary Tree

问题描述

我今天去了一次采访，被要求对一个二叉树进行序列化.我实现了一种基于数组的方法，其中节点i的子节点(按级别顺序遍历的编号)对于左子节点为2 * i索引，对于右子节点为2 * i +1.面试官似乎或多或少地感到高兴，但我想知道序列化的确切含义是什么?它是专门用于使树变平以写入磁盘还是要序列化树，还包括仅将树变成链接列表.另外，我们将如何将树展平为(双重)链表，然后对其进行重构?您可以从链接列表中重新创建树的确切结构吗?

I went to an interview today where I was asked to serialize a binary tree. I implemented an array-based approach where the children of node i (numbering in level-order traversal) were at the 2*i index for the left child and 2*i + 1 for the right child. The interviewer seemed more or less pleased, but I'm wondering what serialize means exactly? Does it specifically pertain to flattening the tree for writing to disk, or would serializing a tree also include just turning the tree into a linked list, say. Also, how would we go about flattening the tree into a (doubly) linked list, and then reconstructing it? Can you recreate the exact structure of the tree from the linked list?

推荐答案

所有这些文章都主要讨论序列化部分.反序列化部分很难一slightly而就.

All those articles talk mostly about the serialization part. The deserialization part is slightly tricky to do in one pass.

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

I have implemented an efficient solution for deserialization too.

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

序列化部分:

1. 使用0表示空值.
2. 使用顺序遍历序列化为整数列表.

反序列化部分:

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;
    }
}

这篇关于如何序列化二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！