線索二叉樹
二叉樹的基本定義結構我們都很熟悉咳胃，節(jié)點數(shù)據(jù)加上孩紙指針笋庄，左孩子指娘家泞遗，右孩子指婆家惰许，我們來看這個例子：
我們會發(fā)現(xiàn)，有些孩子并沒有地方可以去史辙，例子中的樹一共十個結點汹买，十一個空閑指針，由此引出我們對于空閑指針的計算公式：一個有 n 個結點的二叉樹有 2n 個指針域聊倔，而 n 個結點會產生 n-1 個分支晦毙，每個分支對應其指向孩子的指針域，所以空閑指針數(shù)： 2n - (n-1) = n+1 耙蔑，這么多指針域我們怎樣規(guī)劃能避免這些指針便宜null呢见妒？
大佬們提出了這樣一個用途，中序遍歷這棵樹我們可以得到： HDIBJEAFCG 甸陌，很輕松须揣。那么我們可以愉快的知道 I 是 B 的前驅盐股，或者 J 是 B 的后繼這樣的信息，那是借助了遍歷返敬，我們能不能把這些空的指針指向前驅和后繼呢遂庄，當然闊以寥院。
但是馬上有人站出來說劲赠，那指向孩子的指針原來就存在了，這后來的野生指針和指向孩子的指針可怎么區(qū)分呢秸谢，大佬們就決定再加個量來區(qū)分指針的類型凛澎，如果是指向孩子的就用 0 表示，用作前驅后繼的就用 1 表示估蹄，使用的時候進行遍歷就可以一勞永逸地取得前驅后繼的信息塑煎，OK，看看結構的定義變成啥樣了臭蚁。
和原來差不多對不對最铁，多了個枚舉變量的定義
OK，現(xiàn)在我們的線索二叉樹可以算正式出爐遼：
我們把指向前驅和后繼的指針稱為線索垮兑，加上線索的二叉鏈表稱為線索鏈表冷尉，相應的二叉樹就稱為線索二叉樹 (Threaded Binary Tree)
來看一看抽象化結點的結構：ltag = 0 或者 Link，表示這個結點的左指針指向左孩子系枪，ltag = 1 或者?Thread雀哨，表示這個結點的左指針指向前驅
rtag = 0 或者 Link，表示這個結點的右指針指向右孩子私爷，rtag = 1 或者?Thread雾棺，表示這個結點的右指針指向后繼
結點的新式定義
改頭換面的二叉鏈表
中序線索化遍歷的實現(xiàn)
我們來讀一下代碼，樸素的中序遍歷的框架其實還在衬浑，中間加粗的是線索化的代碼捌浩，另外多了 pre 的指針，我們可以發(fā)現(xiàn)這個指針永遠比我們的主角指針 p 慢一拍工秩，它永遠在 p 的前驅結點嘉栓，每次到了一個結點，我們先判斷一哈這個結點有沒有左子樹拓诸，如果沒有侵佃，就使這個節(jié)點的標記值置Thread，表示這個結點被前驅大爺承包了奠支，然后就是讓指針 p 的左孩子管 pre 叫干爹馋辈， 表示這個結點的前驅就定下了；然后是后繼倍谜，我們會發(fā)現(xiàn)這個和前驅有點不同迈螟，這個先看前驅結點的右孩子是否為空叉抡，即 如果 pre -> rchild 為空，就把這個引到 p 指針答毫，我們說 p 指針走的快一步褥民，所以這就找到了后繼，順理成章? pre->rtag = Thread洗搂，pre -> rchild = p; 完美消返！ 這兩步表示一輪線索化的一個輪回，弄完這些讓 pre 再向前走一步耘拇，就是 pre = p撵颊，剩下的和中序遍歷沒什么區(qū)別
我們給這個二叉鏈表加上一個頭指針，并且讓頭結點的左孩子指向樹根節(jié)點惫叛，讓中序的第一個節(jié)點指回頭結點的左孩子指針倡勇，用頭結點的右指針指向中序遍歷的最后一個結點，并且把這個指針指回頭結點的右指針嘉涌，形成雙向的指針循環(huán)妻熊，這樣的好處就在于既可以從第一個結點開始沿中序的后繼向后遍歷，也可以利用從頭開始前序遍歷（例子及表述來自《大話數(shù)據(jù)結構》）
附上帶頭結點的線索二叉樹中序遍歷：
首先定義指向根的頭結點 p仑最，我們先看外層這個最大的循環(huán)扔役，這個循環(huán)條件為 p != T ，這個條件首先排除了空樹的遍歷词身，其次按照剛才對帶頭節(jié)點二叉線索表的分析厅目，最后的 p 指針會在窮途末路時等于 T ，這相當于 p 指向頭結點法严，這時 p = T 损敷，故如果不加 p != T ，則會無限循環(huán)下去深啤。進入循環(huán)拗馒，首先是判定p -> ltag 等于Link，內容是指向左子樹溯街，那么這一個循環(huán)表示從根開始直到沒有左子樹的末端诱桂，路徑是A →B→D→H，然后打印H呈昔，目前 p 的右指針是指向直接后繼D的挥等，所以下面一個進入第二個while，打印出D堤尾，D的右邊是孩子指針肝劲，第十五行指向I，然后重復整個過程，相當于從小樹到大樹以鏈表搜索的形勢進行完整的中序遍歷辞槐，完整順序參照下圖
好的掷漱，我們今天的線索二叉樹就到這里遼，最后附上一段我偷來的話：
在實際問題中 榄檬，如果所用的二叉樹需經常遍歷或查找結點時需要某種遍歷序列中的前驅和后繼卜范，那么采用線索二叉鏈表的存儲結構就是非常不錯的選擇。
