线索二叉树

举报
莫浅子 发表于 2022/10/12 23:21:48 2022/10/12
【摘要】 ​ 线索二叉树概念——普通二叉树缺点1、普通二叉树在遍历的时候必须从根节点出发,不能从其中某一点开始遍历。2、普通二叉树不能快速的找到某个结点的前驱。(可以实现,思路如下)从根结点出发,重新进行一次中序遍历,指针q记录当前访问的结点,指针pre记录上一个被访的结点 ①当 q == p 时,pre为前驱    ②当 pre == p 时,q为后继缺点是找前驱,后继操作不方便:遍历操作必须从根开...

 线索二叉树概念

——普通二叉树缺点

1、普通二叉树在遍历的时候必须从根节点出发,不能从其中某一点开始遍历。

2、普通二叉树不能快速的找到某个结点的前驱。(可以实现,思路如下)

从根结点出发,重新进行一次中序遍历,指针q记录当前访问的结点,指针pre记录上一个被访的结点 ①当 q == p 时,pre为前驱

    ②当 pre == p 时,q为后继

缺点是找前驱,后继操作不方便:遍历操作必须从根开始


——中序线索二叉树

n个结点的二叉树,有n+1个空链域!可以用来记录n个前驱、后继的信息

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

图示说明 

 代码如下

//二叉树的结点(链式存储) 
typedef struct BiTNode{
	ElemType date;
	struct BiTNode *lchild, *rchild
}BiTNode ,*BiTree;
//线索二叉树结点 
typedef struct ThreadNode{
	ElemType date;
	struct ThreadNode *lchild *rchild;
	int ltag,rtag;
}ThreadNode,*ThreadTree;

tag == 0 ,表示指针是指向孩子

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


——先序线索二叉树

和上同理



——后序线索二叉树 

和上同理

—— 三种线索二叉树的比较





二叉树的线索化

用土方法找到中序遍历前驱

普通方法代码

//辅助全局变量,用于查找p的前驱 
BiTNode *p;  //p指向目标结点 
BiTNode * pre = NULL; //指向当前访问结点的前驱 
BiTNode * fina = NULL; //用于记录最终结果 
void InOrder(BITree T){
	if(T != NULL){
		InOrder(T->lchild);  //递归遍历左子树 
		visit(T);          // 访问根结点 
		InOrder(T->rchild);  // 递归遍历右子树 
	}
} 
// 访问结点q
void visit(BoTNode *q){
	if(q == p)         //当前访问的结点刚好是p 
	   final = pre;    //找到p的前驱 
	else 
	   pre = q;   //pre指向当前访问的结点 
} 

中序线索化代码

当ltag = 0,rtag = 0 的时候,表示没有被线索化 


//全局变量,pre指向当前访问结点的前驱 
ThreadNode *pre = NULL; 
//线索二叉树结点
typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild,*rchild;
	int ltag,rtag;
}ThreadNode,*ThreadTree; 
//中序遍历二叉树,一边遍历一边线索化
void InThread(ThreadTree T){
	if(T!=NULL){
		InThread(T->lchild);  //中序遍历左子树 
		visit(T);             //访问根结点 
		InThread(T->rchild);  //中序遍历右子树 
	}
} 
void visit(ThreadNode *q) {
	if(q->lnext == NULL){ //左子树为空,建立前驱线索 
		q->lchild = pre;
		q->ltag = 1;
	}
	if(pre != NULL && pre->rchild == NULL){
		pre->rchild = q;     //建立前驱结点后继线索 
		pre->rtag = 1;
	}
	pre = q;
}
//中序线索化二叉树
void  CreateInThread(ThreadTree T){
	pre = NULL;
	if(T!=NULL){      //非空二叉树才能线索化 
	    InThread(T);  //中序线索化二叉树 
	    if(pre->rchild==NULL)
	       pre->rtag = 1;	//处理遍历的最后一个结点 
	} 
} 

先序线索化代码

//全局变量,pre指向当前访问结点的前驱 
ThreadNode *pre = NULL; 
//线索二叉树结点
typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild,*rchild;
	int ltag,rtag;
}ThreadNode,*ThreadTree; 
//先序遍历二叉树
void InThread(ThreadTree T){
	if(T!=NULL){
		visit(T);
		if(t->ltag == 0)
		  preThread(T->lchild);
		PreThread(T->rchild); 
	}
} 
void visit(ThreadNode*q) {
	if(q->lnext == NULL){ //左子树为空,建立前驱线索 
		q->lchild = pre;
		q->ltag = 1;
	}
	if(pre != NULL && pre->rchild == NULL){
		pre->rchild = q;     //建立前驱结点后继线索 
		pre->rtag = 1;
	}
	pre = q;
}

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

后序线索二叉树代码

//全局变量,pre指向当前访问结点的前驱 
ThreadNode *pre = NULL; 
//线索二叉树结点
typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild,*rchild;
	int ltag,rtag;
}ThreadNode,*ThreadTree; 
//后序遍历二叉树,一边遍历一边线索化
void InThread(ThreadTree T){
	if(T!=NULL){
		InThread(T->lchild);  //后序遍历左子树 
		InThread(T->rchild);  //后序遍历右子树 
		visit(T); 
	}
} 
void visit(ThreadNode *q) {
	if(q->lnext == NULL){ //左子树为空,建立前驱线索 
		q->lchild = pre;
		q->ltag = 1;
	}
	if(pre != NULL && pre->rchild == NULL){
		pre->rchild = q;     //建立前驱结点后继线索 
		pre->rtag = 1;
	}
	pre = q;
}
//中序线索化二叉树
void  CreateInThread(ThreadTree T){
	pre = NULL;
	if(T!=NULL){      //非空二叉树才能线索化 
	    InThread(T);  //中序线索化二叉树 
	    if(pre->rchild==NULL)
	       pre->rtag = 1;	//处理遍历的最后一个结点 
	} 
} 





【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。