将二进制树保存到文件 [英] Saving a Binary tree to a file

问题描述

我有一个非平衡（非二进制搜索）二叉树
需要解码（和以后解码）到txt文件。
我如何以有效的方式做呢？

我发现这个 link
，其中涉及类似的（相同的）问题，但对我来说很明显

解决方案

请参阅 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）; 
} 
} 
  
 
 
如前所述，此方法生成一个轻量级表示的二叉树。
 
 
 
当然，它有一个严重的缺点：它需要一个符号来表示空节点。
 
 
 
如果树的节点是可以包含此符号本身的字符串，那么它可能会导致潜在的问题。
 
I have a non-balanced (not binary-search) binary tree
Need to incode (and later decode) it to txt file.
How can I do it in efficient way?

I found this link 
which talks about similar (same) problem,but it is obvious for me
解决方案
Please look at this on LeetCode.

I like this solution because it's relatively efficient and produces light output files.

Assuming that you've got a tree like this:
    _30_ 
   /    \    
  10    20
 /     /  \ 
50    45  35
This solution lets you serialize it to such an output text file:
30 10 50 # # # 20 45 # # 35 # #
To do this it's enough to perform simple pre-order traversal through the tree:
void writeBinaryTree(BinaryTree *p, ostream &out) {
  if (!p) {
    out << "# ";
  } else {
    out << p->data << " ";
    writeBinaryTree(p->left, out);
    writeBinaryTree(p->right, out);
  }
}
As you can see, a # symbol is used to represent the null node. 

To deserialize this string into a tree you can use:
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);
  }
}
As I said before, this method produces a lightweight representation of Binary Tree.

Of course it has one serious drawback: it requires a symbol to represent the null node.

It can cause potential problems if the nodes of tree are strings that can contain this symbol itself.

                        
这篇关于将二进制树保存到文件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！