简而言之，我想学习/开发一种优雅的方法来将二叉树保存到磁盘（一般树，不一定是 BST）。这是我的问题的描述：
我正在实施一个“20 个问题”的游戏。我写了一棵二叉树，其内部节点是问题，叶子是答案。如果有人对您当前的问题回答“是”，则节点的左孩子是您要遵循的路径，而右孩子是“否”的答案。请注意，这不是二叉搜索树，只是左孩子为“是”而右孩子为“否”的二叉树。
如果程序遇到一个为空的叶子，程序会通过要求用户将她的答案与计算机正在考虑的答案区分开来，将一个节点添加到树中。
这很简洁，因为树会在用户播放时自行构建。不整洁的是我没有将树保存到磁盘的好方法。
我考虑过将树保存为数组表示形式（对于节点 i，左子节点为 2i+1，右节点为 2i+2，父节点为 (i-1)/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 节点表示，就不再需要将其子节点列出到磁盘。加载回来时，您将知道跳到下一个节点。所以对于非常深的树，这个解决方案仍然是有效的。
您可以递归地存储它：
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("}");
}
}
设计自己的文本较少的输出格式。我确定我不需要描述读取结果输出的方法。
这是深度优先遍历。广度优先也有效。
实现此目的的一种简单方法是在执行此操作时遍历输出每个元素的树。然后要重新加载树，只需遍历您的列表，将每个元素重新插入树中。如果您的树不是自平衡的，您可能需要重新排序列表，以使最终的树合理平衡。
不确定它是否优雅，但它简单易懂：为每个节点分配一个唯一的 ID，无论是茎还是叶。一个简单的计数整数就可以了。
保存到磁盘时，遍历树，存储每个节点 ID、“是”链接 ID、“否”链接 ID 以及问题或答案的文本。对于空链接，使用零作为空值。您可以添加一个标志来指示是问题还是答案，或者更简单地说，检查两个链接是否为空。你应该得到这样的东西：
1,2,3,"Does it have wings?"
2,0,0,"a bird"
3,4,0,"Does it purr?"
4,0,0,"a cat"
请注意，如果您使用顺序整数方法，则保存节点的 ID 可能是多余的，如此处所示。您可以按 ID 将它们排序。
要从磁盘恢复，请读取一行，然后将其添加到树中。您可能需要一个表或数组来保存前向引用的节点，例如在处理节点 1 时，您需要跟踪 2 和 3，直到您可以填写这些值。
我会像这样存储树：
<node identifier>
node data
[<yes child identfier>
yes child]
[<no child identifier>
no child]
<end of node identifier>
其中子节点只是上述的递归实例。[] 中的位是可选的，四个标识符只是常量/枚举值。
最随意的简单方式只是可以用来表示任何图形的基本格式。
<parent>,<relation>,<child>
IE：
"Is it Red", "yes", "does it have wings"
"Is it Red", "no" , "does it swim"
这里没有太多冗余，并且格式大多是人类可读的，唯一的数据重复是它拥有的每个直接孩子都必须有一个父母的副本。
您真正需要注意的唯一一件事是您不会意外生成循环；）
除非那是你想要的。
这里的问题是之后重建树。如果我在阅读第一行时创建了“它有翅膀”对象，那么当我后来遇到“它有翅膀”、“是的”、“它有喙吗？”这行时，我必须以某种方式找到它。
这就是为什么我传统上只使用内存中的图形结构来处理指针无处不在的事情。
[0x1111111 "Is It Red" => [ 'yes' => 0xF752347 , 'no' => 0xFF6F664 ],
0xF752347 "does it have wings" => [ 'yes' => 0xFFFFFFF , 'no' => 0x2222222 ],
0xFF6F664 "does it swim" => [ 'yes' => "I Dont KNOW :( " , ... etc etc ]
那么“子/父”连接只是元数据。
在java中，如果你要使一个类可序列化，你可以将类对象写入磁盘并使用输入/输出流将其读回。
这是使用 PreOrder DFS 的 C++ 代码：
void SaveBinaryTreeToStream(TreeNode* root, ostringstream& oss)
{
if (!root)
{
oss << '#';
return;
}
oss << root->data;
SaveBinaryTreeToStream(root->left, oss);
SaveBinaryTreeToStream(root->right, oss);
}
TreeNode* LoadBinaryTreeFromStream(istringstream& iss)
{
if (iss.eof())
return NULL;
char c;
if ('#' == (c = iss.get()))
return NULL;
TreeNode* root = new TreeNode(c, NULL, NULL);
root->left = LoadBinaryTreeFromStream(iss);
root->right = LoadBinaryTreeFromStream(iss);
return root;
}
在main()中，您可以执行以下操作：
ostringstream oss;
root = MakeCharTree();
PrintVTree(root);
SaveBinaryTreeToStream(root, oss);
ClearTree(root);
cout << oss.str() << endl;
istringstream iss(oss.str());
cout << iss.str() << endl;
root = LoadBinaryTreeFromStream(iss);
PrintVTree(root);
ClearTree(root);
/* Output:
A
B C
D E F
G H I
ABD#G###CEH##I##F##
ABD#G###CEH##I##F##
A
B C
D E F
G H I
*/
DFS 更容易理解。
*********************************************************************************
但是我们可以使用队列来使用级别扫描 BFS
ostringstream SaveBinaryTreeToStream_BFS(TreeNode* root)
{
ostringstream oss;
if (!root)
return oss;
queue<TreeNode*> q;
q.push(root);
while (!q.empty())
{
TreeNode* tn = q.front(); q.pop();
if (tn)
{
q.push(tn->left);
q.push(tn->right);
oss << tn->data;
}
else
{
oss << '#';
}
}
return oss;
}
TreeNode* LoadBinaryTreeFromStream_BFS(istringstream& iss)
{
if (iss.eof())
return NULL;
TreeNode* root = new TreeNode(iss.get(), NULL, NULL);
queue<TreeNode*> q; q.push(root); // The parents from upper level
while (!iss.eof() && !q.empty())
{
TreeNode* tn = q.front(); q.pop();
char c = iss.get();
if ('#' == c)
tn->left = NULL;
else
q.push(tn->left = new TreeNode(c, NULL, NULL));
c = iss.get();
if ('#' == c)
tn->right = NULL;
else
q.push(tn->right = new TreeNode(c, NULL, NULL));
}
return root;
}
在main()中，您可以执行以下操作：
root = MakeCharTree();
PrintVTree(root);
ostringstream oss = SaveBinaryTreeToStream_BFS(root);
ClearTree(root);
cout << oss.str() << endl;
istringstream iss(oss.str());
cout << iss.str() << endl;
root = LoadBinaryTreeFromStream_BFS(iss);
PrintVTree(root);
ClearTree(root);
/* Output:
A
B C
D E F
G H I
ABCD#EF#GHI########
ABCD#EF#GHI########
A
B C
D E F
G H I
*/