---
title: 'Thread Binary Tree'
disqus: hackmd
---
[TOC]

# Threaded Binary Tree - 引線二元樹
* 根據 [Binary Tree - Linked List](https://hackmd.io/jALze7TIS6a9A_LYNoVidA#Linked-List) 有 $n+1$ 條 Link 未使用
而在該缺點提到的：對於Leaf Link 的作法，**引線二元樹** 就是其中一個

* 我們將利用這 $n+1$ 條 Link 指向同一棵樹裡的其它 Node
* 規則將依照 [Binary Tree Traversal](https://hackmd.io/jALze7TIS6a9A_LYNoVidA#Binary-Tree-Traversal) 的 **Inorder (中序)** 性質來規定

:::success

* **Def**
<br>
1. 若某 Node 的 Left Child 為 Null
則我們將 **"假裝"** 它是一條左邊的 Thread ，假設這個 Node 為 C
它會指向這顆 Binary Tree 以 Inorder Expression 裡 C 的前一個資料所在的 Node

2. 這棵樹的 Inorder Expression 為：**ABCDEFGHI**
Node C 的 Left Thread (Left Link) 就會指向 B Node：

**... A`B`<-`C`DEFGHI ...**

3. 同理，若 Right Child 為 Null，則指向 Inorder Expression 下一個資料所在的 Node
也就是 D Node：

**... AB`C`->`D`EFGHI ...**
:::

---

# Representation in Data Structure
* 在 Data Structure 中我們可以將一個 Node 想像如下

* 在定義中提到 **"假裝"** 它是一個 Thread 原因是實際上它還是 Link
避免因為稱作 Thread 而與其他類似的東西搞混
* 既然實際上還是一條 Link 我們當然需要某些方法來分辨它到底是指向兒子的 Link
還是指向 Null 而變成 Thread 的 Link
* 所以我們使用 Boolean 作為判斷該條件的參數，若它是 Thread 則 `Ture` 反之 `False`

根據上述的規則我們建立了一顆 Thread Binay Tree
圖中實線為 Link ， 虛線則為 Thread
綠色 Thread 代表有 Node 可以指向，那紅色 Thread 呢？
* 沒錯，紅色 Thread 沒有 Node 可以指向
**Inorder Expression：42135** 中 Node 4 , 5 也就是 Expression 的頭尾並不存在左右 Node 可以讓 Thread 指向
* 因此我們需要一個類似於 Linked List 中的 Head Node 來當這輛火車的領頭羊

---

## Dummy Node - 虛擬節點
* 我們特定使用一個 Node 稱作 Dummy Node，做為這隻領頭羊
* 有別於 Linked List 裡的 Head Pointer ， Head 有可能會因為被 Release() 而為 Null
* 只要 Threaded Binary Tree 被建立，Dummy Node 將始終存在於程式當中，直到程式結束
* 我們可以看到 Dummy Node 有幾個特點

1. 沒有存放 Data
2. Right Thread 永遠都是 False，代表他的 Right Link 永遠會指向某個 Node
3. 那個 Node 就是 Dummy Node 本身
4. 新增第一個 Node 時將放在 Dummy Node 的 Left Child

* 插入第一個 Node 5 後

* **Dummy Node**
1. `Left Child = Node 5` 左兒子指向 Node 5
2. `Left Thread = false` 左 Link 不是 Thread

* **Node 5**
1. `Left Child = Dummy Node` 左兒子指向 Dummy Node
2. `Left Thread = true` 左 Link 是 Thread
3. `Right Child = Dummy Node` 右兒子指向 Dummy Node
2. `Right Thread = true` 右 Link 是 Thread


---

#### **Threaded Binary Tree Insertion**

* 承續上面的狀態，我們將依照 **BST** 的規則來做 Insertion
* 這裡只解釋 Threaded Binary Tree 的獨特性質

1. 插入 Node 1，以藍色表示 新的 及 更動的 Link
* **Node 5**

* ```Left Child = Node 1``` 左兒子指向 Node 1
* ```Left Thread = false``` 左 Link 不是 Thread
* **Node 1**
* ```Right Child = Node 5``` 右兒子指向 Node 5
* ```Right Thread = true``` 右 Link 是 Thread
* ```Left Child = Dummy Node``` 左兒子指向 Dummy Node
* ```Left Thread = true``` 左 Link 是 Thread


1. 插入 Node 8
* **Node 5**

* ```Right Child = Node 8``` 右兒子指向 Node 8
* ```Right Thread = false``` 右 Link 不是 Thread
* **Node 8**
* ```Right Child = Dummy Node``` 右兒子指向 Dummy Node
* ```Right Thread = true``` 右 Link 是 Thread
* ```Left Child = Node 5``` 左兒子指向 Node 5
* ```Left Thread = true``` 左 Link 是 Thread


---

# Thread 的作用

* 講了這麼多， Thread 到底要怎麼使用，跟 Binary Traversal 又有甚麼關係
* 回想當初提到的

:::success
2. 這棵樹的 Inorder Expression 為：**ABCDEFGHI**
Node C 的 Left Thread (Left Link) 就會指向 B Node：

**... A`B`<-`C`DEFGHI ...**

3. 同理，若 Right Child 為 Null，則指向 Inorder Expression 下一個資料所在的 Node
也就是 D

**... AB`C`->`D`EFGHI ...**
:::

:::warning

Right Link 會指向 Inorder Expression 裡面的後一個 Node

那麼如果我已經知道 **A** 的位置，也就是 Inorder Expression 第一個 Node

就可以不停的從 **A** 開始使用 **Right Link** ：**`A`->`B`->`C`->`D`->`E`->`F`->`G`->`H`->`I`**

，求出整棵樹的 Inorder Expression ， Left Link 也同理
:::

* 我們藉由圖案來理解一次，第一個點為：**`A`**

沿著右邊 Link 之依序為 **`A`->`B`->`D`->`E`->`F`->`G`->`I`**
<br>
？？？？？？？？
> [color=#476b00]如果你毫無疑問地看下來，我會很難過
知道原因的以下敘述可以略過

<br>

* 到這裡你可能還沒弄清楚 Threaded Binary Tree 的定義，回想一下我們的初衷
:::info
3. 同理，若 Right Child 為 **Null**，則指向 Inorder Expression 下一個資料所在的 Node
也就是 D Node：

**... AB`C`->`D`EFGHI ...** ...
:::

:::danger
我們所謂的 **"指向下一個資料"** 是建立在原本是指向 **Null** 的那些 Link
:::


* 綠色圈圈的 Link 通通不是原本指向 Null 的 Link，代表他們的 `Right Thread == false`
這是本章節最重要的一點，也是 Threaded Binary Tree 的特色

* 由此可知，我們在使用 Thread 的時候必定是需要一些條件才能夠順暢的求出 Inorder Expression，接下來就讓我們來探討這箇中精華 - **Predecessor & Successor**

---

## Predecessor

presucc(tree)
Input : Threaded Pointer
Output : inorder predecessor of a node

Begin
    Define Threaded Pointer : tmp;
    if(!tree->lThread)       //如果左 link 不是引線
        tmp = tree->lChild;  //指向左兒子
        while(!tmp->rThread) //將左兒子往右找，直到他的右 link 是引線 
            tmp = tmp->rChild;
    return temp;
END

---

## Successor

insucc(tree)
Input : Threaded Pointer
Output : inorder successor of a node

Begin
    Define Threaded Pointer : tmp;
    if(!tree->rThread)       //如果右 link 不是引線
        tmp = tree->rChild;  //指向右兒子
        while(!tmp->lThread) //將右兒子往左找，直到他的左 link 是引線
            tmp = tmp->lChild;
    return temp;
END

---

## 中序走訪 - Iterative

* 這部分很容易，仔細回想 Inorder Traversal 的順序關係
第一步位置是樹中的 Leftmost Node

digraph graphname{
    1[label="1" color=red]
   2->1
   2->3
}

* 起點：紅色三角形為最大的一棵樹

* Root：F
* Left Child：橘色三角形，它的 Root 為 B
* Right Child：淺藍三角形，它的 Root 為 G
* 以下程式步驟將根據此圖，Thread 請自行想像

* **第一式 - 千里尋左子**
處理 F 的 Leftmost Child：橘色三角形
1. ```
while( CurrentNode->LeftThread!=true ){ //當前節點的 LeftLink 不是 Thread
CurrentNode = CurrentNode->LeftLink; //往左 Link 移動
}
printf("%c",CurrentNode->Data); //找到該樹第一個 Node

這樣一來我們便可以找到 Inorder Expression 第一個：`A`
<br>
* **第二式 - 穿針引右線(上冊)**
再來我們只要檢查這個 Node 的 Right Link 是不是 Thread
如果是，我們就可以透過 Thread 找到第二個資料

digraph graphname{
    2[label="2" color=red]
   2->A
   2->3
}

2. ```
if( CurrentNode->RightThread == true ){ //右 Link 是 Thread
CurrentNode = Current->RightLink; //移動到右 Link 指的 Node
printf("Current->Data");
}
恭喜透過 Thread 找到了第二個資料：`B`

digraph graphname{
    2[label="B" color=red]
   2->A
   2->3
}

接著我們繼續使用 **穿針引右線** 看看能不能運氣好又找到 Thread

digraph graphname{
    1[label="A"]
    2[label="B"]
    3[label="3-2" color=green]
    4[label="3-1" color=green]
    5[label="3-3" color=green]
    
    2->1[]
    2->3
    3->4
    3->5
   
}

我們發現了一顆野生的新樹：綠色三角形
這也表示 **穿針引右線** 失敗了，我們將 **當前節點** 往野生的新樹移動
* **穿針引右線(上、中冊)**

    if( CurrentNode->RightThread == true ){ //右 Link 是 Thread
        CurrentNode = Current->RightLink; //移動到右 Link 指的 Node
        printf("Current->Data");
    }
    else{
        Current = Current->RightChild //往野生的新樹移動
    }

* 發現野生的新樹就是要用 **千里尋左子**，我們將兩招搭配起來

    if( CurrentNode->RightThread == true ){ //右 Link 是 Thread
        CurrentNode = Current->RightLink; //移動到右 Link 指的 Node
        printf("CurrentNode->Data");
    } 
    else{
        CurrentNode = Current->RightChild; //往野生的新樹移動
        千里尋左子(CurrentNode);
    }

digraph graphname{
    1[label="A"]
    2[label="B"]
    3[label="3-2" ]
    4[label="C" color=red]
    5[label="3-3" ]
    
    2->1[]
    2->3
    3->4
    3->5
   
}

* **穿針引右線**

digraph graphname{
    1[label="A"]
    2[label="B"]
    3[label="D" color=red]
    4[label="C"]
    5[label="3-3" ]
    
    2->1[]
    2->3
    3->4
    3->5
   
}

* **穿針引右線**

digraph graphname{
    1[label="A"]
    2[label="B"]
    3[label="D" ]
    4[label="C"]
    5[label="4-2" color=green]
    6[label="4-1" color=green]
    7[label="4-3" color=green]
    
    2->1[]
    2->3
    3->4
    3->5
    5->6
    5->7
   
}

* **千里尋左子**

digraph graphname{
    1[label="A"]
    2[label="B"]
    3[label="D" ]
    4[label="C"]
    5[label="4-2"]
    6[label="Null" style=dashed color=red]
    7[label="4-3" ]
    
    2->1[]
    2->3
    3->4
    3->5
    5->6
    5->7
   
}

* **穿針引右線**

digraph graphname{
    1[label="A"]
    2[label="B"]
    3[label="D" ]
    4[label="C"]
    5[label="E"  color=red]
    6[label="Null" style=dashed]
    7[label="4-3" ]
    
    2->1[]
    2->3
    3->4
    3->5
    5->6
    5->7
   
}

* **穿針引右線**
這一步可能需要稍微思考一下，第一步我們直接從橘色三角形開始
但其實要從紅色三角形開始**千里尋左子**，
所以這步相當於紅色三角形 **千里尋左子** 結束(左子樹已經拜訪完了)
再 **穿針引右線** E->F

digraph graphname{
    1[label="A"]
    2[label="B"]
    3[label="D" ]
    4[label="C"]
    5[label="E"]
    7[label="F (4-3)" color=red]
    8[label="5"]
    
    2->1[]
    2->3
    3->4
    3->5
    7->2
    7->8
   
}

* **穿針引右線**

digraph graphname{
    1[label="A"]
    2[label="B"]
    3[label="D" ]
    4[label="C"]
    5[label="E"]
    7[label="F"]
    8[label="5-2" color=green]
    11[label="5-1" color=green]
    12[label="5-3" color=green]
    

    2->1[]
    2->3
    3->4
    3->5
    7->2
    7->8
    8->11
    8->12
   
}

* **千里尋左子**

digraph graphname{
    1[label="A"]
    2[label="B"]
    3[label="D" ]
    4[label="C"]
    5[label="E"]
    7[label="F"]
    8[label="5-2"]
    11[label="Null" style=dashed color=red]
    12[label="5-3"]
    

    2->1[]
    2->3
    3->4
    3->5
    7->2
    7->8
    8->11
    8->12
   
}

* **穿針引右線**

digraph graphname{
    1[label="A"]
    2[label="B"]
    3[label="D" ]
    4[label="C"]
    5[label="E"]
    7[label="F"]
    8[label="G" color=red]
    11[label="Null" style=dashed]
    12[label="5-3"]
    
    2->1[]
    2->3
    3->4
    3->5
    7->2
    7->8
    8->11
    8->12
}

* **穿針引右線**

digraph graphname{
    1[label="A"]
    2[label="B"]
    3[label="D" ]
    4[label="C"]
    5[label="E"]
    7[label="F"]
    8[label="G"]
    12[label="6-2" color=green]
    13[label="6-1"  color=green]
    14[label="6-3"  color=green]
    

    2->1[]
    2->3
    3->4
    3->5
    7->2
    7->8
    8->12
    12->13
    12->14
   
}

* **千里尋左子**

digraph graphname{
    1[label="A"]
    2[label="B"]
    3[label="D" ]
    4[label="C"]
    5[label="E"]
    7[label="F"]
    8[label="G"]
    12[label="6-2"]
    13[label="H"  color=red]
    14[label="6-3"]
    

    2->1[]
    2->3
    3->4
    3->5
    7->2
    7->8
    8->12
    12->13
    12->14
   
}

* **穿針引右線**

digraph graphname{
    1[label="A"]
    2[label="B"]
    3[label="D" ]
    4[label="C"]
    5[label="E"]
    7[label="F"]
    8[label="G"]
    12[label="I"   color=red ]
    13[label="H"]
    14[label="6-3"]
    

    2->1[]
    2->3
    3->4
    3->5
    7->2
    7->8
    8->12
    12->13
    12->14
   
}

* **穿針引右線** (恭喜你，已經找不到野生的新樹了)

digraph graphname{
    1[label="A"]
    2[label="B"]
    3[label="D" ]
    4[label="C"]
    5[label="E"]
    7[label="F"]
    8[label="G"]
    12[label="I"]
    13[label="H"]
    14[label="Null" color=red style=dashed]
    

    2->1[]
    2->3
    3->4
    3->5
    7->2
    7->8
    8->12
    12->13
    12->14
   
}

* 請別以為就這樣結束了，讓我們來回憶一下

:::success
Inorder Expression：42135 中 Node 4 , 5 也就是 Expression 的頭尾並不存在左右 Node 可以讓 Thread 指向
:::

想起我們的領頭羊了嗎，結束的條件是回到 **Dummy Node** ！

digraph graphname{
    1[label="A"]
    2[label="B"]
    3[label="D" ]
    4[label="C"]
    5[label="E"]
    7[label="F"]
    8[label="G"]
    12[label="I"]
    13[label="H"]
    14[label="Dummy Node" color=red]
    

    2->1[]
    2->3
    3->4
    3->5
    7->2
    7->8
    8->12
    12->13
    12->14[ style=dashed]
   
}

* **穿針引右線(全冊)**

    if( CurrentNode->RightThread == true &&
        CurrentNode->RightLink != DummyNode){ //右Link是Thread 且不是DummyNode
        
        CurrentNode = Current->RightLink; //移動到右Link指的Node
        printf("CurrentNode->Data");
    }
    
    if( CurrentNode->RightThread == false &&
        CurrentNode->RightLink != DummyNode){
        
        CurrentNode = Current->RightChild; //往野生的新樹移動
        CurrentNode = 千里尋左子(CurrentNode);
    }
    
    else{
        printf("程式結束！");
    }

:::warning
**Time Complexity：**
:::

> [time=Wed, May 8, 2019 6:20 PM]

---

# 待補充
### 引線由來 畫線
inorder 插入
1.找到該樹的最右子點 即是 中旭表達最後一個
2.插入在該點的右邊

### 使用引線樹的原因 搭配插入的方式 (有待商討)
引線樹：對樹裡面 DATA 前中後序輸出會很快
插入的方法：
1. 大放右，小放左：跟前中後續完全無關
2. 根據predecessor successor來放：跟前中後續相關
* Pre-Order
* Post-Order
* In-Order
* Level-Order
### 遺漏
* 講解程式如何處理引線接到何處
* 寫完 Traversal 再來修改此篇針對 Traversal 不必要的描述，再新增 preorder、postorder 的方法

###### tags: `Data Structure`