二叉树的线索化

二叉树的线索化

线索二叉树：

1. 中序线索化 左中右
2. 先序线索化 中左右
3. 后序线索化 左右中

用土办法找到中序前驱

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

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

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

中序线索化

左中右

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

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

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

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

先序线索化

中左右

注意：做了前驱线索，小心遍历的时候无限转圈圈。

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

//先序线索化二叉树T
void CreatePreThread(ThreadTree T){
    pre = NULL;
    if(T!=NULL){
        PreThread(T);
        if(pre->rchild == NULL){
            pre->rtag = 1;
        }
    }
}

//先序遍历二叉树，一边遍历一边线索化
void PreThread(ThreadTree T){
    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 CreatePreThread(ThreadTree T){
    pre = NULL;
    if(T!=NULL){
        PreThread(T);
        if(pre->rchild == NULL){
            pre->rtag = 1;
        }
    }
}

//后序遍历二叉树，一边遍历一边线索化
void PostThread(ThreadTree T){
    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;
}

总结