二叉樹層序序列化與反序列化

二叉樹層序序列化與反序列化

二叉樹的正序列化：把二叉樹按照某種周遊方式的結果以某種格式儲存為字元串，進而使得記憶體中建立起來的二叉樹可以持久儲存。

序列化可以基于 先序、中序、後序、層序 的方式來進行周遊。

層序序列化要求：

1、從二叉樹的根節點開始，逐層周遊

2、資料之間使用逗号“,”隔開

3、樹的節點中，存在的節點将值（51、7、13等）存入數組中即可

4、結尾如果有不存在的節點，則全部忽略

根據規則，忽略掉結尾不存在的節點後，字元串應該為"51,7,13,5,26,17,9"

一、正序列化

根據要求我們可以看出是用層序排序法來序列化，推薦用隊列來存儲節點。

實作步驟：

1.首先我們先将樹的根節點（51）存入隊列

2.利用隊列先進先出原理取出根節點（51）

3.此時再存入根節點的左右子節點（左子節點：7，右子節點：13），那麼隊列中就有兩個節點（7，13）

4.此時我們再從隊列中取出目前根節點的左子節點（7），隊列中隻剩一個節點（13）

5.添加左子節點（7）的左右子節點（5，0），此時隊列中節點個數為三個（13，5，0，這裡空節點我們用0表示）

6.以此類推，直到所有節點都加入隊列，并從隊列中取出後，隊列中無任何節點

代碼示例

二叉樹的反序列化：從檔案或者數組中取出資料，重構二叉樹

二、反序列化

依然采用隊列來存儲我們想要的樹，再利用隊列特性一一取出并指派上符串相應的數值

實作步驟：

1.首先我們先定義一個樹并初始化節點數值為0

2.将根節點存入隊列

3.将隊列的第一個節點取出并指派

4.将根節點（51）的左右子節點放入隊列中

5.将根節點的左子（7）節點取出并指派，

6.加入節點（7）的左右子節點

7.以此類推，直到所有節點都加入隊列，并從隊列中取出後，隊列中無任何節點

代碼示例