二叉查找树的编码与解码

53 阅读 0 评论 35 点赞

我是靠谱客的博主迷人香氛，最近开发中收集的这篇文章主要介绍二叉查找树的编码与解码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

把一个二叉树转换为字符串，再能把这个字符串转回原二叉树。

对二叉查找树进行前序遍历，将遍历得到的结果按顺序重新构造为一棵新的二叉查找树，新的二叉查找树与原二叉查找树完全一样。

二叉查找树编码为字符串：

将二叉查找树前序遍历，遍历时将整型的数据转为字符串，并将这些字符串数据进行连接，连接时使用特殊符号分隔

//       8
//      / 
//     3   10
//    /     
//   1  6     15
//
//  8#3#1#6#10#15#

将字符串解码为二叉查找树：

将字符串按照编码时的分隔符#，将各个数字逐个拆分出来，将第一个数字构建为二叉查找树的根结点，后面各个数字构建出的结点按解析时的顺序插入根结点中，返回根结点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    //将整型数字转换成string
    void change_int_to_str(int val,string& str_val)
    {
        string tmp;
        while(val)
        {
            tmp +=  (val%10 +'0');
            val = val/10;
        }
        for(int i = tmp.size()-1;i>=0;--i)//因为是从个位开始添加到str的，所以逆序
            str_val +=tmp[i];
        str_val +='#';//加一个特殊符号分隔
    }
    //前序遍历,将树编码成了字符串
    void preorder(TreeNode* node,string& data)
    {
        if(!node)
            return;
        string str_val;
        change_int_to_str(node->val,str_val);
        data += str_val;//每转换了一个数字，就把它添加到字符串后
        preorder(node->left,data);
        preorder(node->right,data);
    }
    
    
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string data;
        preorder(root,data);
        return data;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.size() == 0)
            return nullptr;
        
        vector<TreeNode*> node_vec;//将字符串中的数字转为结点后存在这数组里
        
        int val = 0;
        for(int i = 0;i < data.size();++i)
        {
            if(data[i] == '#')
            {
                node_vec.push_back(new TreeNode(val));
                val = 0;
            }else
                val = val * 10 + data[i] -'0';                
        }
        
        for(int i = 1;i<node_vec.size();++i)
            BST_insert(node_vec[0],node_vec[i]);
        
        return node_vec[0];
    }
    
    void BST_insert(TreeNode* root,TreeNode* node)
    {
        if(node->val < root->val)
        {
            if(root->left)
                return BST_insert(root->left,node);
            else
                root->left = node;
        }else{
            if(root->right)
                return BST_insert(root->right,node);
            else
                root->right = node;
        }
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));