免費開始練習
moea_joint_essay 108年 [統計資訊] 資料庫及資料探勘、程式設計

第 二 題

📖 題組:
請就二元搜尋樹回答下列問題:(20 分)
📝 此題為申論題,共 3 小題

小題 (二)

數列 27、35、17、33、20、3、38,試以第 1 個數字為根,寫出其二元搜尋樹及建立的步驟。(10 分)

思路引導 VIP

依序插入每一個數字,若大於當前節點往右,若小於則往左,直到找到空位插入。

🤖
AI 詳解
AI 專屬家教

建立步驟:

  1. 插入 27:樹為空,將 27 設為根節點 (Root)。
  2. 插入 35:35 > 27,放在 27 的右子節點。

小題 (一)

請說明欲建立二元搜尋樹,必須滿足哪些條件?(6 分)

思路引導 VIP

敘述 Binary Search Tree (BST) 的定義特性(節點值關係)。

🤖
AI 詳解
AI 專屬家教

建立二元搜尋樹 (Binary Search Tree) 必須滿足以下條件:

  1. 每個節點最多只能有兩個子節點(左子節點和右子節點)。
  2. 對於任何一個節點,其左子樹中所有節點的值必須小於該節點的值。

小題 (三)

在上述二元搜尋樹中,若欲刪除元素 27,請寫出 2 種做法。(4 分)

思路引導 VIP

刪除有兩個子節點的節點時,可以用左子樹中最大值(前驅),或是右子樹中最小值(後繼)來取代該節點。

🤖
AI 詳解
AI 專屬家教

由於要刪除的元素 27 是根節點,且同時具有左子樹和右子樹,欲刪除它有以下兩種標準做法: 做法 1:找尋左子樹中最大的元素(即 20)來取代 27 的位置,然後刪除原來的 20 節點。 做法 2:找尋右子樹中最小的元素(即 33)來取代 27 的位置,然後刪除原來的 33 節點。

🏷️ 相關主題

程式設計演算法與資料結構實作
查看更多「[統計資訊] 資料庫及資料探勘、程式設計」的主題分類考古題