Threaded Binary Tree實作是我想寫Binary Tree的原因，因為這個題目有夠坑，書中的說明少了一個步驟，聖經本(基礎資料結構使用c++)更是形而上，看youtube也是直接跳步驟的一堆。
看完真心累。
Threaded Binary Tree中文譯為引線二元樹。
一般二元樹的走訪最常見的就是利用遞迴來走訪。如果能用像是linked list的走訪感覺對節點的操作就會更直覺一點，引線二元樹就是想做到這樣的效果。這裡說是像，但還是會有點不同。
名詞介紹:
Successor: 後繼者 — -讓每個Node能連結到下一個節點
Predecessor:前驅者 — -讓每個Node能連結到上一個節點
下圖為一個二元樹例，其中序走訪的順序為HDIBJEAFCG
例如H、I、J右子樹都是空的，可以加以利用，原本H的右子樹指向Null，現在把它們的右子樹連結到下一個Node去，這樣Tree就可以一個接一個的走訪，如下圖。
將樹進行Successor化，讓樹的節點能找到後繼者是誰，紅色的這些線就稱為thread。
這裡也是名詞定義下。若Node是有實際的左或右子樹，則此pointer稱為link(例如B指向D的pointer)，若是將左或右子樹指向後繼者，則此pointer稱為thread(例如J指向E的pointer)。
當初初讀時，以為真的可以向linked list這樣，從H開始一路next->next->next->…….一直指到G。
BUT!!!這棵樹的中序走訪是HDIBJEAFCG，B的下一個後繼者應該是J啊，但實際上再看看圖就會發現，B明明下一個就是指向E。
也就是說這個Threaded Binary Tree，是讓你有方法比較快找到下個後繼者，而不是讓你變成真正的linked list走訪。
例如，B如果要找到後繼者，他會發現自己的右子樹是連結到真正的結點E，所以他的右子樹pointer不能利用來指向中序走訪的後進者，也就是J，必需要繞一下路才能找到J，之後再說明。
因此，在Threaded Binary Tree的資料結果除了二元樹的基本資料結構(data、lchild、rchild)，還多加了LTag和RTag，這個變數是用來記錄，左子樹/右子樹所連結的是link還是thread。
以上講的是Successor，後繼者。但如同雙向鏈結一樣，我可以從頭走到尾，也可以從尾走到頭，Predecessor:前驅者。是同樣的概念。
以下為Threaded Binary Tree的資料結構
這裡小結一下，Threaded Binary Tree包含了兩個步驟:
- 連結引線
- 走訪
這兩個要分開來看。
本篇就先介紹到這