线索二叉树 —C语言王道

目录

线索二叉树概念

——普通二叉树缺点

——中序线索二叉树

——先序线索二叉树

——后序线索二叉树 

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

二叉树的线索化

普通方法代码

中序线索化代码

先序线索化代码

后序线索二叉树代码

---

线索二叉树概念

——普通二叉树缺点

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

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

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

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

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

——中序线索二叉树

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

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

图示说明 

 代码如下

代码语言：javascript复制

//二叉树的结点(链式存储) 
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，表示指针是指向“线索”

——先序线索二叉树

和上同理

——后序线索二叉树 

和上同理

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

---

二叉树的线索化

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

普通方法代码

代码语言：javascript复制

//辅助全局变量，用于查找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 的时候,表示没有被线索化 

代码语言：javascript复制

//全局变量，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;	//处理遍历的最后一个结点 
	} 
} 

先序线索化代码

代码语言：javascript复制

//全局变量，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;	//处理遍历的最后一个结点 
	} 
} 

后序线索二叉树代码

代码语言：javascript复制

//全局变量，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;	//处理遍历的最后一个结点 
	} 
} 

二叉树 编程算法

0 人点赞