线索二叉树的原理及创建是怎样的

发布时间：2021-12-13 17:27:47 作者：柒染
来源：亿速云阅读：276

# 线索二叉树的原理及创建是怎样的

## 目录
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)空间

线索二叉树的应用场景

数据库索引：B+树的变种实现
编译器设计：语法树分析
内存管理：快速查找空闲内存块
图形处理：区域划分数据结构

优势对比： - 相对于普通二叉树：节省空间，加快遍历 - 相对于平衡二叉树：实现简单，不需旋转操作 - 相对于哈希表：保持数据有序性

完整代码示例

#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树 “`