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

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

 

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

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

 

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

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

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

  • 網(wǎng)友評論