想要将二叉树保存到磁盘上"20问题"游戏

Question

简而言之,我想学习/开发一种优雅的方法来将二叉树保存到磁盘(一般树,不一定是BST).这是我的问题的描述:

我正在实施一个"20个问题"的游戏.我写了一个二叉树,其内部节点是问题,叶子是答案.如果有人对你当前的问题回答"是",那么节点的左子节点就是你要遵循的路径,而正确的孩子则是"否"的答案.请注意,这不是二叉搜索树,只是一个二叉树,其左子节点为"是",右侧为"否".

如果通过要求用户将她的答案与计算机所考虑的答案区分开来,该程序遇到一个空的叶子,该程序会向树中添加一个节点.

这很简洁,因为树会在用户播放时自行构建.什么不整洁是我没有一个很好的方法将树保存到磁盘.

我已经考虑过将树保存为数组表示(对于节点i,左边的子节点是2i + 1,右边是2i + 2,父节点是(i-1)/ 2),但它不干净,我最终得到了浪费了很多空间.

有关将稀疏二叉树保存到磁盘的优雅解决方案的任何想法？

Answer 1

我会做一个Level-order遍历.也就是说你基本上都在做一个广度优先的搜索算法.

你有:

1. 创建一个插入根元素的qeueue
2. 从队列中取出一个元素,称之为E
3. 将E的左右子项添加到队列中.如果没有左或右,只需放置一个空节点表示.
4. 将节点E写入磁盘.
5. 从第2步开始重复.

级别顺序遍历序列:F,B,G,A,D,I,C,E,H

你将存储在磁盘上的内容:F,B,G,A,D,NullNode,I,NullNode,NullNode,C,E,H,NullNode

从磁盘加载它更容易.只需从左到右阅读存储到磁盘的节点.这将为您提供每个级别的左右节点.即树将从上到下从左到右填充.

第1步阅读:

F

第2步阅读:

  F 
B

第3步阅读:

  F 
 B  G

第4步阅读:

   F 
 B  G
A

等等 ...

注意:一旦有了NULL节点表示,就不再需要将其子节点列入磁盘.加载后,您将知道跳到下一个节点.因此,对于非常深的树,这种解决方案仍然是有效的.

Answer 2

您可以递归存储它:

 void encodeState(OutputStream out,Node n) {
        if(n==null) {
            out.write("[null]");
        } else {
           out.write("{");
           out.write(n.nodeDetails());
           encodeState(out, n.yesNode());
           encodeState(out, n.noNode());
           out.write("}");
        }
  }

设计自己较少的texty输出格式.我确信我不需要描述读取结果输出的方法.

这是深度优先遍历.广度优先也有效.