C++ binary search tree encoding and decoding

Serialize and deserialize binary search trees

Title [leetcode449]

Serialization is the process of converting a data structure or object into a series of bits so that it can be stored in a file or memory buffer, or transmitted over a network connection link for later reconstruction in the same or another computer environment.

Design an algorithm to serialize and deserialize binary search trees. There are no restrictions on how the serialization/deserialization algorithm works. You just need to make sure that the binary search tree can be serialized to a string, and that the string can be deserialized to the original binary search tree.

The encoded string should be as compact as possible.

Note: Do not use class members/global/static variables to store state. Your serialization and deserialization algorithms should be stateless.

ideas

①The binary search tree is encoded as a string:
Traverse the binary search tree in preorder, convert integer data into strings during traversal, and connect these string data, using special symbols to separate them.

How to insert a node, click: Basics of Binary Search Trees learn

②The string is decoded into a binary search tree:
The string is decomposed one by one according to the delimiter "#" during encoding, and then inserted into the root node of the binary search tree in the order of preorder traversal, and finally the root node is returned, that is, the decoding is completed.

The implementation code is as follows:

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string data;
        BST_preorder(root, data);
        return data;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.length() == 0){
	    	return NULL;
	    }
    	std::vector<TreeNode *> node_vec;
    	int val = 0;
    	for (int i = 0; i < data.length(); 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]); //insert node
    	}
    	return node_vec[0];
    }
private:
    void BST_insert(TreeNode *node, TreeNode *insert_node){
        if (insert_node->val < node->val){
            if (node->left){
                BST_insert(node->left, insert_node);
            }
            else{
                node->left = insert_node;
            }
        }
        else{
            if (node->right){
                BST_insert(node->right, insert_node);
            }
            else{
                node->right = insert_node;
            }
        }
    }

    void change_int_to_string(int val, std::string &str_val){
        std::string tmp;
        while(val){
            tmp += val % 10 + '0'; //add characters at the end
            val = val / 10;
        }
        for (int i = tmp.length() - 1; i >= 0; i--){
            str_val += tmp[i]; //Add to string in reverse order
        }
        str_val += '#';
    }

    void BST_preorder(TreeNode *node, std::string &data){
        if (!node){
            return;
        }
        std::string str_val;
        change_int_to_string(node->val, str_val);
        data += str_val;
        BST_preorder(node->left, data);
        BST_preorder(node->right, data);
    }
};

Thanks

The knowledge points and ideas in this chapter are provided by the relevant videos of Xiaoxiang Academy, which are learned and sorted out by myself. I hope that while deepening my memory, I can also provide you with more knowledge points about some algorithms.
Your likes, comments and collections are the greatest support and encouragement to me, thank you!

Tags: C++ Algorithm Binary tree string Binary Search

Posted by idire on Wed, 18 May 2022 13:53:33 +0300