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

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

10.1二叉樹(shù)

10.1.1為什么需要樹(shù)這種數(shù)據(jù)結(jié)構(gòu)

1.數(shù)組存儲(chǔ)方式的分析

優(yōu)點(diǎn):通過(guò)下標(biāo)方式訪問(wèn)元素，速度快。對(duì)于有序數(shù)組，還可使用二分查找提高檢索速度。

缺點(diǎn):如果要檢索具體某個(gè)值，或者插入值(按一定順序)會(huì)整體移動(dòng)，效率較低[示意圖]

畫(huà)出操作示意圖

2.鏈?zhǔn)酱鎯?chǔ)方式的分析

優(yōu)點(diǎn):在一定程度上對(duì)數(shù)組存儲(chǔ)方式有優(yōu)化(比如:插入一個(gè)數(shù)值節(jié)點(diǎn)，只需要將插入節(jié)點(diǎn)，鏈接到鏈表中即可，刪除效率也很好)。

缺點(diǎn):在進(jìn)行檢索時(shí)，效率仍然較低，比如(檢索某個(gè)值，需要從頭節(jié)點(diǎn)開(kāi)始遍歷)【示意圖】

操作示意圖

3.樹(shù)存儲(chǔ)方式的分析

能提高數(shù)據(jù)存儲(chǔ)，讀取的效率，比如利用二叉排序樹(shù)(Binary Sort Tree)，既可以保證數(shù)據(jù)的檢索速度，同時(shí)也可以保證數(shù)據(jù)的插入，刪除，修改的速度?！臼疽鈭D,后面詳講】

案例: [7,3,10,1,5,9,12]

10.1.2樹(shù)示意圖

樹(shù)的常用術(shù)語(yǔ)(結(jié)合示意圖理解):

1.????? ? 節(jié)點(diǎn)

2.????? ? 根節(jié)點(diǎn)

3.????? ? 父節(jié)點(diǎn)

4.????? ? 子節(jié)點(diǎn)

5.????? ? 葉子節(jié)點(diǎn)(沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn))

6.????? ? 節(jié)點(diǎn)的權(quán)(節(jié)點(diǎn)值)

7.????? ? 路徑(從root節(jié)點(diǎn)找到該節(jié)點(diǎn)的路線)

8.????? ? 層

9.????? ? 子樹(shù)

10.??? ? 樹(shù)的高度(最大層數(shù))

11.??? ? 森林:多顆子樹(shù)構(gòu)成森林

?

10.1.3二叉樹(shù)的概念

1)樹(shù)有很多種，每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)的一種形式稱為二叉樹(shù)。

2)二叉樹(shù)的子節(jié)點(diǎn)分為左節(jié)點(diǎn)和右節(jié)點(diǎn)

3)示意圖

4)如果該二叉樹(shù)的所有葉子節(jié)點(diǎn)都在最后一層，并且結(jié)點(diǎn)總數(shù)=2'n-1,n為層數(shù)，則我們稱為滿二叉樹(shù)。

5)如果該二叉樹(shù)的所有葉子節(jié)點(diǎn)都在最后一層或者倒數(shù)第二層，而且最后一層的葉子節(jié)點(diǎn)在左邊連續(xù)，倒數(shù)第二層的葉子節(jié)點(diǎn)在右邊連續(xù)，我們稱為完全二叉樹(shù)

10.1.4二叉樹(shù)遍歷說(shuō)明

使用前序，中序和后序對(duì)下面的二叉樹(shù)進(jìn)行遍歷

1.????? 前序遍歷:先輸出父節(jié)點(diǎn)，再遍歷左子樹(shù)和右子樹(shù)

2.????? 中序遍歷:先遍歷左子樹(shù)，再輸出父節(jié)點(diǎn)，再遍歷右子樹(shù)

3.????? 后序遍歷:先遍歷左子樹(shù)，再遍歷右子樹(shù)，最后輸出父節(jié)點(diǎn)

4.????? 小結(jié):看輸出父節(jié)點(diǎn)的順序，就確定是前序，中序還是后序

10.1.5二叉樹(shù)遍歷應(yīng)用實(shí)例(前序,中序,后序)

應(yīng)用實(shí)例的說(shuō)明和思路

代碼實(shí)現(xiàn)