data-structures - 想要为 "20 questions"游戏将二叉树保存到磁盘

Question

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

我正在实现一个“20 个问题”的游戏。我写了一个二叉树，它的内部节点是问题，叶子是答案。如果有人对您当前的问题回答"is"，则节点的左 child 是您要遵循的路径，而右 child 是“否”答案。请注意，这不是二叉搜索树，只是一棵二叉树，其左 child 是"is"，右 child 是“否”。

该程序通过要求用户将她的答案与计算机正在考虑的答案区分开来，如果遇到一个为空的叶子，则该程序将一个节点添加到树中。

这很巧妙，因为树会随着用户的游戏而自行构建。不整洁的是我没有将树保存到磁盘的好方法。

我想过将树保存为数组表示(对于节点 i，左子节点为 2i+1，右子节点为 2i+2，父节点为 (i-1)/2)，但它不干净，我最终得到浪费了很多空间。

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

Answer 1

您可以递归存储它:

 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("}");
        }
  }

设计您自己的文本较少的输出格式。我确定我不需要描述读取结果输出的方法。

这就是深度优先遍历。广度优先也适用。