我已经使用标准方法在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;
}
}