数据结构之树(2)
摘要:本篇主要讲线索二叉树,灰常重要!
一、线索二叉树
不知道树的根节点时,给出指定结点,无法直接找到其前驱,除非用快慢指针进行记录。
因此,引出线索二叉树记录前驱后继。
n个结点的二叉树,有n+1个空链域,可用来记录前驱、后继的信息->线索化
前驱线索:左孩子指针充当 后继线索:右孩子指针充当
struct TreeNode{
int data;
struct TreeNode*lchild, *rchild;
int ltag ,rtag;//左右线索标志,tag=0表示指针指向孩子,tag=1表示指向线索
}
二、二叉树线索化
中序
void InThread(TreeNode* root)
{
if(root)
{
InThread(root->lchild);
visit(root);
InThread(root->rchild);
}
}
void visit(TreeNode* root)
{
if(root->lchild == nullptr)
{ root->lchild=pre; root->ltag=1;}
if(pre!=nullptr && pre->rchild == nullptr)
{ pre->rchild=root; pre->rtag=1;}
pre=root;
}
//全局变量pre,指向当前访问结点的前驱
TreeNode* pre =nullptr;
//中序线索化二叉树
void CreateInThread(TreeNode* root)
{
pre=nullptr;
if(root)
{
InThread(root);
if(pre->rchild == nullptr)pre->rtag=1;
}
}
先序:注意当Itag==0时,才能对左子树先序线索化
原因:当判断左子树为空时,左子树的左指针指向前驱结点,又因为接下来访问的结点是当前结点的左孩子(根左右),而左指针此时不为空,导致出错。
void PreThread(TreeNode* root){
if(root){
visit(root);//先处理根节点
if (root->ltag ==0 )PreThread(root->lchild);
PreThread(root->rchild);
}
}
三、找前驱后继
1、找到指定结点的中序后继
若p->rtag==1,则next=p->rchild
若p->rtag==0,next为p的右子树中最左下结点
画图就明白
//找到以p为根的子树中,第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *P){
//循环找到最左下结点
while(p->ltag==0)p=p->lchild;
return p;
}
//在中序线索二叉树中找到结点p的后继结点
ThreadNode *NextNode(ThreadNode *p){
//右子树最左下结点
if(p->rtag==0)return Firstnode(p->rchild);
else return p->rchild;//rtag==1直接返回后继线索
}
对中序线索二叉树进行中序遍历(利用线索实现的非递归算法)(空间复杂度O(1))
void Inorder(ThreadNode T){
for(ThreadNode *p=FirstNode(T);p!=NULL;p=Nextnode(p))//p=Nextnode(p)很方便地找到后继
visit(p);
}
2、找到指定结点的中序前驱
若p->ltag==1 next为p->lchild
若p->ltag==0 左子树最右边的结点
//找到以p为根的子树中,最后一个被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p){
//循环找到最右下结点(不一定时叶节点)
while(p->rtag==0)p=p->rchild;
return p;
}
//在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){
//左子树最右下结点
if(p->ltag==0) return Lastnode(p->lchild);
else return p->lchild;//ltag==1直接返回前驱线索
}
对中序线索二叉树进行逆向中序遍历
void RevInorder(ThreadNode *T){
for (ThreadNode *p=Lastnode(T);p!=NULL;p=Prenode(p))
visit(p);
}
附:
先序后继
p->rtag==0,则next为左孩子(左子树第一个被访问的结点)
根 左 右
根(根 左 右) 右
p->rtag==1(没有左孩子),则next=p->rchild
先序前驱
改用三叉链表可以找到父结点
1、如果能找到p的父结点且p是左孩子,p的父结点即为前驱
2、如果能找到p的父结点,且p是右孩子,其左兄弟为空,p的父结点为前驱
3、如果能找到p的父结点,且P是右孩子,其左兄弟非空,p的前驱为做兄弟子树中最后一个被先序遍历的结点
4、如果p是根节点,则p没有先序前驱
原文地址:https://blog.csdn.net/2301_76246515/article/details/142620419
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!