前言
有一顆二叉樹，將它轉換成特定規則的字符串就稱之為序列化，將序列化后的字符串按照序列化時的規則還原成二叉樹就稱之為反序列化。
那么如何實現二叉樹與字符串之間的相互轉換呢？本文就跟大家分享下這個問題的解決方案，歡迎各位感興趣的開發者閱讀本文。
實現思路
在文章重建二叉樹中，我們學會了利用前序遍歷序列和中序遍歷序列將一個字符串構建成一顆二叉樹。這個思路有兩個缺點：
- 二叉樹中不能有數值重復的節點
- 只有當兩個序列中所有的數據都讀出來后才能開始反序列化（如果兩個序列中的數據都是從一個流里讀出來的，那么就需要等待比教長的時間）
其實，當我們用前序遍歷來讀取二叉樹時，得到的序列是從根節點開始的，那么反序列化時在根節點讀取出來之后就可以開始了。當我們在序列化的時候可能會遇到空節點，我們用一個特殊的字符來標記它（例如"$"）。節點值之間的連接也需要用特殊字符標記（例如","）。
序列化的規則捋清楚后，我們舉個例子來驗證下是否可行，如下所示（一顆二叉樹）：
根據上面定義的規則，我們使用前序遍歷得到的序列為：1,2,4,$,$,$,3,5,$,$,6,$,$。
經過驗證，上述方法成功的實現了樹的序列化。接下來我們以字符串1,2,4,$,$,$,3,5,$,$,6,$,$為例分析如何反序列化二叉樹。
第一個讀出的數字是1。由于前序遍歷是從根節點開始的，這是根節點的值。緊接著讀出的數字是2，根據前序遍歷的規則，這是根節點的左子節點的值。同樣的，接下來的數字4是值為2的節點的左子節點。
接著從序列化字符串里讀出兩個字符"$"，這表明節點4的左、右子節點均為空，因此它是一個葉節點。
接下來返回至節點2，重建它的右子節點。繼續讀取字符，下一個字符是"$"，這表明節點2的右子節點為空。這個節點的左、右子樹都已經構建完畢。
接下來返回至根節點，反序列化根節點的右子樹。
下一個序列化字符串中讀取出來的數字是3，因此根節點的右子樹的值為3。它的左子節點是一個值為5的葉節點，因為接下來的三個字符是"5,$,$"。
同樣，它的右子節點是值為6的葉節點，因為最后3個字符是"6,$,$"。
字符串中的所有字符已讀取完畢，序列化流程結束，樹也完成重建，如下圖所示（去掉了分析思路時所畫的輔助線）
實現代碼
經過前面的分析，我們已經得到了完整的思路，接下來我們來看下代碼的實現。
序列化二叉樹
我們利用前序遍歷即可完成二叉樹的序列化。
public serialize(root: BinaryTreeNode | null): string {
// 空節點用$表示
if (root == null) return "$";
const result: serializeNode = { nodeVal: "" };
this.serializeFn(root, result);
// 末尾會有多余的分隔符，將其去除
return result.nodeVal.substring(0, result.nodeVal.length - 1);
}
/**
* 處理樹序列化的實現函數
* @param root 樹的根節點
* @param strObj 序列化后的節點對象
* @private
*/
private serializeFn(
root: BinaryTreeNode | null | undefined,
strObj: serializeNode
) {
if (root == null) {
strObj.nodeVal += "$,";
return;
}
strObj.nodeVal += root.key + ",";
this.serializeFn(root.left, strObj);
this.serializeFn(root.right, strObj);
}反序列化
我們序列化的時候用的前序遍歷，同樣的在反序列化的時候也要使用前序遍歷。反序列的時候稍微麻煩些，需要先把字符串中的每個字符放到數組中。隨后再按照我們前面的分析：
- 定義一個全局變量across用來表示當前讀取到了第幾個字符（已走步長）
- 遞歸執行構建函數時，已走步長先自增。
- 根節點的左子樹一定是緊根其后的字符，所以從index+1位置開始繼續執行遞歸函數直至遇到"$"字符為止
- 根節點的右子樹一定是緊根在它左子樹之后的字符，所以從across位置開始繼續執行遞歸函數直至遇到"$"字符為止
- 構建函數接受兩個參數：字符數組、當前讀取的字符索引
- 從字符數組中讀取當前字符索引位置的值，構建根節點
- 左、右子樹都構建完畢后，將構建好的根節點返回就得到了一顆完整的樹
/**
* 反序列化二叉樹
* @param treeStr
*/
public deserialize(treeStr: string): BinaryTreeNode | null {
if (treeStr === "$") {
return null;
}
return this.deserializeFn(treeStr);
}
/**
* 處理樹的反序列化實現函數
* @param nodeStrVal 反序列化后的樹節點字符串
* @private
*/
private deserializeFn(nodeStrVal: string) {
// 讀取字符串的每一個字符，將其轉換為數組
const strArr: Array<string> = [];
let readIndex = 0;
while (readIndex < nodeStrVal.length) {
if (nodeStrVal.charAt(readIndex) !== ",") {
strArr.push(nodeStrVal.charAt(readIndex));
}
readIndex++;
}
// 反序列化二叉樹
return this.buildTree(strArr, 0);
}
/**
* 將字符串數組序列化為二叉樹
* @param str 字符串數組
* @param index 起始索引
* @private
*/
private buildTree(str: Array<string>, index: number) {
this.across++;
// 處理空節點（遞歸的基線條件）
if (str[index] === "$") return null;
// 構造樹節點
const treeNode: BinaryTreeNode = { key: parseInt(str[index]) };
// 當前節點的下一個節點一定為它的左子樹
treeNode.left = this.buildTree(str, index + 1);
// 左子樹遇到基線條件后，右子樹的索引就為已走步長
treeNode.right = this.buildTree(str, this.across);
return treeNode;
}
測試用例
我們用文章開頭所列舉的例子來驗證下上述代碼能否正確的解決問題。
const rootNode: BinaryTreeNode = {
key: 1,
left: {
key: 2,
left: {
key: 4
}
},
right: {
key: 3,
left: {
key: 5
},
right: {
key: 6
}
}
};
const serializedBinaryTree = new SerializedBinaryTree();
const treeStr = serializedBinaryTree.serialize(rootNode);
console.log("序列化后的字符串", treeStr);
const result = serializedBinaryTree.deserialize(treeStr);
console.log("反序列化后的樹", result);執行結果如下所示。
示例代碼
本文用到的代碼完整版請移步：
- SerializedBinaryTree.ts
- SerializedBinaryTree-test.ts
