Snowdream

發(fā)現(xiàn)居然還是Pascal描述，親切啊親切

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

線索二叉樹

當(dāng)用二叉鏈表作為二叉樹的存儲結(jié)構(gòu)時(shí)，因?yàn)槊總€(gè)結(jié)點(diǎn)中只有指向其左、右兒子結(jié)點(diǎn)的指針，所以從任一結(jié)點(diǎn)出發(fā)只能直接找到該結(jié)點(diǎn)的左、右兒子。在一般情況下靠它無法直接找到該結(jié)點(diǎn)在某種遍歷序下的前驅(qū)和后繼結(jié)點(diǎn)。如果在每個(gè)結(jié)點(diǎn)中增加指向其前驅(qū)和后繼結(jié)點(diǎn)的指針，將降低存儲空間的效率。

我們可以證明：在n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n+1個(gè)空指針。因?yàn)楹琻個(gè)結(jié)點(diǎn)的二叉鏈表中含有個(gè)指針，除了根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)都有一個(gè)從父結(jié)點(diǎn)指向該結(jié)點(diǎn)的指針，因此一共使用了n-1個(gè)指針，所以在n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n+1個(gè)空指針。

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

其中l(wèi)tag為左線索標(biāo)志，rtag為右線索標(biāo)志。它們的含義是:

• ltag=0，LeftChild是指向結(jié)點(diǎn)左兒子的指針；
• ltag=1，LeftChild是指向結(jié)點(diǎn)前驅(qū)的左線索。
  
• rtag=0，RightChild是指向結(jié)點(diǎn)右兒子的指針；
• rtag=1，RihgtChild是指向結(jié)點(diǎn)后繼的右線索。

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

(a)

(b)

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

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

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

對一棵非線索二叉樹以某種次序遍歷使其變?yōu)橐豢镁€索二叉樹的過程稱為二叉樹的線索化。由于線索化的實(shí)質(zhì)是將二叉鏈表中的空指針改為指向結(jié)點(diǎn)前驅(qū)或后繼的線索，而一個(gè)結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)的信息只有在遍歷時(shí)才能得到，因此線索化的過程即為在遍歷過程中修改空指針的過程。為了記下遍歷過程中訪問結(jié)點(diǎn)的先后次序，可附設(shè)一個(gè)指針pre始終指向剛剛訪問過的結(jié)點(diǎn)。當(dāng)指針p指向當(dāng)前訪問的結(jié)點(diǎn)時(shí)，pre指向它的前驅(qū)。由此也可推知pre所指結(jié)點(diǎn)的后繼為p所指的當(dāng)前結(jié)點(diǎn)。這樣就可在遍歷過程中將二叉樹線索化。對于找前驅(qū)和后繼結(jié)點(diǎn)這二種運(yùn)算而言，線索樹優(yōu)于非線索樹。但線索樹也有其缺點(diǎn)。在進(jìn)行插人和刪除操作時(shí)，線索樹比非線索樹的時(shí)間開銷大。原因在于在線索樹中進(jìn)行插人和刪除時(shí)，除了修改相應(yīng)的指針外，還要修改相應(yīng)的線索。