線索二叉樹 C 語言完整實現：中序線索化、非遞歸遍歷、前驅後繼查找

編輯：關於C語言

為什麼需要線索二叉樹？

普通二叉鏈表中空指針佔比極高（n 個節點有 n+1 個空指針）。線索二叉樹利用這些空指針存儲中序遍歷的前驅/後繼，實現無棧非遞歸遍歷與O(1) 前驅後繼查找。

節點結構定義

typedef enum { Link, Thread } PointerTag;  // Link=孩子指針, Thread=線索指針

typedef struct ThrBiTrNode {
    char data;
    struct ThrBiTrNode *lchild, *rchild;
    PointerTag lTag, rTag;   // 標記左右指針性質
} ThrBiTrNode, *ThrBiTree;

核心算法流程

1. 先序建樹（教學用）

Status ThreadBinaryTree_PreOrderInput(ThrBiTree *T) {
    char c; scanf("%c", &c);
    if (c == ' ') *T = NULL;
    else {
        *T = (ThrBiTrNode *)malloc(sizeof(ThrBiTrNode));
        (*T)->data = c;
        (*T)->lTag = (*T)->rTag = Link;
        ThreadBinaryTree_PreOrderInput(&(*T)->lchild);
        ThreadBinaryTree_PreOrderInput(&(*T)->rchild);
    }
    return OK;
}

2. 中序線索化核心遞歸 `InOrderThread`

ThrBiTree Pre;  // 全局變量，指向「剛訪問過的節點」

Status InOrderThread(ThrBiTree T) {
    if (T) {
        InOrderThread(T->lchild);           // 1. 線索化左子樹

        if (T->lchild == NULL) {            // 2. 處理當前節點前驅
            T->lTag = Thread;
            T->lchild = Pre;
        }
        if (Pre->rchild == NULL) {          // 處理前驅節點後繼
            Pre->rTag = Thread;
            Pre->rchild = T;
        }
        Pre = T;                            // 更新 Pre

        InOrderThread(T->rchild);           // 3. 線索化右子樹
    }
    return OK;
}

3. 建立頭節點並啟動線索化

Status CreateInOrderThreadBinaryTree(ThrBiTree T, ThrBiTree *head) {
    *head = (ThrBiTrNode *)malloc(sizeof(ThrBiTrNode));
    (*head)->lTag = Link;  (*head)->rTag = Thread;
    (*head)->rchild = *head;                // 右線索指向自己

    if (!T) (*head)->lchild = *head;        // 空樹
    else {
        (*head)->lchild = T;
        Pre = *head;
        InOrderThread(T);                   // 核心線索化
        Pre->rTag = Thread;                 // 處理最後一個節點
        Pre->rchild = *head;
    }
    return OK;
}

4. 非遞歸中序遍歷（無棧！）

Status InOrderTraverse_NoRecursion(ThrBiTree T, ThrBiTree head) {
    while (T != head) {
        while (T->lTag == Link) T = T->lchild;  // 走到最左
        visit(T->data);
        while (T->rTag == Thread && T->rchild != head) {
            T = T->rchild;                       // 沿後繼線索走
            visit(T->data);
        }
        T = T->rchild;                           // 轉向右子樹
    }
    return OK;
}

5. 通用前驅/後繼查找 API

// 中序第一個節點
ThrBiTrNode *SeekFirstNode_InOrderThrBiTree(ThrBiTree T) {
    if (T) while (T->lTag == Link) T = T->lchild;
    return T;
}

// 任意節點的中序後繼
ThrBiTrNode *GetNextNode(ThrBiTrNode *p) {
    if (p->rTag == Link) return SeekFirstNode_InOrderThrBiTree(p->rchild);
    return p->rchild;  // 直接是後繼線索
}

// 基於上述兩函數的遍歷
Status InOrderTraverse_NoRecursion_Method(ThrBiTree T, ThrBiTree head) {
    for (T = SeekFirstNode_InOrderThrBiTree(T); T != head; T = GetNextNode(T))
        visit(T->data);
    return OK;
}

測試主程序與輸出

int main() {
    ThrBiTree T, Head;
    InitThreadBinaryTree(&T);
    printf("先序輸入 (空格代表空)：\n");
    ThreadBinaryTree_PreOrderInput(&T);  // 例：ABD  E  CF  G  (空格換行)

    printf("線索化前遞歸中序：\n"); InOrderTraverse(T); printf("\n");

    CreateInOrderThreadBinaryTree(T, &Head);
    printf("線索化後非遞歸中序：\n"); InOrderTraverse_NoRecursion(T, Head); printf("\n");

    // 驗證前驅後繼
    ThrBiTrNode *p = SeekFirstNode_InOrderThrBiTree(T);
    for (int i=0; i<7; i++) {
        printf("第%d個: %c\n", i+1, p->data);
        p = GetNextNode(p);
    }
    return 0;
}

關鍵圖解：線索化前後指針變化

原樹 (中序: D B E A F C G)
      A
    /   \
   B     C
  / \   / \
 D   E F   G

線索化後 (虛線為線索):
D -.-> B -.-> E -.-> A -.-> F -.-> C -.-> G
 ^    ^    ^    ^    ^    ^    ^    ^
 |    |    |    |    |    |    |    |
lTag=rTag=Thread, 指向前驅/後繼