【数据结构】线索二叉树

1. 思考

一个二叉树中序遍历序列中，如何找到指定结点p的前驱和后继？

思路：从根结点除法，重新进行依次中序遍历，指针q记录当前访问的结点，指针pre记录上一个被访问的结点。当q==p时，pre为前驱。当pre==p时，q为后继。

缺点：找前驱、后继很不方便；遍历操作必须从根开始。

2. 中序线索二叉树

// 二叉树的结点（链式存储）
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

我们将二叉树线索化，得到如下链表：

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;  // 左、右线索标志
}ThreadNode,*ThreadTree;

使用同样的方法可以得到先序线索二叉树和后序线索二叉树。

3. 中序线索化

// 线索二叉树结点
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;  // 左、右线索标志
}ThreadNode,*ThreadTree;

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

// 中序线索化二叉树T
void CreatInThread(ThreadTree T){
    pre=NULL;  // pre初始化为NULL
    if(T!=NULL){  // 非空二叉树才线索化
        InThread(T);  // 中序线索化二叉树
        if(pre->rchild==NULL){
            pre->rtag=1;  // 处理遍历的最后一个结点
        }
    }
}

// 中序遍历二叉树，一边遍历一边线索化
void InThread(ThreadTree T){
    if(T!=NULL){
        InThread(T->lchild);  // 中序遍历左子树
        visit(T);   // 访问根结点
        InThread(T->rchild);  // 中序遍历右子树
    }
}

void visit(ThreadNode *q){
    if(q->lchild==NULL){ // 左子树为空，建立前驱线索
        q->lchild=pre;
        q->tag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q;  // 建立前驱结点的后继线索
        pre->rtag=1;
    }
    pre=q;
}

4. 先序线索化

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

// 先序线索化二叉树T
void CreatThread(ThreadTree T){
    pre=NULL;   // pre初始为NULL
    if(T!=NULL){  // 非空二叉树才能线索化
        PreThread(T);  // 先序线索化二叉树
        if(pre->rchild==NULL){
            pre->rtag=1;  // 处理遍历的最后一个结点
        }
    }
}

// 先序遍历二叉树，一边遍历一边线索化
void PreThread(ThreadTree T){
    if(T!=NULL){
        visit(T);  // 先处理根结点
        if(T->ltag==0){  // lchild不是前驱结点
            PreThread(T->lchild);
        }
        PreThread(T->rchild);
    }
}

void visit(ThreadNode *q){
    if(q->lchild==NULL){  // 左子树为空，建立前驱线索
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->lchild=q;  // 建立前驱结点的后继线索
        pre->rtag=1;
    }
    pre=q;
}

5. 后序线索化

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

// 后序线索化二叉树T
void CreatPostThread(ThreadTree T){
    pre=NULL;  // pre初始化为NULL
    if(T!=NULL){  // 非空二叉树才能线索化
        PostThread(T);  // 后序线索化二叉树
        if(pre->rchild==NULL){
            pre->rtag=1;  // 处理遍历的最后一个结点
        }
    }
}

// 后序遍历二叉树，一边遍历一边线索化
void PostThread(ThreadTree T){
    if(T!=NULL){
        PostThread(T->lchild);  // 后序遍历左子树
        PostThread(T->rchild);  // 后序遍历右子树
        visit(T);
    }
}

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;
}