线索二叉树
【摘要】 线索二叉树概念——普通二叉树缺点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）