序列化二叉树

题目

　　请实现两个函数，分别用来序列化和反序列化二叉树

 思路

　　根据先序遍历得到二叉树的序列，把结点为空的值用特殊数字代替，存入queue(原文使用流代替的，根据先进先出的思想，用队列也可实现)，然后重建二叉树的时候：

　　　　如果此节点不为空(nullptr)，递归建立左子树，递归建立右子树

#include <iostream>
#include <queue>
using namespace std;

struct tree
{
    double data;
    tree *left,*right;
    tree(int d=0):data(d)
    {
        left=right=nullptr;
    }
};
class Solution
{
    public:
        void create(tree *&root);
        void pre_order(tree *root);//中序遍历
        void serialize(tree *root,queue<int> &v);
        void de_seizlize(tree *&root,queue<int> &v);
        tree *root;    
};
void Solution::create(tree *&root)
{
    double x;
    cin>>x;
    if(x==0)
        root=nullptr;
    else
    {
        root=new tree();
        root->data=x;
        create(root->left);
        create(root->right);
    }
}
void Solution::pre_order(tree *root)
{
    if(root)
    {
        cout<<root->data<<endl;
        pre_order(root->left);
        pre_order(root->right);
    }
}
void Solution::serialize(tree *root,queue<int> &q)
{
    if(!root)
    {
        q.push(0x3f3f);
        return;
    }
    q.push(root->data);
    serialize(root->left,q);
    serialize(root->right,q);
}
void Solution::de_seizlize(tree *&root,queue<int> &q)
{
    int n=q.front();
    q.pop();
    if(n!=0x3f3f)
    {
        root=new tree();
        root->data=n;
        de_seizlize(root->left,q);
        de_seizlize(root->right,q);//这种方法也可以 
    }
    //这种方法也可以 
    /*if(root) 
    {
        de_seizlize(root->left,q);
        de_seizlize(root->right,q);
    }*/
}
int main()
{
    Solution s,s1;
    s.create(s.root);
    
    queue<int> q;
    s.serialize(s.root,q);
    s1.de_seizlize(s1.root,q);
    s1.pre_order(s1.root);
    return 0;
}