引入線索二叉樹的目的

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

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