資料結構：線索二叉樹構建與遍歷算法

資料結構：線索二叉樹構建與遍歷算法

線索樹由來

二叉樹 n 節點有 2n 指標域，n-1 條連線 → n+1 個空指標域。利用空域儲存前驅/後繼資訊，避免遍歷時需堆疊。

• 左指標為空 → 指向中序前驅 (Ltag=1)
• 右指標為空 → 指向中序後繼 (Rtag=1)

線索二叉樹節點結構

typedef struct BiThrNode {
    ElemType data;
    struct BiThrNode *Lchild, *Rchild;
    int Ltag, Rtag;  // 0=指標, 1=線索
} BiThrNode, *BiThrTree;

中序線索樹尋找後繼規則

• 右標籤為線索 (Rtag=1) → 右鏈直接是後繼
• 右標籤為指標 (Rtag=0) → 後繼為右子樹中最左下節點 (沿左鏈至 Ltag=1)

後序線索樹尋找後繼 (三種情況)

1. 根節點 → 後繼為空
2. 為父節點左孩子且父無右子樹 → 後繼為父節點
3. 為父節點左孩子且父有右子樹 → 後繼為父右子樹後序首個節點

中序線索化遞歸算法

BiThrNode *pre; // 全域變數，指向剛訪問節點

void InThreading(BiThrNode *T) {
    if (T) {
        InThreading(T->Lchild);
        if (!T->Lchild) { T->Ltag = 1; T->Lchild = pre; } // 前驅線索
        if (!pre->Rchild) { pre->Rtag = 1; pre->Rchild = T; } // 後繼線索
        pre = T;
        InThreading(T->Rchild);
    }
}

Status InOrderThreading(BiThrTree *Thrdhead, BiThrTree T) {
    *Thrdhead = (BiThrTree)malloc(sizeof(BiThrNode));
    (*Thrdhead)->Ltag = 0; (*Thrdhead)->Rtag = 1; (*Thrdhead)->Rchild = NULL;
    if (!T) (*Thrdhead)->Lchild = *Thrdhead;
    else {
        (*Thrdhead)->Lchild = T;
        pre = *Thrdhead;
        InThreading(T);
        pre->Rchild = *Thrdhead; pre->Rtag = 1; // 最後節點線索化
        (*Thrdhead)->Rchild = pre;
    }
    return OK;
}

線索二叉樹非遞歸中序遍歷 (無堆疊)

Status InOrderTraverse_Thr(BiThrTree T) {
    BiThrTree p = T->Lchild; // 指向根
    while (p != T) {
        while (p->Ltag == 0) p = p->Lchild; // 找最左
        visit(p->data);
        while (p->Rtag == 1 && p->Rchild != T) {
            p = p->Rchild; visit(p->data); // 走線索訪問後繼
        }
        p = p->Rchild; // 轉右子樹
    }
    return OK;
}

先序建立線索二叉樹 (以 # 表空)

Status CreateBiThrTree(BiThrTree *T) {
    ElemType ch; scanf("%c", &ch);
    if (ch == '#') *T = NULL;
    else {
        *T = (BiThrTree)malloc(sizeof(BiThrNode));
        (*T)->data = ch;
        CreateBiThrTree(&(*T)->Lchild); if ((*T)->Lchild) (*T)->Ltag = 0;
        CreateBiThrTree(&(*T)->Rchild); if ((*T)->Rchild) (*T)->Rtag = 0;
    }
    return OK;
}