0

究竟如何序列化 BST？以最有效的方式做到这一点的正确方法是什么？现在，这太笼统了，所以让我解释一下我的意思。

这是一些伪伪代码：

public int[] serialize(root){
    preorder traversal 
    convert node to binary representation
    add the binary representation to an array
    send array via stream
}

或者

public int serialize(root){
    preorder traversal 
    convert node to binary representation
    send the binary representation via stream
}

我的问题是——创建一个数组并发送它充满位，这有效吗？或者我应该跳过整个数组的想法，每次转换一个节点时，将其发送出去以反序列化它？也许这两种实现都是愚蠢的。任何帮助，将不胜感激。

4

4 回答 4

1

我建议你也看看谷歌协议缓冲区 https://developers.google.com/protocol-buffers/docs/overview

于 2012-08-21T02:24:52.577 回答
0

如果您所说的“流”是指 C++ iostream，它们已经以合理的大小缓冲，并且插入该缓冲区的成本非常低。标准库成熟；在自己的游戏中击败它非常困难。你需要可利用的细节来获得任何有价值的东西。那说：

您的输出缓冲区应该有多大（退化的情况是单元素缓冲区，即没有缓冲）取决于缓冲区刷新的开销。该开销将具有固定成本和与大小相关的成本——而不是给定缓存效应的简单线性成本。对于更昂贵的固定开销，更大的缓冲区有助于摊销固定费用。例如，如果缓冲区刷新可以触发零拷贝 I/O，那么缓冲所有较大的序列化可能会大大降低成本，但如果输出操作要复制源缓冲区，则缓冲区大小会减少大约四分之一当刷新的固定成本较低时，L1 缓存大小是一个不错的选择。

除非序列化所花费的时间将其置于关键路径上，否则这些都不重要，即使其成为用户正在等待的东西——对于这样的事情，除非您谈论数百万个以上的项目，否则很难产生。即使那样，如果您还没有研究过它，几乎可以肯定，您如何生成单个序列化比您选择的缓冲方案中的浪费更多——即使那样，也永远不要忘记您正在比赛的内容。是 I/O 带宽吗？通过低级压缩器发送您的序列化流可以比您预先做的任何事情轻松节省更多时间。

于 2013-01-25T18:46:51.620 回答
0

BST 只能在后序中序列化，因为前序和中序不是唯一的。

1) 预购中非唯一

      root                     root
    /     \                   / 
  left    right             left
                               \
                               right

2）按顺序不唯一

     1                 1
    /                   \    
   2                     2
于 2013-01-25T14:23:57.550 回答
0

这取决于树和数据类型。如果树中节点的顺序很重要，您需要存储足够的信息来重新创建它。如果它在数组中，您可以使用数组中的位置来重新创建结构

于 2012-08-21T02:24:58.267 回答