線索二叉樹是指在二叉樹的結(jié)點(diǎn)上加上線索的二叉樹。這里的線索指的是對(duì)于n個(gè)結(jié)點(diǎn)的二叉樹，在二叉鏈存儲(chǔ)結(jié)構(gòu)中有n+1個(gè)空鏈域，利用這些空鏈域存放在某種遍歷次序下該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針。本文我們就將以這些指針為線索來(lái)為大家解析線索二叉樹。

一個(gè)二叉樹通過(guò)如下的方法“穿起來(lái)”：所有原本為空的右孩子指針改為指向該節(jié)點(diǎn)在中序序列中的后繼，所有原本為空的左孩子指針改為指向該節(jié)點(diǎn)的中序序列的前驅(qū)。

上圖這種加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹。

鏈接規(guī)則：

1.結(jié)點(diǎn)左子樹為空，利用左孩子指針指向它的前驅(qū)結(jié)點(diǎn)

2.結(jié)點(diǎn)右子樹為空，利用右孩子指針指向它的后繼結(jié)點(diǎn)

3.注意：所有前驅(qū)和后繼只能按照一種遍歷邏輯（例如：中序）

通過(guò)考察各種二叉鏈表，不管兒叉樹的形態(tài)如何，空鏈域的個(gè)數(shù)總是多過(guò)非空鏈域的個(gè)數(shù)。準(zhǔn)確的說(shuō)，n各結(jié)點(diǎn)的二叉鏈表共有2n個(gè)鏈域，非空鏈域?yàn)閚-1個(gè)，但其中的空鏈域卻有n+1個(gè)。

根據(jù)線索性質(zhì)的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。線索鏈表解決了無(wú)法直接找到該結(jié)點(diǎn)在某種遍歷序列中的前驅(qū)和后繼結(jié)點(diǎn)的問(wèn)題，解決了二叉鏈表找左、右孩子困難的問(wèn)題。

實(shí)際上也就是當(dāng)二叉樹的左右孩子結(jié)點(diǎn)為NUll的時(shí)候,指向的地址是浪費(fèi)的,為了減少浪費(fèi)我們可以通過(guò)將其指向前驅(qū)或者后續(xù)來(lái)利用這些無(wú)用的空間,提升查找速度,值得注意的是實(shí)際使用中我們要根據(jù)選擇的二叉樹遍歷規(guī)則來(lái)進(jìn)行對(duì)應(yīng)的指向(前序、中序、后序)要保持一直.一般來(lái)說(shuō)我們使用中序遍歷進(jìn)行二叉樹線索化。

二叉樹的遍歷本質(zhì)上是將一個(gè)復(fù)雜的非線性結(jié)構(gòu)轉(zhuǎn)換為線性結(jié)構(gòu)，使每個(gè)結(jié)點(diǎn)都有了唯一前驅(qū)和后繼（第一個(gè)結(jié)點(diǎn)無(wú)前驅(qū)，最后一個(gè)結(jié)點(diǎn)無(wú)后繼）。對(duì)于二叉樹的一個(gè)結(jié)點(diǎn)，查找其左右子女是方便的，其前驅(qū)后繼只有在遍歷中得到。為了容易找到前驅(qū)和后繼，有兩種方法。一是在結(jié)點(diǎn)結(jié)構(gòu)中增加向前和向后的指針，這種方法增加了存儲(chǔ)開銷，不可?。欢抢枚鏄涞目真溨羔?。

建立線索二叉樹，或者說(shuō)對(duì)二叉樹線索化，實(shí)質(zhì)上就是遍歷一棵二叉樹。在遍歷過(guò)程中，訪問(wèn)結(jié)點(diǎn)的操作是檢查當(dāng)前的左，右指針域是否為空，將它們改為指向前驅(qū)結(jié)點(diǎn)或后續(xù)結(jié)點(diǎn)的線索。為實(shí)現(xiàn)這一過(guò)程，設(shè)指針pre始終指向剛剛訪問(wèn)的結(jié)點(diǎn)，即若指針p指向當(dāng)前結(jié)點(diǎn)，則pre指向它的前驅(qū)，以便設(shè)線索。

二叉樹本身其實(shí)就是一種特殊的樹形結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)，而線索二叉樹又是特殊的二叉樹。所以，線索二叉樹本身的特殊性是值得我們探究的。在本站的數(shù)據(jù)結(jié)構(gòu)和算法教程中我們也將接觸到更多有意思的數(shù)據(jù)結(jié)構(gòu)，讓我們?cè)跀?shù)據(jù)結(jié)構(gòu)世界里初窺門徑。