在上一篇博客中，我們主要介紹了四種查找的方法，包括順序查找、折半查找、插入查找以及Fibonacci查找。上面這幾種查找方式都是基于線性表的查找方式，今天博客中我們來介紹一下基于二叉樹結(jié)構(gòu)的查找，也就是我們今天要聊的二叉排序樹。今天主要聊的是二叉排序樹的查找、插入與刪除的內(nèi)容，二叉排序的創(chuàng)建過程其實(shí)就是不斷查找與插入的過程，也就是說當(dāng)我們在創(chuàng)建二叉排序樹時(shí)，我們會先搜索該節(jié)點(diǎn)在二叉排序樹中的位置，若沒有找到該節(jié)點(diǎn)則返回該節(jié)點(diǎn)將要插入的父節(jié)點(diǎn)，然后將該結(jié)點(diǎn)插入。而二叉排序樹結(jié)點(diǎn)的刪除則有些復(fù)雜，分為幾種情況討論，下方會給出詳細(xì)的介紹。

在本篇博客的開頭，我們先聊聊什么是二叉排序樹。說的直白一些，具有左子樹上的值<根節(jié)點(diǎn)的值<右子樹上的值的二叉樹，我們稱之為二叉排序樹?；诙媾判驑涞奶攸c(diǎn)，有結(jié)合著中序遍歷的特點(diǎn)（中序遍歷是先遍歷左子樹，再遍歷根節(jié)點(diǎn)，然后遍歷右子樹），我們不難發(fā)現(xiàn)，二叉排序樹的中序遍歷的結(jié)果是從小到大有序的。下方我們會先給出二叉排序樹的創(chuàng)建，然后給出二叉排序樹的節(jié)點(diǎn)刪除的代碼。廢話少說，進(jìn)入今天博客的主題。

 

一、二叉排序樹的創(chuàng)建

上面也簡單的提了一下，二叉排序樹的創(chuàng)建無非就是不斷查找和插入的過程，當(dāng)我們查找某個(gè)值沒有找到時(shí)，我們就會將該值插入到二叉排序樹中。因?yàn)樵俨檎业倪^程中可以確定該結(jié)點(diǎn)要插入的合適位置，所以插入就顯得比較簡單了。下方我們會先給出二叉排序樹查找與插入的示意圖，然后再給出相應(yīng)的代碼實(shí)現(xiàn)。最后給出中序遍歷的結(jié)果，觀察我們創(chuàng)建的二叉排序樹的中序遍歷是否是有序的。

 

1、二叉排序樹的查找與插入的示意圖

我們要將集合{62, 88, 58, 47, 35, 73, 51, 99, 37, 93}中的元素放入到我們的二叉排序樹中去存儲，如果對我們創(chuàng)建好的二叉排序樹進(jìn)行中序搜索的話，輸出的結(jié)果就是上面集合的有序序列。下方就是我們二叉排序樹從無到有的完整創(chuàng)建過程。

  • （1）、在初始化狀態(tài)下我們二叉排序樹的根節(jié)點(diǎn)為空，我們依次將集合中的元素通過搜索插入到二叉排序樹中合適的位置。

  • 網(wǎng)友評論