線索二叉樹，是一種在計算機科學(xué)中添加了直接指向節(jié)點的前驅(qū)和后繼的指針的二叉樹。線索二叉樹能線性地遍歷二叉樹，從而比遞歸的中序遍歷更快。使用線索二叉樹也能夠方便地找到一個節(jié)點的父節(jié)點，這比顯式地使用父節(jié)點指針或者棧效率更高。這在棧空間有限，或者無法使用存儲父節(jié)點的棧時很有作用（對于通過深度優(yōu)先搜索來查找父節(jié)點而言)。
理論概念
當(dāng)用二叉鏈表作為二叉樹的存儲結(jié)構(gòu)時，因為每個結(jié)點中只有指向其左、右兒子結(jié)點的指針，所以從任一結(jié)點出發(fā)只能直接找到該結(jié)點的左、右兒子。在一般情況下靠它無法直接找到該結(jié)點在某種遍歷序下的前驅(qū)和后繼結(jié)點。如果在每個結(jié)點中增加指向其前驅(qū)和后繼結(jié)點的指針，將降低存儲空間的效率。
我們可以證明：在n個結(jié)點的二叉鏈表中含有n+1個空指針。因為含n個結(jié)點的二叉鏈表中含有2n個指針，除了根結(jié)點，每個結(jié)點都有一個從父結(jié)點指向該結(jié)點的指針，因此一共使用了n-1個指針，所以在n個結(jié)點的二叉鏈表中含有n+1個空指針。
因此可以利用這些空指針，存放指向結(jié)點在某種遍歷次序下的前驅(qū)和后繼結(jié)點的指針。這種附加的指針稱為線索，加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹(ThreadedBinaryTree)。根據(jù)線索性質(zhì)的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。
主要結(jié)構(gòu)
例如圖(a)是一棵中序線索二叉樹，它的線索鏈表如圖(b)所示。
(a)
(b)
圖(b)中，在二叉樹的線索鏈表上增加了一個頭結(jié)點，其LeftChild指針指向二叉樹的根結(jié)點，其RightChild指針指向中序遍歷時的最后一個結(jié)點。另外，二叉樹中依中序列表的第一個結(jié)點的LeftChild指針，和最后一個結(jié)點的RightChild指針都指向頭結(jié)點。這就像為二叉樹建立了一個雙向線索鏈表，既可從第一個結(jié)點起，順著后繼進行遍歷，也可從最后一個結(jié)點起順著前驅(qū)進行遍歷。
如何在線索二叉樹中找結(jié)點的前驅(qū)和后繼結(jié)點？以圖13的中序線索二叉樹為例。樹中所有葉結(jié)點的右鏈是線索，因此葉結(jié)點的RightChild指向該結(jié)點的后繼結(jié)點，如圖13中結(jié)點"b"的后繼為結(jié)點"*"。當(dāng)一個內(nèi)部結(jié)點右線索標志為0時，其RightChild指針指向其右兒子，因此無法由RightChild得到其后繼結(jié)點。然而，由中序遍歷的定義可知，該結(jié)點的后繼應(yīng)是遍歷其右子樹時訪問的第一個結(jié)點，即右子樹中最左下的結(jié)點。例如在找結(jié)點"*"的后繼時，首先沿右指針找到其右子樹的根結(jié)點"-"，然后沿其LeftChild指針往下直至其左線索標志為1的結(jié)點，即為其后繼結(jié)點(在圖中是結(jié)點"c")。類似地，在中序線索樹中找結(jié)點的前驅(qū)結(jié)點的規(guī)律是：若該結(jié)點的左線索標志為1，則LeftChild為線索，直接指向其前驅(qū)結(jié)點，否則遍歷左子樹時最后訪問的那個結(jié)點，即左子樹中最右下的結(jié)點為其前驅(qū)結(jié)點。由此可知，若線索二叉樹的高度為h，則在最壞情況下，可在O(h)時間內(nèi)找到一個結(jié)點的前驅(qū)或后繼結(jié)點。在對中序線索二叉樹進行遍歷時，無須像非線索樹的遍歷那樣，利用遞歸引入棧來保存待訪問的子樹信息。
對一棵非線索二叉樹以某種次序遍歷使其變?yōu)橐豢镁€索二叉樹的過程稱為二叉樹的線索化。由于線索化的實質(zhì)是將二叉鏈表中的空指針改為指向結(jié)點前驅(qū)或后繼的線索，而一個結(jié)點的前驅(qū)或后繼結(jié)點的信息只有在遍歷時才能得到，因此線索化的過程即為在遍歷過程中修改空指針的過程。為了記下遍歷過程中訪問結(jié)點的先后次序，可附設(shè)一個指針pre始終指向剛剛訪問過的結(jié)點。當(dāng)指針p指向當(dāng)前訪問的結(jié)點時，pre指向它的前驅(qū)。由此也可推知pre所指結(jié)點的后繼為p所指的當(dāng)前結(jié)點。這樣就可在遍歷過程中將二叉樹線索化。對于找前驅(qū)和后繼結(jié)點這二種運算而言，線索樹優(yōu)于非線索樹。但線索樹也有其缺點。在進行插人和刪除操作時，線索樹比非線索樹的時間開銷大。原因在于在線索樹中進行插人和刪除時，除了修改相應(yīng)的指針外，還要修改相應(yīng)的線索。
參考資料 >