想为“20个问题”游戏将二叉树保存到磁盘上

你可以递归地存储它:

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

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

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

我会进行一次级别顺序遍历。也就是说,你基本上是在做一个 Breadth-first search 算法。

您有:

1. 创建一个插入根元素的queue
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

从磁盘加载回它甚至更容易。只需从左到右读取存储到磁盘的节点。这将为您提供每个级别的左右节点。也就是说,这棵树将从左到右从上到下填充。

第一步阅读:

F

第二步阅读:

  F 
B

第三步:阅读:

  F 
 B  G

第四步:阅读:

   F 
 B  G
A

等等。..

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

实现这一点的一个简单方法是遍历树,输出每个元素。然后要重新加载树,只需迭代列表,将每个元素重新插入树中。如果你的树不能自我平衡,你可能想重新排序列表,使最终的树达到合理的平衡。

不确定它是否优雅,但它简单易懂: 为每个节点分配一个唯一的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可能是多余的,如下所示。你可以按身份把它们按顺序排列。

要从磁盘还原,请读取一行,然后将其添加到树中。您可能需要一个表或数组来保存引用的节点,例如,在处理节点1时,您需要跟踪2和3,直到您可以填写这些值。

最简单的方法就是使用一种基本格式来表示任何图形。

<parent>,<relation>,<child>

即:

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

没有 很 这里存在冗余,格式大多是人类可读的,唯一的数据重复是,它所拥有的每个直接子项都必须有一个父项的副本。

你唯一需要注意的是,你不会意外地产生循环;)

除非这是你想要的。

这里的问题是重建 树之后。如果我创建“does” 阅读时,它有翅膀的物体 第一行,我必须设法找到 当我后来遇到这条线时 阅读“它有吗 “翅膀”,“是的”,“它有喙吗?”?"

这就是为什么我传统上只在内存中使用图结构来处理指针无处不在的事情。

[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中,如果要使类可序列化,只需将类对象写入磁盘,然后使用输入/输出流将其读回即可。

我会这样存放这棵树:

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

其中子节点只是上述的递归实例。[]中的位是可选的,四个标识符只是常量/枚举值。

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