建站
咨詢
售后
建站咨詢
新聞中心
大家好，我是鴨血粉絲，拼著頭發(fā)掉光的風(fēng)險(xiǎn)給大家總結(jié)了這篇文章，我愿拿我明年的今天還是單身來祝愿你們能學(xué)會(huì)～
創(chuàng)新互聯(lián)公司長期為數(shù)千家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺(tái)，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為中山企業(yè)提供專業(yè)的成都網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站，中山網(wǎng)站改版等技術(shù)服務(wù)。擁有10余年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。
所謂二叉查找樹，就是按照二分進(jìn)行查找，每次查詢只需要選擇其中一個(gè)子樹就進(jìn)行查找，從而減少查找次數(shù)，提升查詢效率!
一、介紹
在前面的文章中，我們對(duì)樹這種數(shù)據(jù)結(jié)構(gòu)做了一些基本介紹，今天我們繼續(xù)來聊聊一種非常常用的動(dòng)態(tài)查找樹： 二叉查找樹。
二叉查找樹，英文全稱：Binary Search Tree，簡稱：BST，它是計(jì)算機(jī)科學(xué)中最早投入實(shí)際使用的一種樹形結(jié)構(gòu)，特性如下：
- 若左子樹不為空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值;
- 若右子樹不為空，則右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值;
- 它的左、右子樹也分別為二叉查找樹;
特性定義比較粗放，所以在樹形形態(tài)結(jié)構(gòu)上，有著多樣，例如下圖：
上圖 a、b、c 三個(gè)圖，都滿足以上特性，也被稱為二叉查找樹，雖然通過中序遍歷可以得到一個(gè)有效的數(shù)組：[1、2、3、4、5、6、7、8]，但是就查找效率來說，有著一定的差別，例如查詢目標(biāo)為8的內(nèi)容，從根目錄開始查詢，結(jié)構(gòu)如下：
- a圖，需要5次;
- b圖，需要3次;
- c圖，需要8次;
由此可見，不同的形狀，所需查找的次數(shù)是不一樣的，關(guān)于這一點(diǎn)，后面我們在介紹平衡二叉查找樹、紅黑樹這種數(shù)據(jù)結(jié)構(gòu)的時(shí)候，會(huì)進(jìn)行詳細(xì)介紹。
雖然二叉查找樹，在不同的形狀下，查找效率不一樣，但是它是學(xué)習(xí)其他樹形結(jié)構(gòu)的基礎(chǔ)，了解了二叉查找樹的算法，相信再了解其他二叉樹結(jié)構(gòu)會(huì)輕松很多。
二、算法思路
2.1、 新增
新增元素表示向二叉樹中添加元素，比較簡單。如果二叉樹為空，默認(rèn)第一個(gè)元素就是根節(jié)點(diǎn)，如果二叉樹不為空，就以上面提到的特點(diǎn)為判斷條件，進(jìn)行左、右節(jié)點(diǎn)的添加。
2.2、 查找
查找元素表示從根節(jié)點(diǎn)開始查找元素，如果根節(jié)點(diǎn)為空，就直接返回空值，如果不為空，通過以左子樹小于父節(jié)點(diǎn)，右子樹大于父節(jié)點(diǎn)的特性為依據(jù)進(jìn)行判斷，然后以遞歸方式進(jìn)行查找元素，直到找到目標(biāo)的元素為止。
2.3、 刪除
刪除元素表示從二叉樹中移除要?jiǎng)h除的元素，邏輯稍微復(fù)雜一些。同樣，先要判斷根節(jié)點(diǎn)是否為空，如果為空，直接返回，如果不為空，分情況考慮。
被刪除的節(jié)點(diǎn)，右子樹為空
這種場景，只需要將被刪除元素的左子樹的父節(jié)點(diǎn)移動(dòng)到被刪除元素的父節(jié)點(diǎn)，然后將被刪除元素移除即可。
- 被刪除的節(jié)點(diǎn)，左子樹為空
這種場景，與上面類似，只需要將被刪除元素的右子樹的父節(jié)點(diǎn)移動(dòng)到被刪除元素的父節(jié)點(diǎn)，然后將被刪除元素移除即可。
- 被刪除的節(jié)點(diǎn)，左、右子樹不為空
這種場景，稍微復(fù)雜一點(diǎn)，先定位到要?jiǎng)h除的目標(biāo)元素，根據(jù)左子節(jié)點(diǎn)內(nèi)容一定小于當(dāng)前節(jié)點(diǎn)內(nèi)容特點(diǎn)，找到目標(biāo)元素的左子樹，通過遞歸遍歷找到目標(biāo)元素的左子樹的右子樹，找到最末端的元素之后，進(jìn)行與目標(biāo)元素進(jìn)行替換，最后移除最末端元素。
2.4、 遍歷
二叉樹的遍歷方式，分兩類：
- 層次遍歷，從根節(jié)點(diǎn)開始;
- 深度遍歷，又分為前序、中序、后序遍歷三種方式;
2.4.1、層次遍歷
層次遍歷，算法思路比較簡單，從根節(jié)點(diǎn)開始，分層從左到右進(jìn)行遍歷元素。
2.4.2、深度遍歷
深度遍歷，在遍歷起始位置上又分三種，分別是前序遍歷、中序遍歷、后序遍歷，每種遍歷方式輸出的結(jié)果不一樣。
- 前序遍歷：從樹根開始 -> 左子樹 -> 右子樹
- 中序遍歷：從最末端左子樹開始 -> 樹根 -> 右子樹
- 后序遍歷：從最末端左子樹 -> 右子樹 -> 最后到樹根
盡管二叉樹在遍歷方式上有多種，但是只要我們掌握了其中的思路原理，再去實(shí)現(xiàn)起來，就會(huì)輕松很多。
三、代碼實(shí)踐
首先創(chuàng)建一個(gè)實(shí)體數(shù)據(jù)結(jié)構(gòu)BSTNode，內(nèi)容如下：
然后，創(chuàng)建一個(gè)二叉查找樹操作類BinarySearchTree，內(nèi)容如下：
最后，我們來測試一下，代碼內(nèi)容如下：
輸出結(jié)果：
- ========插入元素========
- 插入關(guān)鍵字key=5
- 插入到樹根節(jié)
- 插入關(guān)鍵字key=2
- 插入關(guān)鍵字key=7
- 插入關(guān)鍵字key=1
- 插入關(guān)鍵字key=6
- 插入關(guān)鍵字key=4
- 插入關(guān)鍵字key=8
- 插入關(guān)鍵字key=3
- 插入關(guān)鍵字key=9
- 插入關(guān)鍵字key=10
- ========中序遍歷元素========
- key:1
- key:2
- key:3
- key:4
- key:5
- key:6
- key:7
- key:8
- key:9
- key:10
- ========查找key為9的元素========
- 搜索關(guān)鍵字key=9
- 搜索路徑[5 ->7 ->8 ->9 ->],搜索成功
- 查找結(jié)果：true
- ========刪除key為10的元素========
- 刪除關(guān)鍵字key=10
- 開始搜索目標(biāo)元素[5 ->7 ->8 ->9 ->10 ->],搜索成功
- 刪除結(jié)果：true
- ========再次中序遍歷元素========
- key:1
- key:2
- key:3
- key:4
- key:5
- key:6
- key:7
- key:8
- key:9
四、總結(jié)
二叉查找樹，作為樹類型中一種非常重要的數(shù)據(jù)結(jié)構(gòu)，有著非常廣泛的應(yīng)用，但是二叉查找樹具有很高的靈活性，不同的插入順序，可能造成樹的形態(tài)差異比較大，如開文介紹的圖c，在某些情況下會(huì)變成一個(gè)長鏈表，此時(shí)的查詢效率會(huì)大大降低，如何解決這個(gè)問題呢，平衡二叉樹就要派上用場了，會(huì)在后面的文章進(jìn)行介紹!
(第一句話是開玩笑，呸呸呸，情人節(jié)快樂)
網(wǎng)頁名稱：看懂這篇文章，玩轉(zhuǎn)二叉查找樹
標(biāo)題來源：http://www.dlmjj.cn/article/cdoppop.html
