github地址：
https://github.com/arkulo56/thought/blob/master/software/dataStruct/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E6%A0%91_%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91.md

線索二叉樹

產(chǎn)品分類是樹型結構，如果要頻繁的按照一定的次序訪問產(chǎn)品分類（遍歷）

1. 有效的利用了二叉鏈表中的空指針
2. 對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程稱為線索化
3. 一棵有n個節(jié)點的二叉樹，左右孩子用到的指針是n-1,留給線索的空指針是n+1

<img src="https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/xiansuo_binaryTree.png" width="600" />

創(chuàng)建

按照中序遍歷訪問每一個節(jié)點，訪問的過程中，用線索取代空指針。

1. 若上次訪問的節(jié)點的右指針為空，則將當前訪問的節(jié)點地址填入，并置右標識位為1（后序）
2. 若當前訪問的節(jié)點的左指針為空，則將上次訪問的節(jié)點地址填入，并置做標識位為1（前序）

注：從圖2的H節(jié)點開始中序遍歷，按照上述兩條規(guī)則就可建立線索二叉樹了

查詢

訪問前驅(qū)后繼的方法是相同的，下面介紹后繼，前驅(qū)反過來就行了

1. 如果當前節(jié)點P的右標識位為0，則P->rchild為線索，指向P的后繼
2. 如果節(jié)點P的右標識位為1，則P的后繼節(jié)點是右子樹中序遍歷的第一個節(jié)點。也就是沿著P的右孩子開始，按照左鏈（左孩子）往下查，直至找到一個沒有左孩子的節(jié)點為止。

注：圖3中A節(jié)點就是比較特殊的節(jié)點，他的前驅(qū)后繼就得通過左右子樹確定