专栏首页书山有路勤为径二叉查找树编码与解码

二叉查找树编码与解码

LeetCode 449 给定一个二叉查找树,实现对该二叉查找树编码与解码功能。编码即将二叉查找树转为字符串,解码即将字符串转为二叉查找树。不限制使用何种编码算法,只需保证当对二叉查找树调用编码功能后可再调用解码功能将其复原。

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode * right;
    TreeNode(int x) : val(x),left(NULL),right(NULL){}
};
class Codec{
public:
    string serializer(TreeNode *root){}
    TreeNode * deserialize(string data){}
};
预备知识:二叉查找树前序遍历与复原

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

//对二叉树进行前序遍历,将遍历得到的节点收集到node_vec中。
void collect_nodes(TreeNode * node, std::vector<TreeNode *> & node_vec){
    if(!node){
        return;
    }
    node_vec.push_back(node);
    collect_nodes(node->left, node_vec);
    collect_nodes(node->right, node_vec);
}
int main(){
    TreeNode a(8);
    TreeNode b(3);
    TreeNode c(10);
    TreeNode d(1);
    TreeNode e(6);
    TreeNode f(15);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.right = &f;
    std::vector<TreeNode *> node_vec;
    collect_nodes(&a, node_vec);
    for(int i =0; i < node_vec.size(); i++){
        node_vec[i] -> left = NULL;
        node_vec[i] -> right = NULL;
    }
    for(int i =1; i < node_vec.size(); i++){
        BST_insert(node_vec[0], node_vec[i]);
    }
    preorder_print(node_vec[0], 0);
    return 0;

}
算法思路(解码)

将字符串解码为二叉查找树: 将字符串按照编码时的分隔符“#”,将各个数字诸葛拆分出来,将第一个数字构建为二叉查找树的根节点,后面各个数字构建出的节点按解析时的顺序插入根节点中,返回根节点,即完成解码操作。

整型转为字符串(编码阶段)

利用对整数10取余,可以逐个循环的将一个整数从最低位到最高位拆分出来,在这个过程中每取出一个最低位,就将该数字除以10。每拆分出一个字符,就将这个字符添加到string中,直到该数字为0结束。最后将 string进行反转,就完成了整数转字符串。

void change_int_to_string(int val, std::string &str_val){
    std:string tmp;
    while(val){
        tmp += val % 10 + '0';
        val = val / 10;
    }
    for(int i = tmp.length() -1; i > = 0; i--){
        str_val += tmp[i];
    }
    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);
}
字符串拆分为整数(解码阶段)
#include<stdio.h>
#include<string>
int main(){
    std::string str = "123#456#10000#1#";
    int val = 0;
    for(int i = 0 ; i < str.length(); i++){
        if(str[i] == '#'){
            printf("val = %d\n", val);
            val = 0;
        }
        else{
            val = val * 10 + str[i] - '0';
        }
    }
    return 0;
}
练习
class Codec{
public:
    std::string serialize(TreeNode * root){
        std::string data;
        BST_preorder(root, data);//将root指向的树转为字符串data
    }
    TreeNode *deserialize(std::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]);
        }
        return node_vec[0];
    }
}
测试
int main(){
    TreeNode a(8);
    TreeNode b(3);
    TreeNode c(10);
    TreeNode d(1);
    TreeNode e(6);
    TreeNode f(15);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.left = &f;
    Codec solve;
    std::string data = solve.serialize(&a);
    printf("%s\n", data.c_str());
    TreeNode * root = solve.deserialize(data);
    preorder_print(root, 0);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • k个排序链表的合并

    LeetCode 23. Merge k Sorted Lists 已知k个已排序链表头节点指针,将这k个链表合并,合并后仍为有序的,返 回合并后的头节点。

    小飞侠xp
  • 排序数组转换为二叉查找树

    已知一个排序的数组,将该数组转换为一个高度平衡的二叉查找树。 平衡的定义: 二叉查找树中,任意节点的两颗子树高度差不超过1. LeetCode 108

    小飞侠xp
  • 二叉查找树

    二叉查找树是一种数据结构,它是具有以下性质的二叉树: 1.若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值; 2.若右子数不空,则右子树上所有...

    小飞侠xp
  • akka-grpc - 应用案例

    上期说道:http/2还属于一种不算普及的技术协议,可能目前只适合用于内部系统集成,现在开始大面积介入可能为时尚早。不过有些项目需求不等人,需要使用这项技术,...

    用户1150956
  • 使用javafx框架tornadofx制作的成语字典小工具

    使用borderpane布局,left部分包括一个用于输入查寻关键字的文本框、查询清空按键和26个英文字母按钮,center部分一个tableview,显示查寻...

    用户6167008
  • 【翻译】忘了RxJava吧——你需要的是拥抱Kotlin协程(Part 1/2)

    2018-08-31 by Liuqingwen | Tags: Kotlin Android 翻译 | Hits

    IT自学不成才
  • SD-WAN领域16个热门网络产品

    新的SD-WAN产品闪亮登场 随着网络蓝图逐渐向软件定义的方式转变,厂商们都发布了新的产品旨在降低成本,提高网络自动化并提高效率。 解决方案提供商需要着眼于新的...

    SDNLAB
  • 数据库系统——B+树索引

    http://blog.csdn.net/cjfeii/article/details/10858721

    bear_fish
  • 【腾讯云Serverless】记一次使用腾讯云Serverless的VS Code插件来定位问题

    该库封装了微信公共平台消息接口,并将其作为中间件的形式,配合express,koa等框架使用。

    Juli
  • 数据整合和机器学习深入客户见解

    本文精选与新的DZone人工智能指南中。免费获取更有深度的文章,行业统计,以及更多!

    Lethe丶L

扫码关注云+社区

领取腾讯云代金券