C 語言實現線索二叉樹：非遞歸中序遍歷的高效結構

編輯：關於C語言

C 語言實現線索二叉樹：非遞歸中序遍歷的高效結構

線索二叉樹利用空指標域存儲前驅/後繼資訊，實現 O(1) 空間非遞歸中序遍歷。本文完整實現建樹、線索化、帶頭結點環狀結構、非遞歸遍歷。

資料結構定義

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

核心演算法

1. 前序建樹

void create_tree(BiTree *T, char **str) {
    char c; sscanf(*str, "%c", &c); (*str)++;
    if (c == ' ') { *T = NULL; return; }
    *T = malloc(sizeof(BiTNode));
    (*T)->data = c;
    (*T)->ltag = (*T)->rtag = Link;
    create_tree(&(*T)->lchild, str);
    create_tree(&(*T)->rchild, str);
}

2. 中序線索化

BiTree pre = NULL; // 全域前驅指標
void in_order_threading(BiTree T) {
    if (!T) return;
    in_order_threading(T->lchild);
    if (!T->lchild) { T->lchild = pre; T->ltag = Thread; }
    if (pre && !pre->rchild) { pre->rchild = T; pre->rtag = Thread; }
    pre = T;
    in_order_threading(T->rchild);
}

3. 加頭結點形成環

void in_thread(BiTree *P, BiTree T) {
    *P = malloc(sizeof(BiTNode));
    (*P)->ltag = Link; (*P)->rtag = Thread;
    (*P)->rchild = *P; // 右指向自己
    if (!T) { (*P)->lchild = *P; return; }
    (*P)->lchild = T;
    pre = *P;
    in_order_threading(T);
    (*P)->rchild = pre; // 頭結點右指向最後節點
    pre->rchild = *P;   // 最後節點右指向頭結點
    pre->rtag = Thread;
}

4. 非遞歸中序遍歷

void in_order_traverse(BiTree P) {
    BiTree T = P->lchild;
    while (T != P) {
        while (T->ltag == Link) T = T->lchild; // 找最左
        visit(T);
        while (T->rtag == Thread && T->rchild != P) {
            T = T->rchild; // 沿線索找後繼
            visit(T);
        }
        T = T->rchild; // 進入右子樹
    }
}

測試範例

int main() {
    BiTree P, T;
    char *preorder = "ab d ce "; // 空格代表空節點
    create_tree(&T, &preorder);
    in_thread(&P, T);
    in_order_traverse(P); // 輸出中序序列
    return 0;
}