定義
按照某種遍曆方式對二叉樹進行遍曆，可以把二叉樹中所有結點排列為一個線性序列。在該序列中，除第一個結點外，每個結點有且僅有一個直接前驅結點；除最後一個結點外，每個結點有且僅有一個直接後繼結點。但是，二叉樹中每個結點在這個序列中的直接前驅結點和直接後繼結點是什麼，二叉樹的存儲結構中并沒有反映出來，隻能在對二叉樹遍曆的動态過程中得到這些信息。為了保留結點在某種遍曆序列中直接前驅和直接後繼的位置信息，可以利用二叉樹的二叉鍊表存儲結構中的那些空指針域來指示。這些指向直接前驅結點和指向直接後繼結點的指針被稱為線索（thread），加了線索的二叉樹稱為線索二叉樹。
構建
建立線索二叉樹，或者說對二叉樹線索化，實質上就是遍曆一棵二叉樹。在遍曆過程中，訪問結點的操作是檢查當前的左，右指針域是否為空，将它們改為指向前驅結點或後續結點的線索。為實現這一過程，設指針pre始終指向剛剛訪問的結點，即若指針p指向當前結點，則pre指向它的前驅，以便設線索。
另外，在對一顆二叉樹加線索時，必須首先申請一個頭結點，建立頭結點與二叉樹的根結點的指向關系，對二叉樹線索化後，還需建立最後一個結點與頭結點之間的線索。
圖1是建立中序二叉樹的遞歸算法，其中pre為全局變量。
圖2進行中序線索化的算法：
線索二叉樹查找前驅和後繼：
（1）中序線索二叉樹：若結點的ltag=1，lchild指向其前驅；否則，該結點的前驅是以該結點為根的左子樹上按中序遍曆的最後一個結點。若rtag=1，rchild指向其後繼；否則，該結點的後繼是以該結點為根的右子樹上按中序遍曆的第一個結點。
求後繼的算法如圖3：
求前驅的算法如圖4：
（2）後序線索二叉樹：
在後序線索二叉樹中查找結點*p的前驅：若結點*p無左子樹，則p->lchild指向其前驅；否則，若結點*p有左子樹，當其右子樹為空時，其左子樹的根（即p->lrchild）為其後序前驅。當其右子樹非空時，其右子樹的根（即p->rchild）為其後序前驅。
在後序線索二叉樹中查找結點*p的後繼：若結點*p為根，則無後繼；若結點*p為其雙親的右孩子，則其後繼為其雙親；若結點*p為其雙親的左孩子，且雙親無右子女，則其後繼為其雙親；若結點*p為其雙親的左孩子，且雙親有右子女，則結點*p的後繼是其雙親的右子樹中按後序遍曆的第一個結點。所以，求後序線索二叉樹中結點的後繼要知道其雙親的信息，要使用棧，所以說後序線索二叉樹是不完善的。
（3）先序線索二叉樹：
在先序線索二叉樹中查找結點的後繼較容易，而查找前驅要知道其雙親的信息，要使用棧，所以說先序線索二叉樹也是不完善的。
本質
二叉樹的遍曆本質上是将一個複雜的非線性結構轉換為線性結構，使每個結點都有了唯一前驅和後繼（第一個結點無前驅，最後一個結點無後繼）。對于二叉樹的一個結點，查找其左右子女是方便的，其前驅後繼隻有在遍曆中得到。為了容易找到前驅和後繼，有兩種方法。一是在結點結構中增加向前和向後的指針，這種方法增加了存儲開銷，不可取；二是利用二叉樹的空鍊指針。
優勢與不足
優勢
(1)利用線索二叉樹進行中序遍曆時，不必采用堆棧處理，速度較一般二叉樹的遍曆速度快，且節約存儲空間。
(2)任意一個結點都能直接找到它的前驅和後繼結點。
不足
(1)結點的插入和删除麻煩，且速度也較慢。
(2)線索子樹不能共用。
