首页 > 二叉树：二叉搜索树的编码和解码

二叉树：二叉搜索树的编码和解码

二叉搜索树的编码和解码描述：

编码：即将一个二叉搜索树编码，节点数值转换为字符串

解码：即将一个字符串解码，数值转换为对应的二叉搜索树的节点

过程导图如下：

在这里插入图片描述

针对性编码实现如下:

/*数字转字符串*/
void change_num_to_string(int val, string &tmp) { string buf;while(val) { buf += val % 10 + '0';val /= 10; }for (int i = buf.length() - 1;i >= 0; i--) { tmp += buf[i];}tmp += '#';
}
/*先序遍历，进行编码，最终结果放入buf中*/
void code_tree(Tree *node, string &buf) { if (node == NULL) { return;}string s;change_num_to_string(node -> data, s);buf.append(s);code_tree(node -> left, buf);code_tree(node -> right, buf);
}

编码之后的string buf内容类似8#3#2#1#9#20#

针对编码的string buf进行解码实现如下:

/*创建二叉搜索树*/
void create_tree(TreeNode *node, Tree *insert) { if ((*node) -> data > insert -> data) { if ((*node) -> left) { create_tree(&(*node) ->left,insert);} else { (*node) -> left = insert;}} else { if ((*node)  -> right) { create_tree(&(*node) ->right, insert);} else { (*node)  -> right = insert;}}
}
/*解码*/
TreeNode *decode_tree(string s) { int result = 0;std::vector<Tree *> node_arr;/*字符串转数字*/for (int i = 0;i < s.size(); ++i) { if (s[i] != '#') { result = 10 * result + (s[i] - '0');} else { Tree *node = (Tree *)malloc(sizeof(tree));node -> data = result;node_arr.push_back(node);result = 0;}}/*创建二叉树*/for (int i = 1;i < node_arr.size(); ++i) { create_tree(&node_arr[0], node_arr[i]);}return &node_arr[0];
}

最终解码输出为一个完整的二叉树

8
----3
--------2
------------1
----9
--------20

更多相关：

  • 二叉树：二叉搜索树的创建和插入

    二叉搜索树又名二叉排序树。 大概简略的思维导图如下，方便记忆特性 基本二叉搜索树创建过程如下 /*数据结构如下*/ typedef struct tree {int data;struct tree *left = NULL;struct tree *right = NULL; }Tree,*TreeNode;/*Node 为二...

  • Linux安装Nodejs

    Linux安装Nodejs 　　 　　　阿里云镜像： https://npm.taobao.org/mirrors/node/ 选择所需版本，进行下载。 　　　我这边下载的是：https://npm.taobao.org/mirrors/node/v8.2.1/node-v8.2.1-linux-x64.tar.gz  　　　 　　　...

  • Hadoop自学笔记（二）HDFS简单介绍

    1. HDFS Architecture 一种Master-Slave结构。包括Name Node, Secondary Name Node,Data Node Job Tracker, Task Tracker。JobTrackers: 控制全部的Task Trackers 。这两个Tracker将会在MapReduce课程里...

  • Sublime Text3配置Node.js开发环境

    下载Nodejs插件，下载zip压缩包后解压链接: http://pan.baidu.com/s/1hsBk60k 密码: jrcv打开Sublime Text3，点击菜单“首选项（N）” =>“浏览插件（B）”打开“Packages”文件夹，并将第1部的Nodejs文件夹剪切进来打开文件“Nodejs.sublime-build”，...

  • OC字符串转C语言字符串

            NSString * str = @"123";char buf[20];[str getCString:buf maxLength:20 encoding:NSASCIIStringEncoding];NSLog(@"%s",buf); 转载于:https://blog.51cto.com/8947509/1...

  • sscanf

    sscanf 目录 名称:函数原型:头文件：说明：支持集合操作：例子： 编辑本段名称: 　　sscanf() - 从一个字符串中读进与指定格式相符的数据. 编辑本段函数原型: 　　Int sscanf( const char *, const char *, ...); 　　int scanf( const char...

  • des vue 双倍长 解密_3DES双倍长加密 - osc_ojx9hm4t的个人空间 - OSCHINA - 中文开源技术交流社区...

    importjava.security.SecureRandom;importjavax.crypto.Cipher;importjavax.crypto.SecretKey;importjavax.crypto.SecretKeyFactory;importjavax.crypto.spec.DESKeySpec;//结果与DES算...

  • 剑指offer：面试题05. 替换空格

    题目：替换空格 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 输入：s = "We are happy." 输出："We%20are%20happy." 限制： 0 <= s 的长度 <= 10000 解题： 时间复杂度：O(n) 空间复杂度：O(n) class Solution { public:s...

  • c++ to_string用法

    在C++11标准库中，string.h已经添加了to_string方法，方便从其他类型（如整形）快速转换成字面值。 例如： for (size_t i = 0; i < texArrSize; i++)RTX_Shader.SetInt(string("TexArr[") + to_string(i) + "]", 7 + i);...

  • Ubuntu 14.04 64位字体美化(使用文泉驿微黑)

    Ubuntu 14.04安装并升级之后，变成楷体字体非常难看，我昨天搞了一晚上，终于理了个头绪，这里整理一下。 经过网上调研，大家的一致看法是，使用开源字体库文泉驿的微黑字体效果比较理想，甚至效果不输windows平台的雅黑字体。下面我打算微黑来美化Ubuntu 14.04. 1.安装文泉驿微黑字体库 sudo aptitude...

  • 关于std::string 在 并发场景下 __grow_by_and_replace free was not allocated 的异常问题

    使用string时发现了一些坑。 我们知道stl 容器并不是线程安全的，所以在使用它们的过程中往往需要一些同步机制来保证并发场景下的同步更新。 应该踩的坑还是一个不拉的踩了进去，所以还是记录一下吧。 string作为一个容器，随着我们的append 或者 针对string的+ 操作都会让string内部的数据域动态增加，而动态增加的...

©2024 11GX.COM