(手动)序列化和反序列化二进制搜索树

本文关键字：反序列化 二进制 搜索树 序列化 手动 | 更新日期: 2023-09-27 18:23:52

我已经使用标准方法在C#中实现了二进制搜索树。

完整的代码在这里

我不知道如何使用自定义方法来做到这一点如何使用C#手动完成此操作

(手动)序列化和反序列化二进制搜索树

我不明白为什么不使用一些标准（反）序列化技术（BinaryFormatter、XmlSerializer、数据契约、协议缓冲区）？

但如果你真的想使用链接中给出的方法，文章的要点可以总结为：

一个简单的解决方案是存储Inorder和Preorder遍历。此解决方案需要的空间是二进制树大小的两倍。

当以这种方式表示时，必须为空节点使用"dummy"值。由于链接文章的作者使用树来存储整数，因此他选择对空节点使用"特殊"-1值。

但是，如果不是以这种方式在内部存储树（我认为您使用的是链表），那么添加这些伪值就没有意义了。如果您存储的是普通的C#对象，那么null值可以清楚地描述一个空节点。

如果您的意图是将C++完全移植到C#，那么序列化方法将如下所示：

// This function stores a tree in a file pointed by fp
void Serialize(Node root, StreamWriter writer)
{
    // If current node is NULL, store marker
    if (root == null)
    {
        writer.Write("{0} ", MARKER);
        return;
    }
    // Else, store current node and recur for its children
    writer.Write("{0} ", root.key);
    Serialize(root.leftc, writer);
    Serialize(root.rightc, writer);
}

但这对于您的树来说是非常具体的，因为它只适用于简单的键（在您的情况下是整数），而且它在空间/速度方面不是很高效。

在将二进制数据写入文件（或流）时，需要为null放置一些"标记"（指示符）（与XML相比，XML中有一个自然的"缺失"元素/属性）。它可以是任何东西，最自然的是bool，代表类似于Nullable<T>.HasValue的东西，但对于Node参考，比如这个

class ObjectPersistence
{
    public void StoreBSTToFile(BST bst, string TreeStoreFile)
    {
        using (var writer = new BinaryWriter(File.Create(TreeStoreFile)))
            WriteNode(writer, bst.root);
    }
    public BST ReadBSTFromFile(string TreeStoreFile)
    {
        using (var reader = new BinaryReader(File.OpenRead(TreeStoreFile)))
            return new BST { root = ReadNode(reader) };
    }
    private static void WriteNode(BinaryWriter output, Node node)
    {
        if (node == null)
            output.Write(false);
        else
        {
            output.Write(true);
            output.Write(node.key);
            WriteNode(output, node.leftc);
            WriteNode(output, node.rightc);
        }
    }
    private static Node ReadNode(BinaryReader input)
    {
        if (!input.ReadBoolean()) return null;
        var node = new Node();
        node.key = input.ReadInt32();
        node.leftc = ReadNode(input);
        node.rightc = ReadNode(input);
        return node;
    }
}
相关文章：