C语言线索二叉树的前中后如何创建和遍历

# C语言线索二叉树的前中后如何创建和遍历

## 一、线索二叉树概述

### 1.1 基本概念
线索二叉树（Threaded Binary Tree）是通过利用二叉树中的空指针域来存储结点在某种遍历顺序下的前驱或后继信息的一种二叉树结构。在普通二叉树中：
- 含有n个结点的二叉树有n+1个空指针域
- 线索化就是利用这些空指针存放指向结点在特定遍历顺序下的前驱或后继的指针

### 1.2 线索化类型
根据遍历顺序的不同，线索二叉树可分为：
- 前序线索二叉树
- 中序线索二叉树
- 后序线索二叉树

### 1.3 结点结构
线索二叉树的结点通常包含以下字段：
```c
typedef struct ThreadNode {
    int data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;  // 0表示孩子，1表示线索
} ThreadNode, *ThreadTree;

二、前序线索二叉树的创建与遍历

2.1 前序线索化算法

// 全局变量，始终指向前一个访问的结点
ThreadNode *pre = NULL;

void PreThread(ThreadTree p) {
    if (p != NULL) {
        // 处理当前结点
        if (p->lchild == NULL) {
            p->lchild = pre;
            p->ltag = 1;
        }
        if (pre != NULL && pre->rchild == NULL) {
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
        
        // 递归线索化左子树（注意判断是否为真孩子）
        if (p->ltag == 0)
            PreThread(p->lchild);
            
        // 递归线索化右子树
        if (p->rtag == 0)
            PreThread(p->rchild);
    }
}

void CreatePreThread(ThreadTree T) {
    pre = NULL;
    if (T != NULL) {
        PreThread(T);
        // 处理最后一个结点的右指针
        if (pre->rchild == NULL)
            pre->rtag = 1;
    }
}

2.2 前序线索遍历

void PreOrder(ThreadTree T) {
    while (T != NULL) {
        // 访问当前结点
        printf("%d ", T->data);
        
        // 有左孩子则访问左孩子
        if (T->ltag == 0)
            T = T->lchild;
        else  // 否则沿线索访问后继
            T = T->rchild;
    }
}

三、中序线索二叉树的创建与遍历

3.1 中序线索化算法

void InThread(ThreadTree p) {
    if (p != NULL) {
        InThread(p->lchild);  // 递归线索化左子树
        
        // 处理当前结点
        if (p->lchild == NULL) {
            p->lchild = pre;
            p->ltag = 1;
        }
        if (pre != NULL && pre->rchild == NULL) {
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
        
        InThread(p->rchild);  // 递归线索化右子树
    }
}

void CreateInThread(ThreadTree T) {
    pre = NULL;
    if (T != NULL) {
        InThread(T);
        // 处理最后一个结点的右指针
        if (pre->rchild == NULL)
            pre->rtag = 1;
    }
}

3.2 中序线索遍历

// 找到以p为根的子树中第一个被中序遍历的结点
ThreadNode *FirstNode(ThreadNode *p) {
    while (p->ltag == 0)
        p = p->lchild;
    return p;
}

// 找到p在中序序列下的后继结点
ThreadNode *NextNode(ThreadNode *p) {
    if (p->rtag == 1)
        return p->rchild;
    else
        return FirstNode(p->rchild);
}

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

四、后序线索二叉树的创建与遍历

4.1 后序线索化算法

void PostThread(ThreadTree p) {
    if (p != NULL) {
        PostThread(p->lchild);  // 递归线索化左子树
        PostThread(p->rchild);  // 递归线索化右子树
        
        // 处理当前结点
        if (p->lchild == NULL) {
            p->lchild = pre;
            p->ltag = 1;
        }
        if (pre != NULL && pre->rchild == NULL) {
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
    }
}

void CreatePostThread(ThreadTree T) {
    pre = NULL;
    if (T != NULL) {
        PostThread(T);
        // 处理最后一个结点的右指针
        if (pre->rchild == NULL)
            pre->rtag = 1;
    }
}

4.2 后序线索遍历

后序线索树的遍历较为复杂，通常需要借助栈或三叉链表实现：

// 需要知道父结点的情况（实际实现可能需要修改数据结构）
void PostOrder(ThreadTree T) {
    if (T == NULL) return;
    
    ThreadTree prev = NULL;
    ThreadTree curr = T;
    
    while (curr != NULL) {
        // 向左走到底
        while (curr->ltag == 0 && curr->lchild != prev)
            curr = curr->lchild;
            
        // 处理右子树
        while (curr != NULL && curr->rtag == 1) {
            printf("%d ", curr->data);
            prev = curr;
            curr = curr->rchild;
        }
        
        // 处理叶子结点或回到根结点的情况
        if (curr == T && curr->rchild == prev) {
            printf("%d ", curr->data);
            return;
        }
        
        // 转向右子树
        if (curr != NULL && curr->rtag == 0) {
            curr = curr->rchild;
        }
    }
}

五、完整示例代码

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

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

// 创建示例二叉树
ThreadTree CreateExampleTree() {
    ThreadNode *nodes[6];
    for (int i = 0; i < 6; i++) {
        nodes[i] = (ThreadNode*)malloc(sizeof(ThreadNode));
        nodes[i]->data = i + 1;
        nodes[i]->lchild = nodes[i]->rchild = NULL;
        nodes[i]->ltag = nodes[i]->rtag = 0;
    }
    
    nodes[0]->lchild = nodes[1];  // 1->2
    nodes[0]->rchild = nodes[2];  // 1->3
    nodes[1]->lchild = nodes[3];  // 2->4
    nodes[1]->rchild = nodes[4];  // 2->5
    nodes[2]->rchild = nodes[5];  // 3->6
    
    return nodes[0];
}

// 中序线索化示例
ThreadNode *pre = NULL;

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

void CreateInThread(ThreadTree T) {
    pre = NULL;
    if (T != NULL) {
        InThread(T);
        if (pre->rchild == NULL)
            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;
    else
        return FirstNode(p->rchild);
}

void InOrder(ThreadTree T) {
    for (ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p))
        printf("%d ", p->data);
    printf("\n");
}

int main() {
    ThreadTree T = CreateExampleTree();
    CreateInThread(T);
    
    printf("InOrder traversal: ");
    InOrder(T);
    
    return 0;
}

六、应用场景与总结

6.1 实际应用

1. 数据库索引结构
2. 文件系统目录结构
3. 表达式树的高效处理
4. 编译器语法分析

6.2 性能分析

• 空间效率：利用空指针域，不增加额外存储
• 时间效率：遍历时间复杂度O(n)，且不需要递归栈空间

6.3 不同线索方式的比较

线索二叉树通过利用空指针域，实现了非递归的高效遍历，是二叉树的重要优化方式。开发者应根据具体需求选择合适的线索化方式。 “`