JavaScript二叉树的序列化与反序列化

邹立鹏发布于2019-08-23 18:17 / 2291人阅读

摘要：参考自对称的二叉树公众号秘密花园如下二叉树按照前序遍历序列化出来的结果为反序列化按规定的字符串输出二叉树思路如果二叉树是一颗完全二叉树只需知道前序遍历即可重建在序列化二叉树时可以将空节点使用特殊符号存储起来这个就可以模拟一颗完全二叉树的前序

参考自ConardLi：《对称的二叉树》公众号： code秘密花园

如下二叉树:

按照前序遍历序列化出来的结果为: 8,6,5,#,#,7,#,#,6,7,#,#,5,#,#
反序列化:按规定的字符串输出二叉树

思路:
1.如果二叉树是一颗完全二叉树,只需知道前序遍历即可重建
2.在序列化二叉树时,可以将空节点使用特殊符号存储起来,这个就可以模拟一颗完全二叉树的前序遍历
3.在重建二叉树时,当遇到特殊符号当空节点进行处理

步骤1:模拟一个二叉树

const symmetricalTree = {
  val: 8,
  left: {
    val: 6,
    left: { val: 5, left: null, right: null },
    right: { val: 7, left: null, right: null }
  },
  right: {
    val: 6,
    left: { val: 7, left: null, right: null },
    right: { val: 5, left: null, right: null }
  }
}

步骤2:

//序列化
function Serialize(pRoot, arr = []) {
  if (!pRoot) {
    arr.push("#");
  } else {
    arr.push(pRoot.val);
    Serialize(pRoot.left, arr);
    Serialize(pRoot.right, arr);
  }
  return arr.join(",");
}

步骤3:

//反序列化
function Deserialize(str) {
  if (!str) {
    return null;
  }
  return deserialize(str.split(","));
}

function deserialize (arr) {
  let node = null;
  const current = arr.shift();
  if (current !== "#") {
    node = { val: current };
    node.left = deserialize(arr);
    node.right = deserialize(arr);
  }
  return node;
}

输出

console.log(Serialize(symmetricalTree));
console.log(Deserialize("8,6,5,#,#,7,#,#,6,7,#,#,5,#,#"));

结果如下:

8,6,5,#,#,7,#,#,6,7,#,#,5,#,#
{ val: "8",
  left:
   { val: "6",
     left: { val: "5", left: null, right: null },
     right: { val: "7", left: null, right: null } },
  right:
   { val: "6",
     left: { val: "7", left: null, right: null },
     right: { val: "5", left: null, right: null } } }

参考自ConardLi：《对称的二叉树》公众号： code秘密花园

云服务器 GPU云服务器二叉树的遍历二叉树的存储二叉树的存储结构 java二叉树的构建

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/104979.html

树和树的算法

摘要：树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式，为二叉树的节点个数。树和树的算法一、树 1.1 树的概念树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个...

RaoMeng 2019-08-19 11:08 评论0 收藏0
树和树的算法

摘要：树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式，为二叉树的节点个数。树和树的算法一、树 1.1 树的概念树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个...

PiscesYE 2019-07-30 17:45 评论0 收藏0
使用JavaScript完成二叉树的一些基本操作

摘要：另外，由于篇幅有限，本篇的重点在于二叉树的常见算法以及实现。常见的二叉树实现代码之前写过相关的文章，是关于如何创建及遍历二叉树的，这里不再赘述。同时我们注意到，在二叉树深度比较大的时候，我们光是比较左右是不够的。本篇为复习过程中遇到过的总结，同时也给准备面试的同学一份参考。另外，由于篇幅有限，本篇的重点在于二叉树的常见算法以及实现。常见的二叉树实现代码之前写过相关的文章，是关于如...

YPHP 2019-08-23 12:48 评论0 收藏0
推导二叉树的遍历结果

摘要：推导前序序列已知二叉树的中序序列是，后序序列是，求前序序列。二叉树的中序序列是按照左子树，根，右子树的顺序排列的，根将左子树的序列和右子树的序列分割在左右两边。推导前序序列已知二叉树的中序序列是ABCDEFG，后序序列是BDCAFGE，求前序序列。思路 showImg(https://segmentfault.com/img/bVW1es?w=723&h=431); 二叉树的后序...

joy968 2019-08-21 17:10 评论0 收藏0
数据结构与算法:二叉树算法

摘要：因此，根据题目给出的先序遍历和中序遍历，可以画出二叉树选参考数据结构与算法描述实现二叉树算法浅谈数据结构二叉树慕课网实现二叉树算法前端树控件腾讯软件开发面试题内容衔接上一章数据结构与算法:常见排序算法内容提要什么是树　　- 为什么使用树二叉树二叉查找树红黑树Ｂ、Ｂ＋树堆伸展树树可以点击链接感受下笔者用d3.js画的tree https://codepen...

Little_XM 2019-08-22 11:09 评论0 收藏0