線索二叉樹的原理
通過考察各種二叉鏈表存炮，不管兒叉樹的形態(tài)如何隶校，空鏈域的個數(shù)總是多過非空鏈域的個數(shù)。準(zhǔn)確的說忍坷，n各結(jié)點(diǎn)的二叉鏈表共有2n個鏈域粘舟，非空鏈域?yàn)閚-1個，但其中的空鏈域卻有n+1個承匣。如下圖所示蓖乘。
因此，提出了一種方法韧骗，利用原來的空鏈域存放指針嘉抒，指向樹中其他結(jié)點(diǎn)。這種指針稱為線索袍暴。
記ptr指向二叉鏈表中的一個結(jié)點(diǎn)些侍，以下是建立線索的規(guī)則：
（1）如果ptr->lchild為空，則存放指向中序遍歷序列中該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)政模。這個結(jié)點(diǎn)稱為ptr的中序前驅(qū)岗宣；
（2）如果ptr->rchild為空，則存放指向中序遍歷序列中該結(jié)點(diǎn)的后繼結(jié)點(diǎn)淋样。這個結(jié)點(diǎn)稱為ptr的中序后繼耗式；
顯然，在決定lchild是指向左孩子還是前驅(qū)趁猴，rchild是指向右孩子還是后繼刊咳，需要一個區(qū)分標(biāo)志的。因此儡司，我們在每個結(jié)點(diǎn)再增設(shè)兩個標(biāo)志域ltag和rtag娱挨，注意ltag和rtag只是區(qū)分0或1數(shù)字的布爾型變量，其占用內(nèi)存空間要小于像lchild和rchild的指針變量捕犬。結(jié)點(diǎn)結(jié)構(gòu)如下所示跷坝。
其中：
（1）ltag為0時指向該結(jié)點(diǎn)的左孩子，為1時指向該結(jié)點(diǎn)的前驅(qū)碉碉；
（2）rtag為0時指向該結(jié)點(diǎn)的右孩子柴钻，為1時指向該結(jié)點(diǎn)的后繼；
（3）因此對于上圖的二叉鏈表圖可以修改為下圖的養(yǎng)子垢粮。
線索化的實(shí)質(zhì)就是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索顿颅。由于前驅(qū)和后繼信息只有在遍歷該二叉樹時才能得到，所以，線索化的過程就是在遍歷的過程中修改空指針的過程粱腻。
有了線索二叉樹后，對它進(jìn)行遍歷時斩跌，其實(shí)就等于操作一個雙向鏈表結(jié)構(gòu)绍些。
和雙向鏈表結(jié)點(diǎn)一樣，在二叉樹鏈表上添加一個頭結(jié)點(diǎn)耀鸦，如下圖所示柬批，并令其lchild域的指針指向二叉樹的根結(jié)點(diǎn)（圖中第一步），其rchild域的指針指向中序遍歷訪問時的最后一個結(jié)點(diǎn)（圖中第二步）袖订。反之氮帐，令二叉樹的中序序列中第一個結(jié)點(diǎn)中，lchild域指針和最后一個結(jié)點(diǎn)的rchild域指針均指向頭結(jié)點(diǎn)（圖中第三和第四步）洛姑。這樣的好處是：我們既可以從第一個結(jié)點(diǎn)起順后繼進(jìn)行遍歷上沐，也可以從最后一個結(jié)點(diǎn)起順前驅(qū)進(jìn)行遍歷。
例子：
