中序线索化二叉树

发布时间 2023-09-15 21:27:44作者: CherriesOvO

思路:

1、线索化二叉树结点定义与二叉树基本相同,只是在原先的基础上添加了int类型的左右线索标志。
2、定义全局变量pre,用来指向当前结点的前驱结点。
3、构造visit()时,如果访问结点的左孩子为空,需要建立前驱线索并将ltag设为1;如果访问结点的前驱结点不为空且其右孩子为空,需要建立后继线索并将rtag设为1。
4、对二叉树进行中序线索化时,先对其左子树进行中序线索化,再访问根结点,最后对右子树进行中序线索化。

代码:

#include<stdio.h>

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

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

int main(){
	
}