26、数据结构——二叉树——线索二叉树

前言

对于普通二叉树而言，现在提出一个问题，如果随意给出你一个结点p，现在需要你找到它中序遍历对于结点p而言在遍历的时候的前驱或者后继（注意：这个的前驱是指中序遍历的时候的前驱哟！） 。这个时候就会比较麻烦了，你必须对这课树从根节点出发重新进行一次中序遍历，同时还需要准备两个指针分别指向当前结点p和当前结点的前驱pre两个。但是这样的话就会非常不方便，效率也会很低，因此我们就引入了线索二叉树来解决这种特殊情况问题。

代码

// 寻找某个节点的前驱节点
typedef struct BiTNode {
    ElemType data;
    struct BiNode *lchild, rchild;
}BitNode,*BitTree;

BitNode *p; // p指向目标节点，也就是我们现在要寻找的某个结点
BitNode *pre = NULL; // pre指向前驱结点
BitNode *final = NULL; // final用于记录最终结果

void visit(BitNode *q) { // 这里实际上也可以写成BitTree q，但是为了将树和节点区分开，我们才使用这种写法！！！
    if (q==p) { // q节点就是目标节点p
        final = pre; // 此时的前驱节点就是目标节点的前驱节点
    } else {
        pre = p; // pre指向当前结点
    }
}
void InOrder(BitTree T){
    if (T!=NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

注意：如果你是以考研为目标，我下面的内容写得比较简单，可能不是非常好懂，这里开始就必须大家自己去寻找一些视频进行观看了，反之如果不是以考研为目标，这一节内容简单了解即可，可以先行跳过，期末有需求再额外学习

一、中序线索二叉树

对于一个 n 个结点的二叉树，有 n + 1 空指针域！可用来记录前驱和后继信息。

前驱线索： 左孩子指针充当

后驱线索： 右孩子指针充当

存储结构

//线索二叉树结点
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag,rtag; // 左右线索标志位：两个tag==0的时候表示指向孩子，==1表示是线索的
}ThreadNode,*ThreadTree;

// 全局变量 pre，指向当前访问节点的前驱
ThreadNode *pre = NULL;

中序线索二叉树的构建

void visit(ThreadNode *q) {
    if (q -> lchild==NULL) { // 左子树为空，建立前驱线索 
        q -> lchild = pre;
        q -> ltag = 1;
    }
    if (pre != NULL && pre -> rchild == NULL){ 
        // 当前结点左子树不为空，那么我们就看看前驱结点的右孩子节点是否为空
        pre -> rchild = q; // 建立前驱节点的后继线索
        pre -> rtag = 1;
    }
    pre = q;
}

void InThread(ThreadTree T) {
    if (T!=NULL){
        InThread(T->lchild);
        visit(T);
        InThread(T->rchild);
    }
}

void CreateInThread(ThreadTree T){
    pre = NULL;
    if (T != NULL) {
        InThread(T);
        if (pre -> rchild == NULL) { 
  // 按道理来说，如果是前序遍历的最后一个结点，应该是绝对不存在右节点的，因此，不用这个判断条件也是可以的
            pre -> rtag = 1;
        }
    }
}

二、先序线索二叉树（和中序的差不多）

代码

void visit(ThreadNode *q) {
    if (q -> lchild==NULL) { // 左子树为空，建立前驱线索 
        q -> lchild = pre;
        q -> ltag = 1;
    }
    if (pre != NULL && pre -> rchild == NULL){ 
        // 当前结点左子树不为空，那么我们就看看前驱结点的右孩子节点是否为空
        pre -> rchild = q; // 建立前驱节点的后继线索
        pre -> rtag = 1;
    }
    pre = q;
}

void PreThread(ThreadTree T) {
    if (T!=NULL){
        visit(T);
        // 这里加上判断条件的原因是：防止出现死循环。因为如果T->ltag == 1的话，那么就意味着左孩子节点是之前已经线索过了的，如果这时候还将左孩子节点赋值给它，就会出现死循环的情况。
        if (T->ltag == 0) PreThread(T->lchild); 
        PreThread(T->rchild);
    }
}

void CreateInThread(ThreadTree T){
    pre = NULL;
    if (T != NULL) {
        PreThread(T);
        if (pre -> rchild == NULL) { 
  // 按道理来说，如果是中序遍历的最后一个结点，应该是绝对不存在右节点的，因此，不用这个判断条件也是可以的
            pre -> rtag = 1;
        }
    }
}

三、后序线索二叉树

void visit(ThreadNode *q) {
    if (q -> lchild==NULL) { // 左子树为空，建立前驱线索 
        q -> lchild = pre;
        q -> ltag = 1;
    }
    if (pre != NULL && pre -> rchild == NULL){ 
        // 当前结点左子树不为空，那么我们就看看前驱结点的右孩子节点是否为空
        pre -> rchild = q; // 建立前驱节点的后继线索
        pre -> rtag = 1;
    }
    pre = q;
}

void PostThread(ThreadTree T) {
    if (T!=NULL){
        PostThread(T->lchild); 
        PreThread(T->rchild);
        visit(T);
    }
}

void CreateInThread(ThreadTree T){
    pre = NULL;
    if (T != NULL) {
        PostThread(T);
        if (pre -> rchild == NULL) { 
  // 按道理来说，如果是后序遍历的最后一个结点，应该也是绝对不存在右节点的，因此，不用这个判断条件也是可以的
            pre -> rtag = 1;
        }
    }
}

一节内容是27、树——存储结构…….

一定要把本节内容看懂再往下看，不然会非常痛苦的哦o(╥﹏╥)oo(╥﹏╥)oo(╥﹏╥)o

27、数据结构——树——存储结构上一篇

25、数据结构——二叉树——通过遍历构建二叉树下一篇