二叉树应用_序列化二叉树

爱被打了一巴掌 2022-05-22 04:41 238阅读 0赞

题目：实现两个函数，实现序列化和反序列化二叉树。  
分析：我们可以从前序遍历和中序遍历序列构造出一个二叉树。我们可以先把一颗二叉树序列化成一个前序遍历序列和一个中序遍历序列，然后进行构造。但是这个思路有两个缺点，一个是要求两个序列中所有数据都读出后才能开始反序列化，另外要求不能有数值重复的节点。  
我们可以根据前序遍历的顺序来序列化二叉树，前序遍历是从根节点开始的。当在遍历二叉树碰到NULL指针时，将NULL换成一个特数字符，此外节点的数字之间要用一个特殊字符隔开。  
实现如下：

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };
    */
     void bulid_serialize(TreeNode *root,string &str)
     {
         if(root==NULL)
         {
             str+='#';
             return ;
         }
         str+=to_string(root->val);
         str+=',';
         bulid_serialize(root->left,str);
         bulid_serialize(root->right,str);
     }
     //字符串转成char*
     char*serialize(string &str)
     {
         string str;
         bulid_serialize(root,str);
         char* result=new char[str.size()+1];
         int i;
         for( i=0;i<str.size();++i)
         {
             result[i]=str[i];
         }
         result[i]='\0';
         return result;
     }
     //反序列化
    TreeNode *DeserializeCore(char **str) {
       if (**str == '#') {
           ++(*str);
           return nullptr;
       }
       int value = 0;
       while (**str != '\0' && **str != ',') {
           value = value * 10 + ((**str) - '0');
           ++(*str);
       }
       TreeNode *node = new TreeNode(value);
       if (**str != '\0') {
           ++(*str);
           node->left = DeserializeCore(str);
           node->right = DeserializeCore(str);
       }
       return node;
    }
    
    TreeNode* Deserialize(char *str) {
       return DeserializeCore(&str);
    }