二叉樹鏈表中有很多空指針，比如葉子節(jié)點，會有左右孩子兩個空指針。如何把這些空指針利用起來呢？那就是線索二叉樹

在這些節(jié)點上，可以存儲按照二叉樹某種遍歷順序的前后節(jié)點，這樣就不需要每次都遍歷二叉樹，從而快速點位節(jié)點。

哪一種遍歷順序是最有效的呢？要求是最好有兩個空指針的節(jié)點在非空節(jié)點的中間，這樣就可以記錄前前驅(qū)后繼節(jié)點。?這個遍歷方法叫中序遍歷方法。這樣包含線索的二叉樹，叫做線索二叉樹

線索二叉樹節(jié)點

因為不是所有的節(jié)點都包含兩個空指針，如果只含有一個空指針的時候，就無法判斷，另一個非空指針是指向前驅(qū)或者后繼或者是孩子節(jié)點，所以，在節(jié)點結(jié)構(gòu)中增加2bit，用于指示是指針的類型。

線索二叉樹的實現(xiàn)

首先定義數(shù)據(jù)類型

定義節(jié)點：注意枚舉的使用，默認(rèn)從0開始

只有構(gòu)建了線索二叉樹，才能使用非迭代的方法，通過前驅(qū)和后繼的方法，通過迭代遍歷二叉樹 。

線索二叉樹其實是一個線性雙循環(huán)鏈表，里面有一個很關(guān)鍵的頭結(jié)點，這個是線性表中的結(jié)構(gòu)，不同于根節(jié)點

?