數據結構：二叉排序樹構造過程詳解

題目

給定初始關鍵字序列：(45, 80, 48, 40, 22, 78)，要求構造二叉排序樹（BST）並給出構造過程。

二叉排序樹（BST）基本規則

• 若左子樹不空，則左子樹上所有節點的值 小於 根節點的值
• 若右子樹不空，則右子樹上所有節點的值 大於 根節點的值
• 左右子樹也分別為二叉排序樹
• 無鍵值相等的節點（本題假設無重複值）

逐步構造過程

第 1 步：插入 45

樹為空，45 成為根節點。

    45

第 2 步：插入 80

80 > 45，作為 45 的右孩子。

    45
      \
       80

第 3 步：插入 48

48 > 45 → 向右；48 < 80 → 向左，作為 80 的左孩子。

    45
      \
       80
      /
     48

第 4 步：插入 40

40 < 45 → 向左，作為 45 的左孩子。

    45
   /  \
  40   80
      /
     48

第 5 步：插入 22

22 < 45 → 向左；22 < 40 → 向左，作為 40 的左孩子。

      45
     /  \
    40   80
   /    /
  22   48

第 6 步：插入 78

78 > 45 → 向右；78 < 80 → 向左；78 > 48 → 向右，作為 48 的右孩子。

      45
     /  \
    40   80
   /    /
  22   48
         \
         78

最終二叉排序樹結構

        45
       /  \
     40    80
    /     /
   22    48
           \
           78

中序遍歷驗證

中序遍歷結果：22, 40, 45, 48, 78, 80（遞增有序），符合 BST 性質。

複雜度分析

• 平均情況：插入/查找/刪除 O(log n)
• 最壞情況（退化為鏈表）：O(n)
• 本例中樹高為 4，查找 78 需 4 次比較

參考資源

更多圖解可參考：二叉排序樹構造詳解