将二叉树保存到文件

Question

我有一个非平衡(非二进制搜索)二叉树需要将其编码(以后解码)到txt文件.我怎样才能以有效的方式做到这一点？

我发现这个链接 谈论类似(相同)的问题,但对我来说很明显

Answer 1

请在LeetCode上查看.

我喜欢这个解决方案,因为它相对有效并产生光输出文件.

假设你有一棵这样的树:

    _30_ 
   /    \    
  10    20
 /     /  \ 
50    45  35

此解决方案允许您将其序列化为此类输出文本文件:

30 10 50 # # # 20 45 # # 35 # #

要做到这一点,它足以通过树执行简单的预订遍历:

void writeBinaryTree(BinaryTree *p, ostream &out) {
  if (!p) {
    out << "# ";
  } else {
    out << p->data << " ";
    writeBinaryTree(p->left, out);
    writeBinaryTree(p->right, out);
  }
}

如您所见,#符号用于表示空节点.

要将此字符串反序列化为树,您可以使用:

void readBinaryTree(BinaryTree *&p, ifstream &fin) {
  int token;
  bool isNumber;
  if (!readNextToken(token, fin, isNumber)) 
    return;
  if (isNumber) {
    p = new BinaryTree(token);
    readBinaryTree(p->left, fin);
    readBinaryTree(p->right, fin);
  }
}

正如我之前所说,此方法生成二进制树的轻量级表示.

当然它有一个严重的缺点:它需要一个符号来表示空节点.

如果树的节点是可以包含此符号本身的字符串,则可能会导致潜在问题.