上一篇介紹了Threaded Binary Tree
本篇來說下鏈結和走訪
首先先說說Successor
請記住我們的例子都是中序走訪為例
觀察此圖，如果從Successor該連到哪個Node去思考問題，就會有點繞(我覺得啦)，反之，從Node該被哪個Successor所連結，似乎就比較好想(同樣也是我覺得)。
規則: 遞迴找到左子樹的最右子樹ex: A被E所連結是因為:E就是A的左子樹B的最右子樹
D被H所連結是因為: 由於H已經沒有右子樹了，那就是H
這樣的想法比較容易代入遞迴，只要我拿到一個Node，我讓他返回左子樹的最右子樹。
繼續上面的遞迴後，有些Node的右子樹引線就鏈結好了
接下來走訪就稍微輕鬆點
走訪的規則算簡單易懂，由於我們都有後繼者鏈結了，那我們先找到第1個，也就是head，然後再往右找next。前一篇文提到，這無法像linked list單純一直next下去，需要根據PointerTag做調整，請看以下的規則
規則1:先找到head，其實很簡單，就是一個tree的最左子樹
規則2:若右子樹標記(PointerTag)是thread，則Successor直接鏈結到右子樹
規則3:若右子樹標記是link，則Successor為右子樹的最左子樹從圖中來看:
- 找到head，就是H
- H的右子樹是thread，因此右子樹即為Successor，來到D
- D的右子樹是link，因此找到D右子樹的最左子樹，I
- I的右子樹是thread，因此右子樹即為Successor，來到B
- B的右子樹是link，因此找到B右子樹的最左子樹，J
......依次找到右子樹為NULL，即走訪完畢。
完整範例程式碼就放在這裡，先不展開了。
https://gist.github.com/honoyang/df912fc0bcb2589e87ce7e18ff1ef52b再來是Predecessor
直接進入連結規則:
規則:遞迴找到右子樹的最左子樹yes!!!就是剛好和Successor相反
走訪的規則:
規則1:先找到head，其實很簡單，就是一個tree的最右子樹
規則2:若左子樹標記(PointerTag)是thread，則Predecessor直接鏈結到左子樹
規則3:若左子樹標記是link，則Predecessor為左子樹的最右子樹完整可執行範例如下，就不展開了
https://gist.github.com/honoyang/330f3e4d252e5d7af18b0cfc6a96e6c9欸都......以上的Successor和Predecessor
無法合併起來，讓Successor引線化後再Predecessor引線化...
因為Successor引線化後，就改變了右子樹的pointer的內容(從null變成node)，因此就不符合Predecessor的程式規則了
所以要合併兩個code的話就要做些手腳，例如利用PointerTag之類
但我懶得做了
決定下個章節寫直接一次做成雙向鏈節的方法
最後感嘆一下，遞迴真的很燒腦啊