引入線索二元樹的目的

引入線索二元樹的目的是找一個節點的前驅後繼的時候，比非二叉線索樹方便快捷。按照某種遍歷方式對二元樹進行遍歷，可以把二元樹中所有結點排序為一個線性序列。

當用二叉連結串列作為二元樹的儲存結構時，因為每個結點中只有指向其左、右兒子結點的指標，所以從任一結點出發只能直接找到該結點的左、右兒子。在一般情況下靠它無法直接找到該結點在某種遍歷序下的前驅和後繼結點。如果在每個結點中增加指向其前驅和後繼結點的指標，將降低儲存空間的效率。我們可以證明：在n個結點的二叉連結串列中含有n+1個空指標。因為含n個結點的二叉連結串列中含有個指標，除了根結點，每個結點都有一個從父結點指向該結點的指標，因此一共使用了n-1個指標，所以在n個結點的二叉連結串列中含有n+1個空指標。因此可以利用這些空指標，存放指向結點在某種遍歷次序下的前驅和後繼結點的指標。這種附加的指標稱為線索，加上了線索的二叉連結串列稱為線索連結串列，相應的二元樹稱為線索二元樹(ThreadedBinaryTree)。根據線索性質的不同，線索二元樹可分為前序線索二元樹、中序線索二元樹和後序線索二元樹三種。