想要将二进制树保存到磁盘以用于"20个问题".游戏 [英] Want to save binary tree to disk for "20 questions" game

问题描述

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

In short, I'd like to learn/develop an elegant method to save a binary tree to disk (a general tree, not necessarily a BST). Here is the description of my problem:

我正在实施一个"20个问题"的游戏.我已经写了一个二叉树，其内部节点是问题，叶子是答案.如果有人对您当前的问题回答是"，则节点的左侧孩子是您要遵循的路径，而右侧孩子则是否"答案.请注意，这不是二叉树 search ，而是一棵二叉树，其左子节点为"yes"，右子节点为"no".

I'm implementing a game of "20-questions". I've written a binary tree whose internal nodes are questions and leaves are answers. The left child of a node is the path you'd follow if somebody answered "yes" to your current question, while the right child is a "no" answer. Note this is not a binary search tree, just a binary tree whose left child is "yes" and right is "no".

如果程序遇到一个叶子为零的节点，则该程序会通过要求用户将其答案与计算机所考虑的答案区分开来，从而将该节点添加到树中.

The program adds a node to a tree if it encounters a leaf that is null by asking the user to distinguish her answer from the one the computer was thinking of.

这很整洁，因为树在用户玩耍时会自行建立.并非整洁的是，我没有将树保存到磁盘的好方法.

This is neat, because the tree builds itself up as the user plays. What's not neat is that I don't have a good way of saving the tree to disk.

我已经考虑过将树保存为数组表示形式(对于节点i，左子节点为2i + 1，右子节点为2i + 2，对父节点为(i-1)/2)，但它并不干净，我最终会浪费很多空间.

I've thought about saving the tree as an array representation (for node i, left child is 2i+1, and 2i+2 right, (i-1)/2 for parent), but it's not clean and I end up with a lot of wasted space.

有什么想法可以将稀疏的二叉树保存到磁盘吗?

Any ideas for an elegant solution to saving a sparse binary tree to disk?

推荐答案

您可以递归存储:

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

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

Devise your own less texty output format. I'm sure I don't need to describe the method to read the resulting output.

这是深度优先遍历.广度优先也是如此.

This is depth-first traversal. Breadth-first works too.

这篇关于想要将二进制树保存到磁盘以用于"20个问题".游戏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！