基本概念
用五個標志域來存儲結點的結構
以這種結點結構構成的二叉鏈表作為二叉樹的存儲結構叫做線索鏈表（Threaded Linked Lists）
線索指向結點前驅和後繼的指針
線索二叉樹（Threaded Binary Tree）加上線索的二叉樹
線索化對二叉樹以某種次序遍歷使其變為線索二叉樹的過程
在結構示意圖中指針用實線表示線索通常用虛線表示
線索二叉樹的存儲結構
二叉樹按中序線索化的算法
線索二叉樹上常用運算
查找某結點*p在指定次序下的前趨和後繼結點
在中序線索二叉樹中查找指定結點*p的中序後繼結點和中序前趨結點
１若結點*p的左子樹（或右子樹）非空則*p的中序前趨（或中序後繼）是從*p的左孩子（或右孩子）開始往下查找由於二叉鏈表中結點的鏈域是向下鏈接的所以在非線索二叉樹中亦同樣容易找到*p的中序前趨（或中序後繼）
２若結點*p的左子樹（或右子樹）為空則在中序線索二叉樹中是通過*p的左線索（或右線索）直接找到*p的中序前趨（或中序後繼）但中序線索一般都是向上指向其祖先結點而二叉鏈表中沒有向上的鏈接因此在這種情況下對於非線索二叉樹僅從*p出發無法找到其中序前趨（或中序後繼）而必須從根結點開始中序遍歷才能找到*p的中序前趨（或中序後繼）
在後序線索二叉樹中查找指定結點*p的後序前趨結點
１若*p的左子樹為空同p>lchild是前趨線索指示其後序前趨結點
２若*p的左子樹非空則p>lchild不是前趨線索當*p的右子樹非空時*p的右孩子必是其後序前趨
在後序線索二叉樹中查找指定結點*p的後序後繼結點
１若*p是根則*p是該二叉樹後序遍歷過程中最後一個訪問到的結點
２若*p是其雙親的右孩子則*p的後序後繼結點就是其雙親結點
３若*p是其雙親的左孩子但*p無右兄弟時*p的後序後繼結點是其雙親結點
４若*p是其雙親的左孩子但*p有右兄弟則*p的後序後繼是其雙親的右子樹中第一個後序遍歷到的結點它是該子樹中最左下的葉結點
遍歷線索二叉樹
遍歷某種次序的線索二叉樹只要從該次序下的開始結點出發反復找到結點在該次序下的後繼直至終端結點
From:http://tw.wingwit.com/Article/program/sjjg/201311/23149.html
