Question

简言之，我想学习/开发一种优雅的方法来将二叉树保存到磁盘中（一个普通的树，不一定是BST）。以下是我的问题描述：

我正在实现一个“20个问题”的游戏。我写了一棵二叉树，其内部节点是问题，叶子是答案。一个节点的左子节点是如果有人回答“是”你当前的问题，你将会跟随的路径，而右子节点则是“否”答案。请注意，这不是一棵二分搜索树，只是一个左子节点是“是”，右子节点是“否”的二叉树。

如果程序遇到一个为空的叶子节点，它会通过询问用户区分她的答案和计算机想的答案来向树中添加一个节点。

这很整洁，因为用户玩游戏时树会自行建立。不整洁的是我没有一个好的方法将树保存到磁盘上。

我考虑将树保存为数组表示（对于节点 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("}");
        }
  }

设计自己的简洁输出格式。我相信我不需要描述如何阅读生成的输出。

这是深度优先遍历。广度优先遍历也可以。

Answer 2

我会进行层序遍历。也就是说，你基本上正在执行广度优先搜索算法。

你有：

Create a qeueue with the root element inserted into it
Dequeue an element from the queue, call it E
Add the left and right children of E into the queue. If there is no left or right, just put a null node representation.
write node E to disk.
Repeat from step 2.

将其翻译为中文： alt text

层序遍历序列：F，B，G，A，D，I，C，E，H

你将要存储的是：F、B、G、A、D、NullNode、I、NullNode、NullNode、C、E、H、NullNode。

从磁盘重新加载更容易。只需从左到右读取您存储到磁盘的节点即可。这将为您提供每个级别的左右节点。即，树将从上到下从左到右填充。

步骤一：阅读输入：

步骤2：读取中：

  F 
B

第三步阅读中：

  F 
 B  G

步骤4：读取中：

   F 
 B  G
A

等等......

注意：一旦您有了一个NULL节点表示，您就不需要再将其子节点列入磁盘。在加载回来时，您将知道跳到下一个节点。因此，对于非常深的树，此解决方案仍将是有效的。

Answer 3

一个简单的方法是遍历树，输出每个元素。然后要重新加载树，只需迭代您的列表，将每个元素插入回树中。如果您的树不是自平衡的，您可能希望以一种合理平衡的方式重新排序列表，以便最终的树是合理平衡的。

Answer 4

Not sure it s elegant, but it s simple and explainable: Assign a unique ID to each node, whether stem or leaf. A simple counting integer will do.

保存到磁盘时，遍历树，存储每个节点的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，直到可以填入这些值。

Answer 5

最任意简单的方式就是一个基本格式，可以用来表示任何图表。

<parent>,<relation>,<child>

抱歉，这个“ ie”没有上下文，无法翻译。可以再提供一些信息吗？

"Is it Red", "yes", "does it have wings" 
"Is it Red", "no" , "does it swim"

这里并没有太多的冗余，格式大多是人类可读的，唯一的数据重复是每个直接子节点都必须有其父节点的副本。

你真正需要注意的唯一一件事是不要不小心生成循环。

除非那是你想要的。

The problem here is rebuilding the tree afterwards. If I create the "does it have wings" object upon reading the first line, I have to somehow locate it when I later encounter the line reading "does it have wings","yes","Has it got a beak?"

这就是为什么我传统上只是在内存中使用图形结构，使用指针到处指向这样的东西。

[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 ]

然后，“子/父”连接仅是元数据。

Answer 6

在Java中，如果您要使一个类可序列化，您可以直接将类对象写入磁盘并使用输入/输出流读取它。

Answer 7

我会这样存储树：

<node identifier>
node data
[<yes child identfier>
  yes child]
[<no child identifier>
  no child]
<end of node identifier>

孩子节点只是上述递归实例的一部分。方括号中的位是可选的，四个标识符只是常量/枚举值。

Answer 8

这是使用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
 */

友情链接