前序列表告訴我們哪個節點先被訪問,但只有節點值列表未必能反映哪些子節點缺失。例如,只有左子節點的根與只有右子節點的根,可能有相同的前序值。為每個空子節點位置加入特殊空標記後,數據流便同時記錄了值與結構。
這個推導應用延伸了課程的二叉樹走訪與重建單元。
1. 編碼與明確格式
二叉樹有限且有序:左、右子節點位置不同。值可以重複。用特殊記號 # 表示空子樹,並假設它不會與任何編碼後的值記號混淆。遞歸序列化:
encode(node):
如果 node 為空:輸出 #;返回
輸出 VALUE(node.value)
encode(node.left)
encode(node.right)
VALUE(v) 是帶型別標記的值記號,不是可能與 # 混淆的普通字串。實際格式需要區分兩者,即使例子中簡寫成字母。空樹編碼為單個記號 #。
定義 4.3.1
(帶空標記的前序編碼)
對有限有序二叉樹 ,其帶空標記的前序編碼是記號序列 ,定義為 ;對值為 、左子樹為 、右子樹為 的節點,。第一個記號是根的值或空標記。
例題 4.3.2
(編碼缺少左子節點的樹)
例如,設 的左子節點為 、右子節點為 ,而 只有右子節點 ; 都是葉節點。編碼為
A B # D # # C # #
第一個 # 標記 缺失的左子節點;接下來兩個結束 ,最後兩個結束 。如果只是把空標記加到末尾,就無法保留缺失子節點的位置。
反例模式
只有值不能決定樹
一個誘人的說法是:前序值列表已足以決定樹。取 ,根為 且只有左子節點 ;以及 ,根為 且只有右子節點 。兩者的前序值都是 ,卻是不同的有序樹。加上空標記後, 編碼為 A B # # #, 編碼為 A # B # #:第一個空標記的位置記錄了缺少哪個子節點。補救辦法是在每個空子節點位置加入空標記。
2. 每次解碼一棵子樹
decodeOne(tokens, position):
如果 position == length(tokens):報錯「截斷」
token = tokens[position]; position += 1
如果 token == #:返回 (null, position)
如果 token 不是有效 VALUE:報錯「無效記號」
(left, position) = decodeOne(tokens, position)
(right, position) = decodeOne(tokens, position)
返回 (new node(token.value, left, right), position)
decodeTree(tokens):
(root, position) = decodeOne(tokens, 0)
如果 position != length(tokens):報錯「多餘記號」
返回 root
decodeOne 恰好消耗一棵完整子樹,並返回下一棵子樹的起始位置。非空記號首先確定根的值;下一棵完整子樹是左子樹,再下一棵是右子樹。空記號消耗一個位置,不產生子節點。外層檢查拒絕完整樹之後的多餘記號。實際實作若後續解析失敗,應釋放已分配的節點;上述偽程式碼規定結果,不規定特定語言的所有權策略。
定理 4.3.3
(解碼是編碼的逆運算)
對每棵有限有序二叉樹 ,decodeTree(encode(T)) 返回形狀和值都與 相同的樹。反過來,被 decodeTree 接受的每個記號數據流,都恰好是一棵這樣的樹的編碼,即使值重複也成立。
證明
(對樹歸納)
對編碼樹歸納可知,解碼器恰好消耗其編碼並重建根及兩個子節點。反過來,成功解碼的子樹的第一個記號決定它是否為空,或給出其根值;遞歸解析唯一決定每個子節點和記號邊界。因此,一個有效完整數據流恰好表示一棵有序樹,即使節點值重複也成立。
3. 用待填槽位數驗證結構
定義 4.3.4
(待填槽位與槽位數)
槽位是等待填入整棵子樹的位置。開始時根有一個槽位。每個記號填入一個槽位。空標記不建立新槽位,因此數量減 1;值記號建立兩個子槽位,因此淨變化為 。遇到無效記號則拒絕。若下一個記號到來之前槽位數已為零,也拒絕;只有恰好在末尾變為零才接受。空數據流的槽位數仍為 1,因此已截斷。
定理 4.3.5
(槽位計數恰好接受完整的數據流)
設數據流有 個記號,每個都是 # 或有效的值記號。令 ;若第 個記號是值,則 ,若是 #,則 。則 decodeTree 接受該數據流,當且僅當對每個 有 ,且 。
證明
(槽位即待處理的遞歸調用)
該條件既必要也充分。在每個前綴處,槽位對應前序遞歸中尚待調用的子樹。值把下一個待調用位置替換成兩個調用,左先右後;# 完成一個調用。正槽位數確保下一個記號有位置,末尾為零表示沒有待處理調用。因此完整數據流符合遞歸語法。槽位計數檢查結構,每個值記號仍須獨立符合其格式。
證明透視
槽位計數保留了甚麼?
計數記錄尚未填入的子樹位置有多少;它本身不保存節點值,也不能單獨重建樹的形狀。遞歸解析還依靠記號次序,先取完整左子樹,再取右子樹。只有此前沒有前綴提早耗盡所有槽位時,末尾為零才能證明數據流完整。
對於含 個真實節點的樹,空標記有 個。每個節點有兩個子節點位置,共 個;非空樹有 條真實子邊,所以空子節點位置為 。當 時,根槽位本身給出一個標記。完整數據流有 個記號。只有這個數量還不夠:# A # 有一個值和兩個標記,但第一個記號已完成根,後續記號多餘。
例題 4.3.6
(沿著編碼追蹤槽位數)
取編碼一節的數據流 A B # D # # C # #。計數從 1 開始,變化如下。
| 記號 | 變化 | 之後的槽位數 |
|---|---|---|
| 開始 | 1 | |
A | +1 | 2 |
B | +1 | 3 |
# | −1 | 2 |
D | +1 | 3 |
# | −1 | 2 |
# | −1 | 1 |
C | +1 | 2 |
# | −1 | 1 |
# | −1 | 0 |
每個記號之前計數都至少為 1,恰好在末尾為 0,所以數據流被接受,與解碼器一致。
例題 4.3.7
(邊界情況:空樹、單一節點與錯誤數據流)
數據流 # 的計數為 :被接受,解碼為空樹。數據流 A # # 的計數為 :只有一個沒有子節點的節點。數據流 A # 結束時計數為 1,所以解碼器在讀取右子節點時用盡記號,以「截斷」報錯。數據流 # A # 在第一個記號之後計數為 0,但仍剩兩個記號:decodeOne 在一個記號後返回空樹,decodeTree 發現位置 1 不等於長度 3,以「多餘記號」報錯。
常見錯誤
(數記號個數而不是數槽位)
記號總數 與空標記數 是必要條件,卻不充分。數據流 # A # 有三個記號、一個值和兩個空標記,符合 的數量,卻不是任何樹的編碼:第一個空標記已完成整棵樹,其餘記號是多餘的。槽位計數能發現這一點,因為第一個記號之後計數為 0,而記號仍有剩餘。
常見錯誤
(漏掉對多餘記號的檢查)
若 decodeTree 直接返回 decodeOne 的結果,而不比較 position 與長度,則 # A # 會被靜默解碼為空樹,兩個記號被忽略。解析出一棵完整子樹,並不等於解析了完整數據流。
4. 成本與限制
定理 4.3.8
(編碼、解碼與驗證的成本)
設樹有 個節點、高度為 (根到葉路徑上的最大真實節點數,空樹的 )。在記號操作為常數時間的模型下,編碼與解碼各需 時間,輸出或輸入含 個記號。遞歸堆疊使用 空間,鏈狀樹為 。只用槽位計數驗證需要 時間和 個範圍足夠的計數器(不計輸入儲存),並且不構造樹。
證明
(每步一個記號)
編碼器每次調用輸出一個記號,恰好調用 次:每個節點一次,每個空子節點位置一次。解碼器每次調用至少消耗一個記號,每個記號對應一次調用。遞歸深度至多比高度多一。驗證器只讀取每個記號一次,並保持一個計數器。
這些界假設值符合常數時間記號模型;複製可變長度的值還需計入其總長度。帶空標記的前序是不同於普通前序的表示,特殊標記和完整數據流驗證都是約定的一部分。
5. 習題與解答
快速檢查
(編碼這棵樹:根 只有左子節點 ,而 是葉節點。)
先寫 ,再寫左子樹,最後寫右子樹。
解答 · 答案
X Y # # #。根 之後是其左子樹的編碼 Y # #,然後是空右子樹的空標記 #。
快速檢查
(A # B # # 能否解碼?得到哪棵樹?用槽位數檢查。)
逐個記號追蹤計數。
解答 · 答案
計數為 ,每個記號之前都為正,末尾為零。它解碼為:根 的左子樹為空,右子節點 是葉節點。
快速檢查
(含 7 個節點的樹,其編碼有多少個記號、多少個空標記?)
使用 與 這兩個數量。
解答 · 答案
共 個記號,其中 個是空標記,7 個是值。