Day 15 用遞迴寫出了前序、中序、後序三種走訪，程式很短也很直觀。但遞迴看起來簡單，背後其實是程式偷偷幫我們記住「走完左子樹之後要回到哪一個節點」：每往下走一層，就多一個還沒結束的函式呼叫，這些呼叫會一層層疊在記憶體裡一個叫**呼叫堆疊（call stack）**的地方，樹越高疊得越多。

另一方面，用鏈結建立二元樹時，葉節點的 left、right 全都是 NULL，只有一個子節點的節點也會空出一個欄位。這些欄位占著記憶體，卻只能表示「這裡沒有子節點」。既然空著，能不能拿它們來「指路」，讓走訪時直接知道下一個節點在哪裡，不必再靠遞迴記住回去的路？這就是今天的主角：引線二元樹（threaded binary tree）。

二元樹裡有多少空指標

沿用 Day 15 的範例樹，每個節點有 left、data、right 三個欄位：

可以看到圖上這棵樹有 6 個節點，每個節點有 2 個指標欄位，共 12 個。真正用到的有幾個？除了根節點 A 以外，每個節點都恰好被父節點指到一次，所以只用到 6 − 1 = 5 個，剩下 7 個是 NULL。

推廣到一般情況：設 n 是節點數，

• 指標欄位共有 2n 個。
• 除了根節點，每個節點都被指到一次，所以用到 n − 1 個。
• 空著的 NULL 有 2n − (n − 1) = n + 1 個。

也就是說，不論樹長什麼樣子，空指標都比節點數還多一個，超過全部指標欄位的一半。

引線：讓空指標指向走訪的前後節點

引線二元樹的做法，是把這些原本是 NULL 的欄位改成指向「走訪順序中的前後節點」，這種指標稱為引線（thread）。走訪順序可以選前序、中序或後序。

以最常用的中序引線為例：

• left 原本是 NULL：改成指向這個節點的中序前驅（inorder predecessor），也就是中序走訪中排在它前一個的節點。
• right 原本是 NULL：改成指向這個節點的中序後繼（inorder successor），也就是中序走訪中排在它後一個的節點。

範例樹的中序走訪是 D B E A C F，所以：

原本的 7 個 NULL 裡，有 5 個變成了引線；只剩中序第一個節點 D 的 left、最後一個節點 F 的 right，因為前後沒有節點可以指，暫時仍是 NULL。

怎麼分辨子節點和引線

改完之後出現一個新問題：B 的 right 指向 E，E 的 left 也指向 B，看起來都只是「一個指標」，程式要怎麼知道哪一個是真正的子節點、哪一個是引線？

答案是每個節點再多存兩個標記欄位，分別記錄 left、right 現在是子節點還是引線。用 C 的結構寫出來大概是這樣：

typedef struct ThreadNode {
    char data;
    struct ThreadNode *left;   // 左子節點，或中序前驅（引線）
    struct ThreadNode *right;  // 右子節點，或中序後繼（引線）
    bool leftThread;           // true：left 是引線；false：left 指向左子節點
    bool rightThread;          // true：right 是引線；false：right 指向右子節點
} ThreadNode;

這只是節點的宣告片段，使用 bool 需要引入 <stdbool.h>。標記也常寫成 0、1，哪個數字代表引線並沒有統一的規定，閱讀別人的程式時要先確認；這裡一律以「true 代表引線」為準。

頭節點：給第一個和最後一個節點一個去處

前面的表格還留下兩個空位：中序第一個節點 D 沒有前驅，最後一個節點 F 沒有後繼。如果它們仍然是 NULL，走訪程式就得另外處理這兩個特例。

解決方法是額外加一個不存資料的頭節點（head node），並這樣設定：

• 頭節點的 left 指向整棵樹的根節點 A（是子節點，leftThread 為 false）。
• 頭節點的 right 指向頭節點自己（rightThread 為 false）。
• 中序第一個節點 D 的 left 引線、最後一個節點 F 的 right 引線，都指向頭節點。
• 如果樹是空的，頭節點的 left 就是指向自己的引線（leftThread 為 true）。

這麼一來，樹裡已經沒有任何 NULL 了：原本 7 個空欄位，全部變成了引線。頭節點就像環狀串列的起點，走訪從它出發，最後也回到它。

走訪引線二元樹：找出下一個節點

中序走訪的核心問題是：站在目前的節點上，下一個要拜訪的節點是誰？ 有了引線之後，只要看目前節點的 right：

1. 如果 right 是引線，它直接指向目前節點的中序後繼，跟過去就好。
2. 如果 right 是子節點，代表目前節點有右子樹。依照中序「左、根、右」的規則，接下來要走訪右子樹，而右子樹中第一個被拜訪的，是它最左邊的節點。所以先往右走一步，再沿著 left 一路往左，直到某個節點的 left 是引線為止。

整個走訪從頭節點開始，反覆找下一個節點，回到頭節點時就結束。用範例樹追蹤一次：

拜訪順序是 D B E A C F，和遞迴的中序走訪結果相同。注意第一列：頭節點的 right 指向自己，所以「往右一步再一路往左」剛好會走到整棵樹最左邊的 D，第一個節點也能套用同一條規則，不必另外寫特例。

整個過程沒有遞迴、也沒有用堆疊，只靠一個指標在樹上移動。設 n 是節點數，每一條子節點指標或引線，在整次走訪中最多只會經過一次，所以時間複雜度是 O(n)；除了樹本身以外，只需要記住目前節點，額外空間是 O(1)。對照 Day 15 的遞迴走訪，時間同樣是 O(n)，額外空間卻要 O(h)（h 是樹高），樹傾斜時會到 O(n)。

同樣的道理，看節點的 left 也能找到中序前驅，因此引線二元樹還可以由後往前倒著走訪。一般二元樹當然也能倒著走訪，只是同樣得靠遞迴或堆疊記住回去的路。

小結

引線二元樹要解決的，是開頭提到的兩個問題。第一，遞迴走訪要靠呼叫堆疊記住「走完子樹後要回到哪裡」，額外空間是 O(h)，樹傾斜時會到 O(n)；第二，用鏈結建立的二元樹，n 個節點有 2n 個指標欄位，其中 n + 1 個是 NULL，占著空間卻只能表示「沒有子節點」。引線把這兩件事接在一起：把空的 left 改成指向中序前驅、空的 right 改成指向中序後繼，原本「回去的路」就直接寫在樹裡，不必再由堆疊記住。再搭配標記欄位分辨子節點和引線，以及讓第一個、最後一個節點有地方可指的頭節點，走訪時只要看目前節點的 right：是引線就跟過去，是子節點就往右一步再一路往左到底，回到頭節點就結束。這樣時間仍是 O(n)，額外空間卻降到 O(1)，而且從任何一個節點出發，都能找到它的中序前驅與後繼，不必從根重新走起。代價是每個節點要多存兩個標記，修改樹的時候也得把引線一起維護好。

今日重點：

• n 個節點的鏈結二元樹有 2n 個指標欄位，用到 n − 1 個，其餘 n + 1 個是 NULL。
• 中序引線把空的 left 改指向中序前驅、空的 right 改指向中序後繼。
• 每個節點用兩個標記欄位分辨 left、right 是子節點還是引線。
• 頭節點的 left 指向根、right 指向自己；中序第一個與最後一個節點的引線都指向頭節點。
• 引線二元樹每個節點多了標記欄位，並沒有比一般二元樹省記憶體；它省的是走訪時的堆疊空間。

下一篇會先看如何把林轉換成二元樹，再認識堆積（heap）：一種用完整二元樹表示、能快速取出最大或最小值的結構。