內(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è)

本次作業(yè)完成了，有借鑒部分，跟著debug跑過(guò)一遍后能看懂，但是如果自己寫(xiě)，還是有點(diǎn)難度

10.3.1先看一個(gè)問(wèn)題

將數(shù)列{1,3,6,8,10,14}構(gòu)建成一棵二叉樹(shù) n+1 = 7

1.????? 當(dāng)我們對(duì)上面的二叉樹(shù)進(jìn)行中序遍歷時(shí)，數(shù)列為{8,3,10,1,6,14}

2.????? 但是6,8,10,14 這幾個(gè)節(jié)點(diǎn)的左右指針，并沒(méi)有完全的利用上.

3.????? 如果我們希望充分的利用各個(gè)節(jié)點(diǎn)的左右指針，讓各個(gè)節(jié)點(diǎn)可以指向自己的前后節(jié)點(diǎn),怎么辦?

4.????? 解決方案-線索二叉樹(shù)

10.3.2線索二叉樹(shù)的基本介紹

1.????? n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n+1【公式2n-(n-1)=n+1】個(gè)空指針域。利用二叉鏈表中的空指針域，存放指向該結(jié)點(diǎn)在某種遍歷次序下的前驅(qū)和后繼結(jié)點(diǎn)的指針（這種附加的指針?lè)Q為"線索")

2.????? 這種加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹(shù)稱為線索二叉樹(shù)(Threaded BinaryTree)。根據(jù)線索性質(zhì)的不同，線索二叉樹(shù)可分為前序線索二叉樹(shù)、中序線索二叉樹(shù)和后序線索二叉樹(shù)三種

3.????? 一個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，稱為前驅(qū)結(jié)點(diǎn)

4.????? 一個(gè)結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)，稱為后繼結(jié)點(diǎn)

10.3.3線索二叉樹(shù)的應(yīng)用案例

應(yīng)用案例說(shuō)明:將下面的二叉樹(shù)，進(jìn)行中序線索二叉樹(shù)。中序遍歷的數(shù)列為{8,3,10,1,14,6}

思路分析 中序遍歷結(jié)果：{8,3,10,1,14,6}

說(shuō)明:當(dāng)線索化二叉樹(shù)后，Node節(jié)點(diǎn)的屬性left和right，有如下情況:

1.????? left 指向的是左子樹(shù),也可能是指向的前驅(qū)節(jié)點(diǎn).比如①節(jié)點(diǎn)left 指向的左子樹(shù),而⑩節(jié)點(diǎn)的 left 指向的就是前驅(qū)節(jié)點(diǎn).

2.????? right指向的是右子樹(shù)，也可能是指向后繼節(jié)點(diǎn)，比如①節(jié)點(diǎn)right 指向的是右子樹(shù)，而⑩節(jié)點(diǎn)的right 指向的是后繼節(jié)點(diǎn).

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

10.3.4遍歷線索化二叉樹(shù)

1)說(shuō)明:對(duì)前面的中序線索化的二叉樹(shù)，進(jìn)行遍歷

2)分析:因?yàn)榫€索化后，各個(gè)結(jié)點(diǎn)指向有變化，因此原來(lái)的遍歷方式不能使用，這時(shí)需要使用新的方式遍歷線索化二叉樹(shù)，各個(gè)節(jié)點(diǎn)可以通過(guò)線型方式遍歷，因此無(wú)需使用遞歸方式，這樣也提高了遍歷的效率。遍歷的次序應(yīng)當(dāng)和中序遍歷保持一致。

3)代碼:

10.3.5線索化二叉樹(shù)課后作業(yè)

我這里講解了中序線索化二叉樹(shù)，前序線索化二叉樹(shù)和后序線索化二叉樹(shù)的分析思路類似，同學(xué)們作為課后作業(yè)完成.

作業(yè)完成了，但是沒(méi)有完成，代碼上面有

借鑒了CSDN的一位大佬的解答

我根據(jù)大佬解答結(jié)合韓老師的代碼，才完成了這次作業(yè)，運(yùn)行起來(lái)是沒(méi)有問(wèn)題了，理解起來(lái)還需要時(shí)間，主要是后序遍歷線索化樹(shù)有點(diǎn)難度

https://blog.csdn.net/UncleMing5371/article/details/54176252

https://blog.csdn.net/UncleMing5371/article/details/54291221