線索二叉樹的原理
通過考察各種二叉鏈表，不管兒叉樹的形態(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é)點再增設兩個標志域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ū)進行遍歷槽唾。
例子：
