将二叉树保存到文件中

  • Z时代
  • 2024-01-10
  • 分类：问答

我有一个非平衡（非二分查找）的二叉树，需要对其进行编码（以后再解码）为txt文件。如何有效地做到这一点？

回答：

请在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);
  }
}

就像我之前说的那样，此方法产生了二进制树的轻量表示形式。

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

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

以上是 将二叉树保存到文件中 的全部内容， 来源链接： utcz.com/qa/431506.html

回到顶部