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

鄒立鵬發布于2019-08-23 18:17 / 2367人閱讀

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

參考自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二叉樹的構建

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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