数据结构 -- 线索二叉树

线索二叉树

线索二叉树的概念

线索二叉树的作用

我们在进行中序遍历时，总是从根节点出发进行二叉树遍历，而当仅知道某一孩子节点的指针时，由于无法访问父节点，所以没有办法进行遍历。由此引入线索二叉树

【思考】①如何找到指定结点p在中序遍历序列中的前驱？②如何找到p的后继

【思路】从根节点出发，重新进行依次中序遍历，指针q记录当前访问的结点，指针pre记录上一个被访问的结点①当q == p时，pre为前驱②当pre == p时，q为后继

【缺点】很不方便，遍历操作必须从根结点开始

【解决】引入线索二叉树

n个节点的二叉树，由n+1个空链域！可以用来记录前驱、后继的信息

前驱线索由左孩子充当，后驱线索由右孩子充当（如果没有前驱或没有后继则左/右孩子为NULL）

线索二叉树的存储结构

增加左右线索标志 ltag 、rtag

tag == 0，表示指针指向孩子

tag == 1，表示指针是“线索”

//线索二叉树的结点（链式存储）
typedef struct ThreadNode{
    ElemType data;						//数据域
    struct ThreadNode * lchild,*rchild;	//左右孩子
    int ltag,rtag;			//左右线索
}ThreadNode,*ThreadTree;

三种线索二叉树

中序线索二叉树：以中序遍历序列为依据进行“线索化”

先序线索二叉树：以先序遍历序列为依据进行“线索化”

后序线索二叉树：以后序遍历序列为依据进行“线索化”

几个概念：

线索：指向前驱/后继的指针称为线索

中序前驱/中序后继；先序前驱/先序后继；后序前驱/后序后继

手算画出线索二叉树

① 确定线索二叉树类型（中序、先序、后序）

② 按照对应遍历规则，确定各个结点的访问顺序，并写上编号

③ 将n+1个空链域脸上前驱、后继

二叉树的线索化

中序线索化

//线索二叉树的结点（链式存储）
typedef struct ThreadNode{
    ElemType data;						//数据域
    struct ThreadNode * lchild,*rchild;	//左右孩子
    int ltag,rtag;			//左右线索
}ThreadNode,*ThreadTree;

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

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

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

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

先序线索化

//线索二叉树的结点（链式存储）
typedef struct ThreadNode{
    ElemType data;						//数据域
    struct ThreadNode * lchild,*rchild;	//左右孩子
    int ltag,rtag;			//左右线索
}ThreadNode,*ThreadTree;

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

//先序线索化二叉树T
void CreatePreThread(TreadTree 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)	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->rchild = q;	//建立前驱结点的后继线索
        pre->rtag = 1;
    }
    pre = q;
}

【注意】在线序线索化过程中，在访问完左孩子之后会返回根结点导致循环，所以要在遍历左子树之前先判断当前的左孩子是真正的左孩子还是线索

后序线索化

//线索二叉树的结点（链式存储）
typedef struct ThreadNode{
    ElemType data;						//数据域
    struct ThreadNode * lchild,*rchild;	//左右孩子
    int ltag,rtag;			//左右线索
}ThreadNode,*ThreadTree;

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

//后序线索化二叉树T
void CreatePostThread(TreadTree 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;
}