在上一篇博客中，我們主要介紹了四種查找的方法，包括順序查找、折半查找、插入查找以及Fibonacci查找。上面這幾種查找方式都是基于線性表的查找方式，今天博客中我們來(lái)介紹一下基于二叉樹(shù)結(jié)構(gòu)的查找，也就是我們今天要聊的二叉排序樹(shù)。今天主要聊的是二叉排序樹(shù)的查找、插入與刪除的內(nèi)容，二叉排序的創(chuàng)建過(guò)程其實(shí)就是不斷查找與插入的過(guò)程，也就是說(shuō)當(dāng)我們?cè)趧?chuàng)建二叉排序樹(shù)時(shí)，我們會(huì)先搜索該節(jié)點(diǎn)在二叉排序樹(shù)中的位置，若沒(méi)有找到該節(jié)點(diǎn)則返回該節(jié)點(diǎn)將要插入的父節(jié)點(diǎn)，然后將該結(jié)點(diǎn)插入。而二叉排序樹(shù)結(jié)點(diǎn)的刪除則有些復(fù)雜，分為幾種情況討論，下方會(huì)給出詳細(xì)的介紹。
在本篇博客的開(kāi)頭，我們先聊聊什么是二叉排序樹(shù)。說(shuō)的直白一些，具有左子樹(shù)上的值<根節(jié)點(diǎn)的值<右子樹(shù)上的值的二叉樹(shù)，我們稱(chēng)之為二叉排序樹(shù)。基于二叉排序樹(shù)的特點(diǎn)，有結(jié)合著中序遍歷的特點(diǎn)（中序遍歷是先遍歷左子樹(shù)，再遍歷根節(jié)點(diǎn)，然后遍歷右子樹(shù)），我們不難發(fā)現(xiàn)，二叉排序樹(shù)的中序遍歷的結(jié)果是從小到大有序的。下方我們會(huì)先給出二叉排序樹(shù)的創(chuàng)建，然后給出二叉排序樹(shù)的節(jié)點(diǎn)刪除的代碼。廢話少說(shuō)，進(jìn)入今天博客的主題。
一、二叉排序樹(shù)的創(chuàng)建
上面也簡(jiǎn)單的提了一下，二叉排序樹(shù)的創(chuàng)建無(wú)非就是不斷查找和插入的過(guò)程，當(dāng)我們查找某個(gè)值沒(méi)有找到時(shí)，我們就會(huì)將該值插入到二叉排序樹(shù)中。因?yàn)樵俨檎业倪^(guò)程中可以確定該結(jié)點(diǎn)要插入的合適位置，所以插入就顯得比較簡(jiǎn)單了。下方我們會(huì)先給出二叉排序樹(shù)查找與插入的示意圖，然后再給出相應(yīng)的代碼實(shí)現(xiàn)。最后給出中序遍歷的結(jié)果，觀察我們創(chuàng)建的二叉排序樹(shù)的中序遍歷是否是有序的。
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動(dòng)安全 [無(wú)線安全]玩轉(zhuǎn)無(wú)線電——不安全的藍(lán)牙鎖 2017-07-26
- 消息隊(duì)列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標(biāo)分割】 2017-07-26
- 詞向量-LRWE模型-更好地識(shí)別反義詞同義詞 2017-07-26
- 從棧不平衡問(wèn)題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實(shí)現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動(dòng)安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來(lái)看看(二) 2017-07-26
學(xué)習(xí)是年輕人改變自己的最好方式