C语言实现序列化二叉树

1. 二叉树---->字符串

   ·思路：采用层序遍历的方案，使用队列，遍历每一个节点的左右孩子，左右孩子为空则字符为‘#’,否则保存节点值，并且使用队列保存节点。
   ·重点：字符串末尾添加结束符

2. 字符串--->二叉树 ·思路：使用两个指针进行遍历字符串，前一个指针指向节点，后一个指针分别指向左右孩子，每个循环，前一个指针一步，后一个指针两步。依次对前一个指针的所有孩子操作。这里我使用了一个节点数组，先初始化节点数组，然后对这个节点数组进行操作

   ·循环出口：后一个指针走完，说明创建结束

3. 重点：迷惑的点在于节点数组，使用struct TreeNode *nodes[100],初始化100个节点的数组指针，出错。并且需要注意指针赋值需要初始化。

4. 重点：二叉树转字符串 将二叉树节点值存放到字符里，根据题目，节点值范围0~150 ,一个char字符占据1个字节，可存储值：-128~128，当节点值大于128时，肯定会按照有符号存储，所以在读取字符串的时候，使用unsigned char 进行强制转换，这样就会按照无符号计算。

 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return char字符型一维数组
 */
char* Serialize(struct TreeNode* root ) {
    temp=root;
    // write code here 层序方式实现序列化
    if(root==NULL)
        return NULL;
    char* ans_str=(char *)malloc(sizeof(char)*100);    //初始化返回结果
    struct TreeNode *nodes[100];    //初始化100个节点的队列数组
    int node_top=0;//队列指示
    int pre_node=0,temp_node=0,ans_top=0;
    nodes[node_top++]=root;    //存放第一个节点
    ans_str[ans_top++]=root->val;
    while(pre_node<node_top){
        temp_node=node_top;
        //层序遍历
        for(;pre_node<temp_node;pre_node++){
        //空节点 记录'#'
            if(nodes[pre_node]->left==NULL)
                 ans_str[ans_top++]='#';
         //非空节点 入队列，记录值
            else
            {
                nodes[node_top++]=nodes[pre_node]->left;
                ans_str[ans_top++]=nodes[pre_node]->left->val;
             
            }
            
            if(nodes[pre_node]->right==NULL)
                 ans_str[ans_top++]='#';
            else{
                nodes[node_top++]=nodes[pre_node]->right;
                ans_str[ans_top++]=nodes[pre_node]->right->val;
            }
                 
        }
    }
    //结尾 结束符
    ans_str[ans_top++]='\0';
    return ans_str;  
}
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str char字符型一维数组 
 * @return TreeNode类
 */
struct TreeNode* Deserialize(char* str ) {
    if(str==NULL)
        return NULL;
    //初始化1000个节点指针数组
    struct TreeNode *nodes[100];
    int pre_flag=0,len=strlen(str),end_flag=1;
    //根据字符串 循环初始化所有节点 
    for(int i=0;i<len;i++){
        nodes[i]=(struct TreeNode *)malloc(sizeof(struct TreeNode));
        if(str[i]!='#')
        //这里 注意使用unsigned char转换
            nodes[i]->val=(unsigned char)str[i];
        nodes[i]->left=NULL;
        nodes[i]->right=NULL;
    }
    //快指针 遍历最后作为出口
    while(end_flag<len){
    //慢指针的左孩子
        if(str[end_flag]!='#')
            nodes[pre_flag]->left=nodes[end_flag];
        end_flag++;
    //慢指针的右孩子
        if(str[end_flag]!='#')
            nodes[pre_flag]->right=nodes[end_flag];
        end_flag++;
        pre_flag++;
        
    }
    return nodes[0];
}