線索二叉樹的原理及創建是怎樣的

# 線索二叉樹的原理及創建是怎樣的

## 目錄
1. [引言](#引言)
2. [二叉樹遍歷的局限性](#二叉樹遍歷的局限性)
3. [線索二叉樹的基本概念](#線索二叉樹的基本概念)
   - [3.1 線索化定義](#31-線索化定義)
   - [3.2 線索指針類型](#32-線索指針類型)
4. [線索二叉樹的結構設計](#線索二叉樹的結構設計)
5. [線索二叉樹的創建過程](#線索二叉樹的創建過程)
   - [5.1 中序線索化算法](#51-中序線索化算法)
   - [5.2 先序線索化實現](#52-先序線索化實現)
   - [5.3 后序線索化方法](#53-后序線索化方法)
6. [線索二叉樹的遍歷](#線索二叉樹的遍歷)
7. [線索二叉樹的應用場景](#線索二叉樹的應用場景)
8. [完整代碼示例](#完整代碼示例)
9. [總結](#總結)

## 引言

在傳統二叉樹結構中，每個節點包含數據域和左右孩子指針，但存在大量空指針未被利用（約n+1個空指針，n為節點數）。線索二叉樹（Threaded Binary Tree）通過利用這些空指針指向遍歷序列中的前驅或后繼節點，顯著提高了遍歷效率，將時間復雜度從O(n)降低到O(1)（平均情況）。

## 二叉樹遍歷的局限性

普通二叉樹遍歷（中序、先序、后序）存在兩大問題：
1. **空間浪費**：每個葉節點有兩個NULL指針，分支節點有一個NULL指針
2. **遍歷低效**：非遞歸遍歷需要借助棧結構，空間復雜度為O(h)（h為樹高）

| 指針類型 | 普通二叉樹 | 線索二叉樹 |
|---------|------------|------------|
| 左指針  | 指向左子樹或NULL | 指向左子樹或前驅 |
| 右指針  | 指向右子樹或NULL | 指向右子樹或后繼 |

## 線索二叉樹的基本概念

### 3.1 線索化定義
線索化是指將二叉樹中的空指針改為指向某種遍歷順序下的前驅或后繼節點。根據遍歷方式不同分為：
- 中序線索二叉樹
- 先序線索二叉樹
- 后序線索二叉樹

### 3.2 線索指針類型
每個節點需要增加兩個標志位：
```c
typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;  // 0表示孩子，1表示線索
} ThreadNode;

線索二叉樹的結構設計

節點結構示意圖：

+---------------+
| data          |
+---------------+
| lchild | ltag |
+---------------+
| rchild | rtag |
+---------------+

線索化規則： 1. 若節點無左子樹，則lchild指向其前驅 2. 若節點無右子樹，則rchild指向其后繼 3. 增加頭節點作為遍歷的起點和終點

線索二叉樹的創建過程

5.1 中序線索化算法

ThreadNode *pre = NULL;  // 全局變量記錄前驅

void InThread(ThreadNode *p) {
    if (p) {
        InThread(p->lchild);  // 遞歸左子樹線索化
        
        if (!p->lchild) {     // 左子樹為空
            p->ltag = 1;
            p->lchild = pre;  // 指向前驅
        }
        if (pre && !pre->rchild) {  // 前驅的右子樹為空
            pre->rtag = 1;
            pre->rchild = p;  // 指向后繼
        }
        pre = p;
        
        InThread(p->rchild);  // 遞歸右子樹線索化
    }
}

5.2 先序線索化實現

void PreThread(ThreadNode *p) {
    if (p) {
        if (!p->lchild) {
            p->ltag = 1;
            p->lchild = pre;
        }
        if (pre && !pre->rchild) {
            pre->rtag = 1;
            pre->rchild = p;
        }
        pre = p;
        
        if (p->ltag == 0)  // 防止死循環
            PreThread(p->lchild);
        PreThread(p->rchild);
    }
}

5.3 后序線索化方法

void PostThread(ThreadNode *p) {
    if (p) {
        PostThread(p->lchild);
        PostThread(p->rchild);
        
        if (!p->lchild) {
            p->ltag = 1;
            p->lchild = pre;
        }
        if (pre && !pre->rchild) {
            pre->rtag = 1;
            pre->rchild = p;
        }
        pre = p;
    }
}

線索二叉樹的遍歷

中序線索樹遍歷示例：

void InOrder(ThreadNode *T) {
    ThreadNode *p = T;
    while (p) {
        while (p->ltag == 0) p = p->lchild;  // 找最左節點
        visit(p);
        
        while (p->rtag == 1 && p->rchild) {  // 通過線索訪問后繼
            p = p->rchild;
            visit(p);
        }
        p = p->rchild;  // 轉入右子樹
    }
}

時間復雜度分析： - 普通中序遍歷：O(n)時間 + O(h)空間 - 線索中序遍歷：O(n)時間 + O(1)空間

線索二叉樹的應用場景

1. 數據庫索引：B+樹的變種實現
2. 編譯器設計：語法樹分析
3. 內存管理：快速查找空閑內存塊
4. 圖形處理：區域劃分數據結構

優勢對比： - 相對于普通二叉樹：節省空間，加快遍歷 - 相對于平衡二叉樹：實現簡單，不需旋轉操作 - 相對于哈希表：保持數據有序性

完整代碼示例

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;

typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
} ThreadNode;

ThreadNode *pre = NULL;

void CreateTree(ThreadNode **T) {
    ElemType ch;
    scanf("%c", &ch);
    if (ch == '#') {
        *T = NULL;
    } else {
        *T = (ThreadNode *)malloc(sizeof(ThreadNode));
        (*T)->data = ch;
        (*T)->ltag = (*T)->rtag = 0;
        CreateTree(&(*T)->lchild);
        CreateTree(&(*T)->rchild);
    }
}

void InThread(ThreadNode *p) {
    if (p) {
        InThread(p->lchild);
        
        if (!p->lchild) {
            p->ltag = 1;
            p->lchild = pre;
        }
        if (pre && !pre->rchild) {
            pre->rtag = 1;
            pre->rchild = p;
        }
        pre = p;
        
        InThread(p->rchild);
    }
}

void CreateInThread(ThreadNode *T) {
    if (T) {
        InThread(T);
        pre->rtag = 1;  // 處理最后一個節點
    }
}

ThreadNode *FirstNode(ThreadNode *p) {
    while (p->ltag == 0) p = p->lchild;
    return p;
}

ThreadNode *NextNode(ThreadNode *p) {
    if (p->rtag == 1) return p->rchild;
    return FirstNode(p->rchild);
}

void InOrder(ThreadNode *T) {
    for (ThreadNode *p = FirstNode(T); p; p = NextNode(p))
        printf("%c ", p->data);
}

int main() {
    ThreadNode *T = NULL;
    printf("輸入先序序列(#表示空節點): ");
    CreateTree(&T);
    CreateInThread(T);
    printf("中序遍歷結果: ");
    InOrder(T);
    return 0;
}

總結

線索二叉樹通過巧妙利用空指針實現了以下突破： 1. 空間利用率提升50%以上（n個節點節省n+1個指針） 2. 遍歷過程無需遞歸或棧結構 3. 前驅/后繼查找時間復雜度降為O(1)

三種線索化方式各有特點： - 中序線索化：最適合排序操作 - 先序線索化：適合復制樹結構 - 后序線索化：適用于銷毀樹操作

未來改進方向： 1. 動態線索化與去線索化 2. 多線程環境下的線索安全操作 3. 結合平衡樹特性的線索AVL樹 “`