線索二叉樹：原理、構建與中序遍歷完整C語言實現

動機：利用空指針域

含n個節點的二叉鏈表有n+1個空指針。線索二叉樹將這些空指針改指向遍歷序列下的前驅/後繼節點，稱為「線索」。支持O(1)查找前驅後繼，無需遞歸/棟。

節點結構擴展

typedef enum { Link, Thread } childTag;
typedef struct ThreadBiTree {
    char data;
    struct ThreadBiTree *lchild, *rchild;
    int ltag, rtag; // 0=Link(孩子), 1=Thread(線索)
} ThreadBiTree, *PtrThreadBiTree;

中序線索化遞歸算法

中序遍歷時維護pre指向上一訪問節點：

void InOrderThreading(PtrThreadBiTree *pre, PtrThreadBiTree root) {
    if (!root) return;
    InOrderThreading(pre, root->lchild);
    if (!root->lchild) {           // 無左孩子 → 前驅線索
        root->lchild = *pre;
        root->ltag = Thread;
    }
    if (!(*pre)->rchild) {         // pre無右孩子 → 後繼線索
        (*pre)->rchild = root;
        (*pre)->rtag = Thread;
    }
    *pre = root;
    InOrderThreading(pre, root->rchild);
}

引入頭節點形成閉環

void InThread(PtrThreadBiTree *head, PtrThreadBiTree root) {
    *head = malloc(sizeof(ThreadBiTree));
    (*head)->ltag = Link; (*head)->rtag = Thread;
    (*head)->rchild = *head; // 右線索自指
    if (!root) { (*head)->lchild = *head; return; }
    (*head)->lchild = root;
    PtrThreadBiTree pre = *head;
    InOrderThreading(&pre, root);
    (*head)->rchild = pre;       // 頭節點右指向最後節點
    pre->rtag = Thread;
    pre->rchild = *head;         // 最後節點右指向頭節點
}

中序遍歷線索樹（非遞歸）

void MidOrderTraverse(PtrThreadBiTree head) {
    PtrThreadBiTree p = head->lchild;
    while (p != head) {
        while (p->ltag == Link) p = p->lchild; // 找最左
        printf("%c ", p->data);                // 訪問
        while (p->rtag == Thread && p->rchild != head) {
            p = p->rchild;                     // 沿後繼線索
            printf("%c ", p->data);
        }
        p = p->rchild; // 跳到右子樹根或頭節點
    }
}

測試用例

輸入字符串"ab#d##ce###"構建樹（#表空），中序輸出：d b a e c。運行結果驗證正確。

優缺點總結