成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

JavaScript二叉樹的序列化與反序列化

鄒立鵬 / 2371人閱讀

摘要：參考自對稱的二叉樹公眾號秘密花園如下二叉樹按照前序遍歷序列化出來的結(jié)果為反序列化按規(guī)定的字符串輸出二叉樹思路如果二叉樹是一顆完全二叉樹只需知道前序遍歷即可重建在序列化二叉樹時可以將空節(jié)點使用特殊符號存儲起來這個就可以模擬一顆完全二叉樹的前序

參考自ConardLi： 《對稱的二叉樹》 公眾號： code秘密花園

如下二叉樹:

      8
     / 
    6   6
   /   /
  5  7 7  5

按照前序遍歷序列化出來的結(jié)果為: 8,6,5,#,#,7,#,#,6,7,#,#,5,#,#
反序列化:按規(guī)定的字符串輸出二叉樹

思路:
1.如果二叉樹是一顆完全二叉樹,只需知道前序遍歷即可重建
2.在序列化二叉樹時,可以將空節(jié)點使用特殊符號存儲起來,這個就可以模擬一顆完全二叉樹的前序遍歷
3.在重建二叉樹時,當(dāng)遇到特殊符號當(dāng)空節(jié)點進(jìn)行處理

步驟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,#,#"));

結(jié)果如下:

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秘密花園

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/104979.html

相關(guān)文章

  • 樹和樹的算法

    摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時間復(fù)雜度額外空間復(fù)雜度的二叉樹的遍歷方式，為二叉樹的節(jié)點個數(shù)。 樹和樹的算法 一、樹 1.1 樹的概念 樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>=1）個有限節(jié)點組成一個...

    RaoMeng 評論0 收藏0

  • 樹和樹的算法

    摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時間復(fù)雜度額外空間復(fù)雜度的二叉樹的遍歷方式，為二叉樹的節(jié)點個數(shù)。 樹和樹的算法 一、樹 1.1 樹的概念 樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>=1）個有限節(jié)點組成一個...

    PiscesYE 評論0 收藏0

  • 使用JavaScript完成二叉樹的一些基本操作

    摘要：另外，由于篇幅有限，本篇的重點在于二叉樹的常見算法以及實現(xiàn)。常見的二叉樹實現(xiàn)代碼之前寫過相關(guān)的文章，是關(guān)于如何創(chuàng)建及遍歷二叉樹的，這里不再贅述。同時我們注意到，在二叉樹深度比較大的時候，我們光是比較左右是不夠的。 本篇為復(fù)習(xí)過程中遇到過的總結(jié)，同時也給準(zhǔn)備面試的同學(xué)一份參考。另外，由于篇幅有限，本篇的重點在于二叉樹的常見算法以及實現(xiàn)。 常見的二叉樹實現(xiàn)代碼 之前寫過相關(guān)的文章，是關(guān)于如...

    YPHP 評論0 收藏0

  • 推導(dǎo)二叉樹的遍歷結(jié)果

    摘要：推導(dǎo)前序序列已知二叉樹的中序序列是，后序序列是，求前序序列。二叉樹的中序序列是按照左子樹，根，右子樹的順序排列的，根將左子樹的序列和右子樹的序列分割在左右兩邊。 推導(dǎo)前序序列 已知二叉樹的中序序列是ABCDEFG，后序序列是BDCAFGE，求前序序列。 思路 showImg(https://segmentfault.com/img/bVW1es?w=723&h=431); 二叉樹的后序...

    joy968 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法:二叉樹算法

    摘要：因此，根據(jù)題目給出的先序遍歷和中序遍歷，可以畫出二叉樹選參考數(shù)據(jù)結(jié)構(gòu)與算法描述實現(xiàn)二叉樹算法淺談數(shù)據(jù)結(jié)構(gòu)二叉樹慕課網(wǎng)實現(xiàn)二叉樹算法前端樹控件騰訊軟件開發(fā)面試題 內(nèi)容銜接上一章 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法 內(nèi)容提要 什么是樹 　　- 為什么使用樹 二叉樹 二叉查找樹 紅黑樹 Ｂ、Ｂ＋樹 堆 伸展樹 樹 可以點擊鏈接感受下筆者用d3.js畫的tree https://codepen...

    Little_XM 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<