江
江小南
V1
2023/02/27阅读:14主题:萌绿
【数据结构】线索二叉树
1. 思考

一个二叉树中序遍历序列中,如何找到指定结点p的前驱和后继?
思路:从根结点除法,重新进行依次中序遍历,指针q记录当前访问的结点,指针pre记录上一个被访问的结点。当q==p时,pre为前驱。当pre==p时,q为后继。
缺点:找前驱、后继很不方便;遍历操作必须从根开始。
2. 中序线索二叉树

// 二叉树的结点(链式存储)
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
我们将二叉树线索化,得到如下链表:
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag; // 左、右线索标志
}ThreadNode,*ThreadTree;


使用同样的方法可以得到先序线索二叉树和后序线索二叉树。
3. 中序线索化

// 线索二叉树结点
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag; // 左、右线索标志
}ThreadNode,*ThreadTree;
// 全局变量pre,指向当前访问结点的前驱
ThreadNode *pre=NULL;
// 中序线索化二叉树T
void CreatInThread(ThreadTree T){
pre=NULL; // pre初始化为NULL
if(T!=NULL){ // 非空二叉树才线索化
InThread(T); // 中序线索化二叉树
if(pre->rchild==NULL){
pre->rtag=1; // 处理遍历的最后一个结点
}
}
}
// 中序遍历二叉树,一边遍历一边线索化
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->tag=1;
}
if(pre!=NULL&&pre->rchild==NULL){
pre->rchild=q; // 建立前驱结点的后继线索
pre->rtag=1;
}
pre=q;
}
4. 先序线索化
// 全局变量pre,指向当前访问结点的前驱
ThreadNode *pre=NULL;
// 先序线索化二叉树T
void CreatThread(ThreadTree T){
pre=NULL; // pre初始为NULL
if(T!=NULL){ // 非空二叉树才能线索化
PreThread(T); // 先序线索化二叉树
if(pre->rchild==NULL){
pre->rtag=1; // 处理遍历的最后一个结点
}
}
}
// 先序遍历二叉树,一边遍历一边线索化
void PreThread(ThreadTree T){
if(T!=NULL){
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->lchild=q; // 建立前驱结点的后继线索
pre->rtag=1;
}
pre=q;
}
5. 后序线索化
// 全局变量pre,指向当前访问结点的前驱
ThreadNode *pre=NULL;
// 后序线索化二叉树T
void CreatPostThread(ThreadTree T){
pre=NULL; // pre初始化为NULL
if(T!=NULL){ // 非空二叉树才能线索化
PostThread(T); // 后序线索化二叉树
if(pre->rchild==NULL){
pre->rtag=1; // 处理遍历的最后一个结点
}
}
}
// 后序遍历二叉树,一边遍历一边线索化
void PostThread(ThreadTree T){
if(T!=NULL){
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;
}
作者介绍
江
江小南
V1