[数据结构与算法]5.9 二叉树线索化

//一些辅助的全局变量，用于查找结点p的前驱
BiTNode *p;				//p指向目标结点
BiTNode *pre = NULL;	//指向当前访问结点的前驱
BiTNode *final = NULL;	//用来记录最终结果

//中序遍历
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);	//递归遍历左子树
        visit(T);			//访问根节点
        InOrder(T->rchild);	//递归遍历右子树
    }
}

//访问结点q
void visit(BiTNode *q){
    if(q==p)			//当前访问结点刚好是p结点
        final = pre;	//找到p的前驱
    else
        pre = q;		//pre指向当前访问的结点
}

一、中序线索化

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

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

//中序线索化二叉树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->ltag = 1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild = q;	//建立前驱结点的后继线索
        pre->rtag = 1;
    }
    pre = q;
}

【思考】处理完遍历的最后一个结点，为什么没有判断rchild是否为NULL？

【解】因为在中序遍历时访问完一个结点后，如果有右孩子，那就一定会去访问右孩子，所以可以断定，最后一个节点，必没有右孩子

二、先序线索化

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

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

三、后序线索化

//全局变量 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;
}

四、总结

【核心】

1. 中序/先序/后序遍历算法的改造，当访问一个结点时，连接该结点与前驱结点的线索信息
2. 用一个指针pre记录当前访问结点的前驱结点

【易错点】

1. 最后一个结点的rchild、rtag的处理
2. 先序线索化中，注意处理 “爱的魔力转圈圈问题” ，当ltag == 0 时，才能对左子树先序线索化