地特三等申論題 105年 [資訊處理] 資料結構

第一題

📖 題組：
請回答下列問題：

📝 此題為申論題，共 2 小題

小題 (一)

畫出 AVL 平衡二元樹，其中序（inorder）拜訪為 1、2、3、4、5 任三種。（24 分）

看到「中序拜訪為排序數列」應立刻聯想到二元搜尋樹（BST）的特性。接著只要利用 1 到 5 這五個節點，建構出符合「任意節點左右子樹高度差不大於 1」的 BST（即 AVL 樹）即可，可透過改變根節點來畫出不同組合。

🤖

AI 詳解

AI 專屬家教

【解題思路】二元搜尋樹（BST）的中序拜訪必為遞增數列（1、2、3、4、5），因此本題即要求畫出由節點 1~5 所組成，且滿足任意節點其左右子樹高度差（平衡因子 Balance Factor）不大於 1 的 AVL 平衡二元樹。【解答】以下提供三種符合條件的 AVL 樹圖示：

請問共有多少種 AVL 平衡二元樹，其中序拜訪為 1、2、3、4、5？（6 分）

看到中序拜訪序列為遞增數列，應立刻聯想到這構成了一棵「二元搜尋樹 (BST)」。結合 AVL 樹「左右子樹高度差絕對值不超過 1」的特性，解題策略為：依序假設 1 到 5 分別為根節點，拆分左右子樹的節點數，計算符合平衡條件的合法子樹結構數，最後加總所有可能。

🤖

AI 詳解

AI 專屬家教

【解題思路】中序拜訪為 1、2、3、4、5 的二元樹必為二元搜尋樹 (BST)。透過窮舉可能的根節點，篩選並計算符合 AVL 樹條件（左右子樹高度差 $\le 1$）的組合數量。【詳解】已知：節點總數 $n=5$ 且中序為 1 到 5（構成 BST）。