很多小夥伴都老是會碰到疑問,其實還是基礎沒打紮實,這些題如果你不看答案你能知道多少呢?如果還有很多不知道就證明基礎沒打紮實,如果你還在入門糾結,如果你還在苦惱怎麼入門!小編有個建議,可以加小編弄的一個C語言交流基地,大家可以進入交流基地:565122788,裡面新手入門資料,可以說從零到專案實戰,都是可以免費獲取的,還有程式設計師大牛為各位免費解答問題,熱心腸的小夥伴也是蠻多的。不失為是一個交流的的好地方,小編在這裡邀請大家加入我的大家庭。歡迎你的到來。一起交流學習!共同進步!小編等你!
在二叉搜尋樹查詢一文中主要介紹了二叉搜尋樹的
查詢
,本文將繼續介紹其
插入
和
刪除
操作。二叉搜尋樹的插入和刪除關鍵在於在插入和刪除的過程中如何繼續保持二叉搜尋樹的性質。
二叉搜尋樹結點定義如下:
插入結點
插入結點的位置對應著查詢過程中查詢不成功時候的結點位置,因此需要從根結點開始查詢帶插入結點位置,找到位置後插入即可。下圖所示插入結點過程:
插入結點程式碼如下
刪除結點
二叉搜尋樹刪除結點可以說是二叉搜尋樹中最為複雜的操作,要考慮的情況比較多,下面分情況討論。
(1)
要刪除的結點
z
為
葉子
結點,這是最簡單的一種情況,直接修改其父節點相應指標為NULL。刪除過程如下圖所示:
(2)
要刪除的結點
z
為只有
一個子樹
,讓z的子樹與z的父親節點相連,刪除z即可,刪除過程如下圖所示:
(3)
要刪除的結點
z
為有
兩個子樹
,則先找到z的
後繼
結點
y
,y肯定是沒有左子樹的(如果y還有左子樹,那麼y就肯定不是z的後繼結點),所以現在可以按照上面兩種情況
刪除y
結點,最後用
y
的
值代替z
的
值
。整個刪除過程如下圖所示:
二叉搜尋樹刪除結點的程式碼實現如下。
程式碼中的
bstree_successor(z)
函式功能是找到結點z的後繼結點,至於什麼是後繼結點以及其實現,前文二叉搜尋樹查詢已有總結,此處不再詳述。
上面就是二叉搜尋樹的插入和刪除結點的思路和程式碼,大家在看程式碼的時候可以對著圖將每種情況在自己腦中執行,比如說對於刪除操作的第一種情況,它在程式碼中的執行流程是什麼,這樣可能更加容易理解。
為您提供通俗易懂的技術文章,讓技術變的更簡單!