Snowdream

發現居然還是Pascal描述，親切啊親切

http://iprai.hust.edu.cn/icl2002/algorithm/datastructure/basic/binary_tree/chapter5_4.htm

線索二叉樹

當用二叉鏈表作為二叉樹的存儲結構時，因為每個結點中只有指向其左、右兒子結點的指針，所以從任一結點出發只能直接找到該結點的左、右兒子。在一般情況下靠它無法直接找到該結點在某種遍歷序下的前驅和后繼結點。如果在每個結點中增加指向其前驅和后繼結點的指針，將降低存儲空間的效率。

我們可以證明：在n個結點的二叉鏈表中含有n+1個空指針。因為含n個結點的二叉鏈表中含有個指針，除了根結點，每個結點都有一個從父結點指向該結點的指針，因此一共使用了n-1個指針，所以在n個結點的二叉鏈表中含有n+1個空指針。

因此可以利用這些空指針，存放指向結點在某種遍歷次序下的前驅和后繼結點的指針。這種附加的指針稱為線索，加上了線索的二叉鏈表稱為線索鏈表，相應的二叉樹稱為線索二叉樹。為了區分一個結點的指針是指向其兒子的指針，還是指向其前驅或后繼結點的線索，可在每個結點中增加兩個線索標志。這樣，線索二叉樹結點類型定義為：

其中ltag為左線索標志，rtag為右線索標志。它們的含義是:

• ltag=0，LeftChild是指向結點左兒子的指針；
• ltag=1，LeftChild是指向結點前驅的左線索。
  
• rtag=0，RightChild是指向結點右兒子的指針；
• rtag=1，RihgtChild是指向結點后繼的右線索。

例如圖13(a)是一棵中序線索二叉樹，它的線索鏈表如圖13(b)所示。

(a)

(b)

圖13 線索二叉樹及其線索鏈表

圖13(b)中，在二叉樹的線索鏈表上增加了一個頭結點，其LeftChild指針指向二叉樹的根結點，其RightChild指針指向中序遍歷時的最后一個結點。另外，二叉樹中依中序列表的第一個結點的LeftChild指針，和最后一個結點的RightChild指針都指向頭結點。這就像為二叉樹建立了一個雙向線索鏈表，既可從第一個結點起，順著后繼進行遍歷，也可從最后一個結點起順著前驅進行遍歷。

如何在線索二叉樹中找結點的前驅和后繼結點？以圖13的中序線索二叉樹為例。樹中所有葉結點的右鏈是線索，因此葉結點的RightChild指向該結點的后繼結點，如圖13中結點"b"的后繼為結點"*"。當一個內部結點右線索標志為0時，其RightChild指針指向其右兒子，因此無法由RightChild得到其后繼結點。然而，由中序遍歷的定義可知，該結點的后繼應是遍歷其右子樹時訪問的第一個結點，即右子樹中最左下的結點。例如在找結點"*"的后繼時，首先沿右指針找到其右子樹的根結點"-"，然后沿其LeftChild指針往下直至其左線索標志為1的結點，即為其后繼結點(在圖中是結點"c")。類似地，在中序線索樹中找結點的前驅結點的規律是：若該結點的左線索標志為1，則LeftChild為線索，直接指向其前驅結點，否則遍歷左子樹時最后訪問的那個結點，即左子樹中最右下的結點為其前驅結點。由此可知，若線索二叉樹的高度為h，則在最壞情況下，可在O(h)時間內找到一個結點的前驅或后繼結點。在對中序線索二叉樹進行遍歷時，無須像非線索樹的遍歷那樣，利用遞歸引入棧來保存待訪問的子樹信息。

對一棵非線索二叉樹以某種次序遍歷使其變為一棵線索二叉樹的過程稱為二叉樹的線索化。由于線索化的實質是將二叉鏈表中的空指針改為指向結點前驅或后繼的線索，而一個結點的前驅或后繼結點的信息只有在遍歷時才能得到，因此線索化的過程即為在遍歷過程中修改空指針的過程。為了記下遍歷過程中訪問結點的先后次序，可附設一個指針pre始終指向剛剛訪問過的結點。當指針p指向當前訪問的結點時，pre指向它的前驅。由此也可推知pre所指結點的后繼為p所指的當前結點。這樣就可在遍歷過程中將二叉樹線索化。對于找前驅和后繼結點這二種運算而言，線索樹優于非線索樹。但線索樹也有其缺點。在進行插人和刪除操作時，線索樹比非線索樹的時間開銷大。原因在于在線索樹中進行插人和刪除時，除了修改相應的指針外，還要修改相應的線索。