線索二叉樹的原理
通過考察各種二叉鏈表芹关，不管兒叉樹的形態(tài)如何皿桑，空鏈域的個(gè)數(shù)總是多過非空鏈域的個(gè)數(shù)。準(zhǔn)確的說嘹朗，n各結(jié)點(diǎn)的二叉鏈表共有2n個(gè)鏈域师妙，非空鏈域?yàn)閚-1個(gè)，但其中的空鏈域卻有n+1個(gè)屹培。如下圖所示默穴。
因此，提出了一種方法惫谤，利用原來(lái)的空鏈域存放指針壁顶，指向樹中其他結(jié)點(diǎn)。這種指針稱為線索溜歪。
記ptr指向二叉鏈表中的一個(gè)結(jié)點(diǎn)若专，以下是建立線索的規(guī)則：
（1）如果ptr->lchild為空，則存放指向中序遍歷序列中該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)蝴猪。這個(gè)結(jié)點(diǎn)稱為ptr的中序前驅(qū)调衰；
（2）如果ptr->rchild為空，則存放指向中序遍歷序列中該結(jié)點(diǎn)的后繼結(jié)點(diǎn)自阱。這個(gè)結(jié)點(diǎn)稱為ptr的中序后繼嚎莉；
顯然，在決定lchild是指向左孩子還是前驅(qū)沛豌，rchild是指向右孩子還是后繼趋箩，需要一個(gè)區(qū)分標(biāo)志的赃额。因此，我們?cè)诿總€(gè)結(jié)點(diǎn)再增設(shè)兩個(gè)標(biāo)志域ltag和rtag叫确，注意ltag和rtag只是區(qū)分0或1數(shù)字的布爾型變量跳芳，其占用內(nèi)存空間要小于像lchild和rchild的指針變量。結(jié)點(diǎn)結(jié)構(gòu)如下所示竹勉。
其中：
（1）ltag為0時(shí)指向該結(jié)點(diǎn)的左孩子飞盆，為1時(shí)指向該結(jié)點(diǎn)的前驅(qū)；
（2）rtag為0時(shí)指向該結(jié)點(diǎn)的右孩子次乓，為1時(shí)指向該結(jié)點(diǎn)的后繼吓歇；
（3）因此對(duì)于上圖的二叉鏈表圖可以修改為下圖的養(yǎng)子。
線索化的實(shí)質(zhì)就是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索票腰。由于前驅(qū)和后繼信息只有在遍歷該二叉樹時(shí)才能得到城看，所以，線索化的過程就是在遍歷的過程中修改空指針的過程丧慈。
有了線索二叉樹后析命，對(duì)它進(jìn)行遍歷時(shí)主卫，其實(shí)就等于操作一個(gè)雙向鏈表結(jié)構(gòu)逃默。
和雙向鏈表結(jié)點(diǎn)一樣，在二叉樹鏈表上添加一個(gè)頭結(jié)點(diǎn)簇搅，如下圖所示完域，并令其lchild域的指針指向二叉樹的根結(jié)點(diǎn)（圖中第一步），其rchild域的指針指向中序遍歷訪問時(shí)的最后一個(gè)結(jié)點(diǎn)（圖中第二步）瘩将。反之吟税，令二叉樹的中序序列中第一個(gè)結(jié)點(diǎn)中，lchild域指針和最后一個(gè)結(jié)點(diǎn)的rchild域指針均指向頭結(jié)點(diǎn)（圖中第三和第四步）姿现。這樣的好處是：我們既可以從第一個(gè)結(jié)點(diǎn)起順后繼進(jìn)行遍歷肠仪，也可以從最后一個(gè)結(jié)點(diǎn)起順前驅(qū)進(jìn)行遍歷。
例子：
