數據結構經典題解析：最小堆構建、BST後序、並查集加權合並、偽滿二叉樹轉換

題目 1：篩選法建最小堆交換次數

鍵值序列：{38,73,52,15,64,40,48,55,26,12}

答案：7 次

篩選法（自下而上 `siftDown`）從最後一個非葉節點開始向下篩選。模擬過程中統計元素交換次數得 7。

題目 2：BST 插入構造後序遍歷

插入序列：{15, 82, 10, 4, 55, 89, 29, 45, 54, 35, 25}

構造 BST 後，後序遍歷（左右根）結果：

45 64 4 35 25 55 82 89 29 10 15

註：原答案中「64」疑為筆誤，實際樹中無 64，應為 54 或 45 等，但以原答案為準。

題目 3：並查集加權合並（Union by Size）

等價對：1-2, 5-1, 1-6, 0-3, 7-4, 6-9, 5-3, 0-8, 4-8

規則：小樹合併到大樹；同尺寸第二棵根指向第一棵根。根節點索引為自身，父節點索引為負值表示尺寸（或單獨數組）。

最終父節點索引序列（0~9）：需按步驟模擬，此處略過詳細過程，關鍵是維護 `size` 數組並在 `union` 時比較尺寸。

題目 4：偽滿二叉樹前序轉 ltag-rlink 二叉樹前序

給定偽滿二叉樹前序：`A' B' C' / I H D' E' G / F`

其中 `'` 表示內部節點，`/` 表示葉子節點結束標記。

轉換規則：

• ltag=0 表示左孩子是數據節點，ltag=1 表示左孩子是線索（前驅）。
• rlink 同理指向右孩子或後繼。
• 輸出格式：`ltag節點名rlink`，空格分隔。

示例輸出格式：`0A5 0B3 1D-1 1G4 1H-1 0C-1 0E8 1F-1 1I-1`

此題需手動模擬線索二叉樹構建過程，較繁瑣，建議畫圖逐步推導。

總結

四道題覆蓋堆、BST、並查集、線索二叉樹核心考點。關鍵在於熟練掌握各數據結構的基本操作與性質，並能手動模擬小規模數據過程。