內(nèi)容來(lái)自尚硅谷Java數(shù)據(jù)結(jié)構(gòu)與java算法（Java數(shù)據(jù)結(jié)構(gòu)與算法）_嗶哩嗶哩_bilibili

寫在前面:本文內(nèi)容大致和原視頻內(nèi)老師的筆記內(nèi)容相同，會(huì)偶爾插入自己的注釋和理解，盡量會(huì)完成作業(yè)

本次作業(yè)已完成，理解了之后就很簡(jiǎn)單

11.4二叉排序樹(shù)

11.4.1先看一個(gè)需求

給你一個(gè)數(shù)列(7,3,10,12,5,1,9),要求能夠高效的完成對(duì)數(shù)據(jù)的查詢和添加

11.4.2解決方案分析

使用數(shù)組

數(shù)組未排序，優(yōu)點(diǎn):直接在數(shù)組尾添加，速度快。缺點(diǎn):查找速度慢.[示意圖]

數(shù)組排序，優(yōu)點(diǎn):可以使用二分查找，查找速度快，缺點(diǎn):為了保證數(shù)組有序，在添加新數(shù)據(jù)時(shí)，找到插入位置后，后面的數(shù)據(jù)需整體移動(dòng)，速度慢。[示意圖]

使用鏈?zhǔn)酱鎯?chǔ)-鏈表

不管鏈表是否有序，查找速度都慢，添加數(shù)據(jù)速度比數(shù)組快，不需要數(shù)據(jù)整體移動(dòng)。[示意圖]

使用二叉排序樹(shù)

11.4.3二叉排序樹(shù)介紹

二叉排序樹(shù):BST:(BinarySort(Search)Tree)。對(duì)于二叉排序樹(shù)的任何一個(gè)非葉子節(jié)點(diǎn)，要求左子節(jié)點(diǎn)的值比當(dāng)前節(jié)點(diǎn)的值小，右子節(jié)點(diǎn)的值比當(dāng)前節(jié)點(diǎn)的值大。

特別說(shuō)明:如果有相同的值，可以將該節(jié)點(diǎn)放在左子節(jié)點(diǎn)或右子節(jié)點(diǎn)

比如針對(duì)前面的數(shù)據(jù)(7,3,10,12,5,1,9)，對(duì)應(yīng)的二叉排序樹(shù)為:

11.4.4二叉排序樹(shù)的創(chuàng)建和遍歷

一個(gè)數(shù)組創(chuàng)建成對(duì)應(yīng)的二叉排序樹(shù)，并使用中序遍歷二叉排序樹(shù)，比如:數(shù)組為Array(7,3,10,12,5,1,9)，創(chuàng)建成對(duì)應(yīng)的二叉排序樹(shù)為∶

二叉排序樹(shù)的刪除情況比較復(fù)雜，有下面三種情況需要考慮

1.????? 刪除葉子節(jié)點(diǎn)(比如: 2,5,9,12)

2.????? 刪除只有一顆子樹(shù)的節(jié)點(diǎn)(比如:1)

3.????? 刪除有兩顆子樹(shù)的節(jié)點(diǎn).(比如:7,3,10)

4.????? 操作的思路分析

//對(duì)刪除節(jié)點(diǎn)的不同情況的分析

第一種情況:

刪除葉子節(jié)點(diǎn)(比如:2,5,9,12)

思路

(1)需求先去找到要?jiǎng)h除的結(jié)點(diǎn)targetNode

(2)找到targetNode的父結(jié)點(diǎn)parent

(3)確定targetNode是parent的左子結(jié)點(diǎn)還是右子結(jié)點(diǎn)

(4)根據(jù)前面的情況來(lái)對(duì)應(yīng)冊(cè)除

左子結(jié)點(diǎn)parent.left = null

右子結(jié)點(diǎn)parent.right = null;

第二種情況:冊(cè)刪除只有一顆子樹(shù)的節(jié)點(diǎn)比如1

思路

(1)需求先去找到要?jiǎng)h除的結(jié)點(diǎn)targetNode

(2)找到targetNode的父結(jié)點(diǎn)parent

(3)確定targetNode的子結(jié)點(diǎn)是左子結(jié)點(diǎn)還是右子結(jié)點(diǎn)

(4)targetNode是parent的左子結(jié)點(diǎn)還是右子結(jié)點(diǎn)

(5)如果targetNode有左子結(jié)點(diǎn)

5.1如果targetNode是parent 的左子結(jié)點(diǎn)

parent.left = targetNode.left;

5.2如果targetNode是parent的右子結(jié)點(diǎn)

parent.right = targetNode.left;

(6)如果targetNode有右子結(jié)點(diǎn)

6.1如果targetNode是 parent的左子結(jié)點(diǎn)

parent.left = targetNode.right;

6.2如果targetNode是 parent的石子結(jié)點(diǎn)

parent.right = targetNode.right

情況三:刪除有兩顆子樹(shù)的節(jié)點(diǎn).(比如:7,3，10 )

思路

(1)需求先去找到要?jiǎng)h除的結(jié)點(diǎn)targetNode

(2)找到targetNode的父結(jié)點(diǎn) parent

(3)從targetNode 的右子樹(shù)找到最小的結(jié)點(diǎn)

(4)用一個(gè)臨時(shí)變量，將最小結(jié)點(diǎn)的值保存temp = 11

(5)刪除該最小結(jié)點(diǎn)

(6)targetNode.value = temp

11.4.6二叉排序樹(shù)刪除節(jié)點(diǎn)的代碼實(shí)現(xiàn)

11.4.7課后練習(xí)：完成老師代碼，并使用第二種方式解決

如果我們從左子樹(shù)找到最大的節(jié)點(diǎn)，然后按照前面的思路完成