（手动）序列化和反序列化二叉搜索树

Question

我有implemented binary search tree in C# using standard approach.

完整代码为here

我不知道如何使用 custom approach 执行此操作。 如何使用 C# 手动完成此操作？

Answer 1

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

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

A simple solution is to store both Inorder and Preorder traversals. This solution requires requires space twice the size of Binary Tree.

以这种方式表示时，您必须对空节点使用 "dummy" 值。并且由于 the linked article 的作者使用树来存储整数，(s) 他选择对空节点使用 "special" -1 值。

但是如果您不是在内部以这种方式存储树（我假设您使用的是linked列表），那么添加这些就没有意义了虚拟值。如果您要存储纯 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);
}

但这对你的树来说是非常具体的，因为它只适用于简单的键（比如你的情况下的整数），而且它不是很 space/speed 有效。

Answer 2

将二进制数据写入文件（或流）时，您需要为 null 添加一些 "marker"（指示符）（与 XML 相比，您有一个自然的 "missing" element/attribute)。它可以是任何东西，最自然的是 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;
    }
}

（手动）序列化和反序列化二叉搜索树

(Manually) serialize and de-serialize a binary search tree

c#

algorithm

serialization

file

binary-search-tree