Python：如何保存二叉树？

Question

我在想怎么保存我之前创建的二叉树。有没有人知道怎么做？非常感谢。

附注：这里有一个关于如何实现二叉树的链接，我正在使用这段代码：http://code.activestate.com/recipes/286239-binary-ordered-tree/

Answer 1

你可以使用一个小型数据库（比如sqlite3）来保存数据的结构。

举个例子：

Node: {nodeId(PK), [leftChildId](FK), [rightChildId](FK)}
leftChildId, rightChildId references Node;

和Bruce的回答类似，你需要实现一个 save（保存）和 load（加载）功能。

Answer 2

二叉树有很多种类型，每种都有不同的规则，这些规则可以帮助我们更简单地进行反序列化。简单来说，就是遍历整棵树，按顺序输出每个节点，然后在重新创建的时候，从文件中读取这些信息，重新生成树的结构。

在每个节点上加一些标记可能会很有帮助，这些标记可以告诉我们这个节点是不是叶子节点（叶子节点是指没有子节点的节点）。这样的话，我们就能知道下一个元素是应该放在当前节点的下面还是上面。另外，你也可以设置一个标记来表示空节点，比如说有的节点左边有分支但右边没有，这样的情况就可以用这个标记来处理。

例如：

   A
 B   C
D E    F

可以表示为：

A B D - - E - - C - F - -

或者像这样：

A[B[D,E],C[-,F]] 

这让我想起了我大学时做的计算机科学作业。

Answer 3

一个简单的解决办法是：
- 扩展当前的类，增加一个 load 方法和一个 save 方法
- 给每个节点添加一个唯一的ID
- 实现一个从上到下的解析，并将每个节点保存到一个结构像这样的XML文件中

<node id="mynicelycrafteduniqueid">
    <data>...</data>
    <leftChild>childuniqueId</leftChild>
    <rightChild/> <!-- no right child -->
</node>

这样就完成了（前提是数据可以轻松序列化），第一个节点就是你的树的根节点。

别忘了施肥，这样你的树会更加茁壮美丽。