线索二叉树的 C 语言实现

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

// 线索二叉树节点结构（标准定义）
typedef struct ThreadNode {
    int data;                  // 数据域
    struct ThreadNode *lchild, *rchild;  // 左、右指针（可指向孩子或线索）
    int ltag, rtag;            // 线索标志：0表示指向孩子，1表示指向线索
} ThreadNode, *ThreadTree;

// 全局变量：记录当前节点的前驱
ThreadNode *pre = NULL;

// 初始化前驱节点
void initPre() {
    pre = NULL;
}

// 中序线索化二叉树（核心算法）
void InThread(ThreadTree T) {
    if (T != NULL) {
        InThread(T->lchild);  // 递归线索化左子树
  
        // 处理当前节点的左线索
        if (T->lchild == NULL) {
            T->lchild = pre;  // 左指针指向前驱节点
            T->ltag = 1;      // 标记为左线索
        } else {
            T->ltag = 0;      // 标记为左孩子
        }
  
        // 处理前驱节点的右线索
        if (pre != NULL && pre->rchild == NULL) {
            pre->rchild = T;  // 前驱节点的右指针指向当前节点
            pre->rtag = 1;    // 标记为右线索
        }
  
        pre = T;  // 更新前驱节点为当前节点
  
        InThread(T->rchild);  // 递归线索化右子树
    }
}

// 创建中序线索二叉树（对根节点特殊处理）
void CreateInThread(ThreadTree T) {
    initPre();  // 初始化前驱节点
    if (T != NULL) {
        InThread(T);          // 中序线索化整棵树
        pre->rchild = NULL;   // 处理最后一个节点的右线索
        pre->rtag = 1;
    }
}

// 找到中序线索二叉树的第一个节点（最左下节点）
ThreadNode* FirstNode(ThreadNode *p) {
    while (p->ltag == 0) {    // 左标志为0，说明有左孩子，继续向左
        p = p->lchild;
    }
    return p;
}

// 找到节点p在中序线索化中的后继节点
ThreadNode* NextNode(ThreadNode *p) {
    if (p->rtag == 0) {       // 右标志为0，后继是右子树的第一个节点
        return FirstNode(p->rchild);
    } else {
        return p->rchild;     // 右标志为1，直接通过右线索获取后继
    }
}

// 中序遍历线索二叉树（非递归，高效）
void InOrderTraverse(ThreadTree T) {
    for (ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p)) {
        printf("%d ", p->data);
    }
}

// 创建节点
ThreadNode* createNode(int data) {
    ThreadNode *node = (ThreadNode*)malloc(sizeof(ThreadNode));
    if (node == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    node->data = data;
    node->lchild = node->rchild = NULL;
    node->ltag = node->rtag = 0;  // 初始化为孩子指针
    return node;
}

// 释放线索二叉树
void freeThreadTree(ThreadTree T) {
    if (T != NULL) {
        if (T->ltag == 0) {  // 左指针是孩子，递归释放
            freeThreadTree(T->lchild);
        }
        if (T->rtag == 0) {  // 右指针是孩子，递归释放
            freeThreadTree(T->rchild);
        }
        free(T);
    }
}

int main() {
    // 构建一棵示例二叉树
    //       1
    //      / \
    //     2   3
    //    /   /
    //   4   5
    ThreadTree root = createNode(1);
    root->lchild = createNode(2);
    root->rchild = createNode(3);
    root->lchild->lchild = createNode(4);
    root->rchild->lchild = createNode(5);
  
    // 创建中序线索
    CreateInThread(root);
  
    printf("中序线索遍历结果：");
    InOrderTraverse(root);  // 预期输出：4 2 1 5 3
  
    // 释放内存
    freeThreadTree(root);
    return 0;
}

一、时间复杂度

所有核心操作的时间复杂度均为 O(n)（n 为二叉树的节点总数），具体如下：

线索化过程（InThread 和 CreateInThread）

线索化本质是对二叉树进行一次完整的中序遍历，每个节点会被访问恰好一次：
- 对每个节点的操作（判断左右指针是否为空、修改线索标志、更新前驱节点）都是常数时间 O (1)；
- 总操作次数与节点数 n 成正比，因此时间复杂度为 O (n)。
遍历过程（InOrderTraverse）

线索化后的遍历通过 FirstNode找到起点，再通过 NextNode依次访问所有节点，每个节点同样被访问一次：
- FirstNode最多遍历到树的最左下节点（路径长度为树的高度，最坏 O (n)，但整体遍历中每个节点仅被该函数访问一次）；
- NextNode对每个节点的操作是常数时间（判断标志位、跳转指针）；
  整体遍历的总操作次数为 O (n)，时间复杂度为 O (n)。
辅助操作（createNode、freeThreadTree等）
- 创建节点：每个节点被创建一次，总时间 O (n)；
- 释放内存：每个节点被释放一次，总时间 O (n)。

二、空间复杂度

空间复杂度需分线索化阶段和遍历阶段区分：

线索化阶段（InThread 递归过程）

空间复杂度取决于递归调用栈的深度（无其他额外辅助空间）：
- 最坏情况：二叉树为 “斜树”（所有节点只有左孩子或右孩子），递归栈深度等于节点数 n，空间复杂度为 O (n)；
- 最好情况：二叉树为 “平衡树”（左右子树高度接近），递归栈深度为树的高度 log₂n（向上取整），空间复杂度为 O (log n)。
遍历阶段（InOrderTraverse）

遍历过程是非递归的，仅使用了几个指针变量（p、FirstNode和 NextNode的临时变量），没有额外的栈或队列开销，因此空间复杂度为 O(1)。

这是线索二叉树的核心优势 —— 相比普通二叉树的递归遍历（O (n) 空间）或迭代遍历（O (n) 栈空间），线索化遍历能做到常数空间复杂度。
其他操作
- createNode：每次创建一个节点，总空间为存储 n 个节点的内存（O (n)），但这是存储数据本身的空间，不计入算法额外开销；
- freeThreadTree：递归释放节点，空间复杂度与线索化阶段一致（取决于树高，O (n) 最坏，O (log n) 最好）。

总结

时间复杂度：所有核心操作（线索化、遍历、创建、释放）均为 O (n)，与节点总数线性相关；
空间复杂度：线索化阶段为 O (h)（h 为树高，最坏 O (n)，最好 O (log n)），遍历阶段为 O (1)（线索二叉树的显著优势）。

这种特性使得线索二叉树特别适合对遍历效率和空间开销敏感的场景，尤其是需要频繁遍历且内存有限的情况。

目录CONTENT

线索二叉树

线索二叉树的 C 语言实现

一、时间复杂度

二、空间复杂度

总结

评论区