線索樹

常見的關於線索樹的算法設計題目有：對一個二叉樹進行線索化(前序、中序或後序)；對一個線索樹在沒有棧的支持下進行遍歷，一般這樣的線索樹是中序線索樹。 同理，可以對二叉樹進行中序和後序線索化。 在沒有棧的支持下的對線索樹的遍歷的算法是經常出現的考題，考慮到中序線索樹的特點，對中序線索樹不僅可以進行中序的遍歷，還可以進行前序和後序的遍歷。

線索樹

常見類型

常見的關於線索樹的算法設計題目有：對一個二叉樹進行線索化(前序、中序或後序)；對一個線索樹在沒有棧的支持下進行遍歷，一般這樣的線索樹是中序線索樹。對二叉樹進行線索化的算法比較簡單，只要設一個pre指針。若要進行前序線索化，就對此二叉樹進行前序遍歷，pre指向當前訪問結點的直接前驅，然後將結點的空指針域按照線索樹的定義相連，遍歷結束時，這棵二叉樹也就前序線索化成功了。同理，可以對二叉樹進行中序和後序線索化。在沒有棧的支持下的對線索樹的遍歷的算法是經常出現的考題，考慮到中序線索樹的特點，對中序線索樹不僅可以進行中序的遍歷，還可以進行前序和後序的遍歷。值得提出的是，後序的線索樹若沒有指向雙親的指針或者不用棧，則無法對其進行遍歷。

實例

例1（1998年東南大學）給出中序線索樹的結點結構，並畫出一個具有頭結點和6個樹結點的中序線索樹，試寫一算法在不使用棧和遞歸的情況下前序遍歷一中序線索樹，並分析它的時間複雜度。

【解答】具有頭結點和6個樹結點的中序線索樹。