第5章 樹基礎#

本章目標#

• 掌握二元樹的四種走訪方式與遞迴思維。
• 實作二元搜尋樹（BST）的搜尋、插入、刪除。
• 認識樹在真實系統中的各種表示法與應用。

章前言#

從這一章開始，我們進入「非線性」的世界。線性結構（陣列、串列）的每個元素只有前後鄰居，而樹允許一個元素有「多個下層」：公司組織圖、檔案系統目錄、HTML 文件結構、選單分類——凡是「階層關係」，本質上都是樹。

二元樹（binary tree） 是每個節點至多兩個小孩的樹，結構簡單卻蘊含驚人效率：n 個節點若排列平衡，樹高只有 O(log n)，代表「沿著一條路往下走」就能在 O(log n) 內定位任何元素——一百萬筆資料只需約 20 步。二元搜尋樹（BST） 在二元樹上加一條規則「左小右大」，於是搜尋、插入、刪除都變成 O(log n)（平衡時），而且中序走訪天然輸出排序結果，是「有序集合」的基礎實現。

本章先練走訪——前序、中序、後序、層序，這些是所有樹演算法的基本功；再實作完整的 BST，包含最有挑戰性的刪除操作（有兩個小孩時要找後繼者接手）；最後綜覽樹的表示法（子女串列、左子女右兄弟）與真實應用（檔案系統、運算式樹、字典樹的前身）。BST 的弱點——退化成鏈狀導致 O(n)——將在第6章由 AVL 樹與紅黑樹解決。