首页 > 代码库 > 二叉树的序列化与反序列化

二叉树的序列化与反序列化

一个二叉树被序列化为数组,如何反序列化,也就是如何从序列化好的一个数组恢复成二叉树?

在上一篇文章中讲述了如何将一个有序数组创建成一个二叉搜索树,那么如果将将一个儿茶搜索树序列化为一个有序数组,然后按照上面的方法在反序列化即可。对二叉搜索树进行中序遍历即可得到一个有序的数组,那么上篇文章已经完成了对二叉搜索树的序列化和反序列化。同时如果想将二叉搜索树的序列化和反序列化的结果通过文件读取,也是同样的道理。

设计一个算法,将一棵二叉搜索树(Binary Search Tree,BST)保存到文件中,需要能够从文件中恢复原来的二叉搜索树。注意算法的时空复杂度。

如果通过文件的话,我们使用中序遍历是不合适的,因为从文件读取时顺序读取的。但是先序遍历存放到文件,然后从文件中按照依序读取,是符合要求的。

void DeSerialize(int min,int max,int& val,BinTree*& root,ifstream& fin)
{
     int temp;
     if(val > min && val < max)
     {
          temp = val;
          root = new BinTree;
          root->right = NULL;
          root->left = NULL;
          root->value = http://www.mamicode.com/temp;>上面是对二叉搜索树的序列和反序列化的方法

因为二叉树与二叉搜索树的性质不同,所以不能简单的采用前面文章中的方法。不过,我们可以采用先序遍历的思想,只是在这里需要改动。为了能够在重构二叉树时结点能够插入到正确的位置,在使用先序遍历保存二叉树到文件中的时候需要把NULL结点也保存起来(可以使用特殊符号如“#”来标识NULL结点)。

假定二叉树如下所示:

    _30_
   /    \   
  10    20
 /     /  \
50    45  35

则使用先序遍历,保存到文件中的内容如下:

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

序列化二叉树

先序遍历的代码可以完成序列化二叉树的工作,不管你信不信,反正我是信了。代码如下:

void SerializeBinaryTree(BinTree *p, ostream &out)  //BinaryTree是二叉树结构体,typedef struct node BinaryTree.  
    {  
      if (!p) {  
        out << "# ";  
      } else {  
        out << p->data << " ";  
        SerializeBinaryTree(p->left, out);  
        SerializeBinaryTree(p->right, out);  
      }  
    }  

反序列化二叉树

从文件中读取二叉树结点并重构的方法与前面相似。采用先序遍历的思想每次读取一个结点,如果读取到NULL结点的标识符号“#”,则忽略它。如果读取到结点数值,则插入到当前结点,然后遍历左孩子和右孩子。

void readBinaryTree(BinTree *&p, ifstream &fin)   
    {  
      int token;  
      bool isNumber;  
      if (!readNextToken(token, fin, isNumber)) //readNextToken读取文件下一个值,如果是数字返回true,否则返回false  
        return;  
      if (isNumber) {  
        p = new BinTree;
        p->value = http://www.mamicode.com/toekn;         //newNode函数创建新结点,设定data为token,left和right初始化为NULL  >




二叉树的序列化与反序列化