線索二叉樹的原理

通過考察各種二叉鏈表，不管兒叉樹的形態(tài)如何，空鏈域的個數(shù)總是多過非空鏈域的個數(shù)。準確的說，n各結(jié)點的二叉鏈表共有2n個鏈域，非空鏈域為n-1個，但其中的空鏈域卻有n+1個。如下圖所示。

因此，提出了一種方法，利用原來的空鏈域存放指針，指向樹中其他結(jié)點。這種指針稱為線索。

記ptr指向二叉鏈表中的一個結(jié)點，以下是建立線索的規(guī)則：

（1）如果ptr->lchild為空，則存放指向中序遍歷序列中該結(jié)點的前驅(qū)結(jié)點。這個結(jié)點稱為ptr的中序前驅(qū)；

（2）如果ptr->rchild為空，則存放指向中序遍歷序列中該結(jié)點的后繼結(jié)點。這個結(jié)點稱為ptr的中序后繼；

顯然，在決定lchild是指向左孩子還是前驅(qū)，rchild是指向右孩子還是后繼，需要一個區(qū)分標志的。因此，我們在每個結(jié)點再增設(shè)兩個標志域ltag和rtag，注意ltag和rtag只是區(qū)分0或1數(shù)字的布爾型變量，其占用內(nèi)存空間要小于像lchild和rchild的指針變量。結(jié)點結(jié)構(gòu)如下所示。

其中：

（1）ltag為0時指向該結(jié)點的左孩子，為1時指向該結(jié)點的前驅(qū)；

（2）rtag為0時指向該結(jié)點的右孩子，為1時指向該結(jié)點的后繼；

（3）因此對于上圖的二叉鏈表圖可以修改為下圖的養(yǎng)子。

線索化的實質(zhì)就是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索。由于前驅(qū)和后繼信息只有在遍歷該二叉樹時才能得到，所以，線索化的過程就是在遍歷的過程中修改空指針的過程。

有了線索二叉樹后，對它進行遍歷時，其實就等于操作一個雙向鏈表結(jié)構(gòu)。

和雙向鏈表結(jié)點一樣，在二叉樹鏈表上添加一個頭結(jié)點，如下圖所示，并令其lchild域的指針指向二叉樹的根結(jié)點（圖中第一步），其rchild域的指針指向中序遍歷訪問時的最后一個結(jié)點（圖中第二步）。反之，令二叉樹的中序序列中第一個結(jié)點中，lchild域指針和最后一個結(jié)點的rchild域指針均指向頭結(jié)點（圖中第三和第四步）。這樣的好處是：我們既可以從第一個結(jié)點起順后繼進行遍歷，也可以從最后一個結(jié)點起順前驅(qū)進行遍歷。

例子：