C 程式設計 二進位排序樹查詢

<>第乙個數字作為根節點，將下乙個數字分成大於30和小於30的數字，小數放在左邊，大數放在右邊，然後按照數字出現的順序，乙個接乙個地放在比根節點大的節點上， 小的放在左邊。

左下 30 個，右下 15 個，43 個

左下 15 個，右下 8 個，25 個

右下方 43 49

右下方 8 13

左下 25 個，右下 20 個，28 個

左下 49 個，右下 46 個，55 個

左邊下方 13 10

選擇 D，先找到 46 個節點：46>35，然後轉到 46 個節點的左側子樹並繼續搜尋：36>35，繼續到 36 個節點左側子樹搜尋：

18<35，到節點 18 的右側子樹：28<35，到右側子樹的節點 28 搜尋：35=35，結束。

其餘的答案都是不正確的。 例如，在 B 中，找到 36 個節點後，應該去 36 的左側子樹找到它們，所以所有後續節點都應該小於 36，但在 36 個節點之後就不可能了 46。

選項 a 的查詢比較路徑如下所示28

46 35 這個選項，如果說是公升序排序樹，18 在右邊的子樹上，如果說是降序排序樹，顯然不是。

選項 b 的查詢比較路徑如下所示18

46 35 這裡我們看到的是一棵以 36 為根的子樹，丟棄它的原因與上面相同。 36 在右左子樹上有 28 和 28。

選項 c 的查詢比較路徑是 48，如下所示

36 35 是乙個以 28 為根的子樹，它的左子樹上有 18 和 18。 所以被丟棄了。

選項 D 的查詢比較路徑如下46

28 35 非常適合，因此正確的選項是 d。

這應該是選擇B。 就二叉排序樹而言，它有三個特點：（1）如果左邊的子樹不為空，則左邊子樹上所有節點的值都小於其根節點的值; （2）如果右子樹不為空，則右子樹上所有節點的值大於其根節點的值; （3）左子樹和右子樹也分別是二叉排序樹。 可以基於此功能排除 ACD。 例如，如果第一次 a 的數是 28，但關鍵字是 35，那麼應該遍歷 28 的右子樹（很容易知道 28 是根節點），那麼接下來要遍歷的數字，或者要比較的數字應該大於 28（根據二叉排序樹的第二個特徵）， 但是 18 出現在 A 選項之後，所以 A 是錯誤的。

cd 選項也是如此，這也是錯誤的。 只有選項 b 是正確的。

二進位排序樹。

構造過程：按照給定的順序，將節點插入到二叉排序樹中，並在二叉排序樹中插入乙個新節點，並且必須保證插入的二叉樹。

它仍然符合二叉排序樹的定義。

插入過程：如果二叉排序樹為空，則將要插入的節點 *s 作為根節點插入到空樹中。

>>如果 s->key = t->key，則不需要插入，如果 s->key < t->key，則插入根的左子樹，如果 s->key > t->key，則插入根的右子樹。 子樹中的插入過程與樹中的插入過程相同，依此類推，直到節點 *s 作為新葉子插入到二叉排序樹中，或者直到樹中已經有具有相同關鍵字的節點。

說明：每次插入乙個新節點都是二叉排序樹上的乙個新葉節點。

從不同順序的關鍵字序列中，將獲得不同的二叉排序樹。

為任意關鍵字序列構建二叉排序樹本質上是對關鍵字進行排序。

查詢的過程是相似的，從根節點開始，如果它小於根節點，則在左側子樹上進行比較，如果它大於根節點，則在右側子樹上進行比較，依此類推，直到搜尋成功或失敗（與葉節點相比）。

5.刪除二叉排序樹：

假設刪除的節點是 *p，它的父節點是 *f，一般不會丟失，*p 是 *f 的左子節點，下面將討論三種情況：

如果節點 *p 是葉節點，則只需修改其父節點 *f 的指標即可。

如果節點 *p 只有左子樹 pl 或右子樹 pr，則使 pl 或 pr 成為其父節點的左子樹就足夠了。

如果節點 *p 的左子樹和右子樹不為空，首先找到 *p 的正向節點 *s 的中值（注意 *s 是 *p 左子樹中的右下角節點，其右鏈域為空），然後有兩種方法：

讓 *p 的左子樹直接鏈結到 *p 的父節點 *f 的左鏈，*p 的右子樹應該鏈結到 *p 的中階正向節點 *s 的右鏈。

將 *p 替換為 *p 的正向節點中位數 *s（即將 *s 的資料複製到 *p），並將 *s 的左子樹鏈結到 *s 的父節點 *q 的左（或右）鏈。

6.刪除演算法演示：

7.二進位排序樹查詢：

在二叉排序樹中查詢的過程類似於二叉搜尋，也是乙個逐漸縮小搜尋範圍的過程。 如果搜尋成功，則為從根節點到要檢查的節點的路徑。 如果搜尋失敗，則採用從根節點到葉節點的路徑。 因此，比較查詢過程和關鍵字的次數不會超過樹的深度。

由於具有 n 個節點的二叉排序樹不是唯一的，因此形狀和深度可能不同。 因此，具有n個節點的二元排序樹的平均搜尋長度與樹的形態有關。

在最好的情況下，二叉排序樹和二叉決策樹的形狀相同。

最壞情況：二叉排序樹是單分支樹，其中平均查詢長度與順序查詢相同。

最壞的情況。

從平均效能來看，在二叉排序樹上的查詢與二叉搜尋沒有太大區別，在二叉排序樹上插入和刪除節點非常方便，無需移動大量節點。