前言

本章節要談的是引線二元樹，在談引線二元樹，最一開始就要講到為甚麼我們需要引線二元樹、發展的緣由、規則，還有他帶來甚麼好處、還有各種操作，進入本章節之前，建議先參考 30 天系列 (03) 之 Tree 的表示方法，裡面有提到 Linkedlist 建置時會造成浪費連結空間的問題，請看以下

設要使用的 Tree's Degree = 2，且具有 n 個 node
代表可用連結僅只有 n-1 條
那總共會浪費 2*n-(n-1) = n+1 條連結

緣由與規則

緣由

之所以有引線二元樹，就是因為使用鏈結串起此樹的時候必會造成連結的浪費，而引線二元樹的出現，就是為了有效利用這些連結

規則

1. 如果原本 node’s lchild is nil，就把他 link 到中序的前一個點
2. 如果原本 node’s rchild is nil，就把他 link 到中序的後一個點

資料結構的設計

1. nodes 新增了兩個欄位分別是 lthread, rthread (boolean)，因此會呈現 lthread llink data rlink rthread 的結構，若 lthread 為 True 就代表該點沒有左子點，因此他為引線，必須在 Llink 放入其中去前繼者
2. 此外，另外新增了一個新的 Node，完全不存東西，稱其為 head，
   • 當為空樹時，head node's lthread = True, rthread = False，所有 Link 指向自己
   • 若不為空樹，head node's lthread = False, rthread = Fale，lchild 指向 root，rchild 指向自己