014线索,考研之数据结构014_非线性表的线索二叉树

考研之数据结构014_非线性表的线索二叉树 一、二叉树概念1、线索二叉树的概念1.中序线索二叉树 2、线索二叉树存储结构3、三种线索二叉树二、二叉树的线索化1、土办法:1、中序线索化2、先序线索化3、后序线索化三、线索二叉树->找前驱/后继一.中序1、中序线索二叉树查找中序后继1.有线索(第二行代码)2.没有线索(第一行代码)3.中序遍历 2、中序线索二叉树查找中序前驱(pre)1.第二行代码有线索:2.第一行代码没有线索:3.逆向中序遍历二.先序3、先序线索二叉树查找先序后继1.右指针线索化(所以rtag=1)2.右指针没有被线索化 (所以rtag=0) 4、先序线索二叉树查找先序前驱1.左指针线索化(所以ltag=1)2.左指针没有线索化(所以ltag=0)(找不到前序遍历的前驱)三.后序5、后序线索二叉树查找先序前驱1.左指针线索化(所以ltag=1)2.左指针没有线索化(所以ltag=0) 6、后序线索二叉树查找后序后继1.右指针线索化(所以rtag=1)2.右指针没有线索化(所以rtag=0)(找不到后序遍历的后继)

一、二叉树概念

在这里插入图片描述

1、线索二叉树的概念

二叉树的先后中序遍历序列的弊端: 1.只能从根部开始遍历。不能从其中某一个结点开始遍历。 2.给出p结点,不能找到他的前驱。 找到p结点的前驱,我们可以这样做: 答案:对整棵二叉树在进行一次中序遍历,从根节点出发,用指针q记录当前访问的结点,指针pre记录上一个被访问的结点。当我们在访问结点时,会对结点进行visit(T)【访问结点操作】==q结点。 q指向第一个结点,pre指向的是空。让pre指向q指向的结点,q指向下一节点,而此时pre就是q结点的中序前驱。 循环上面 q指向后一个,Pre依次跟着往后移动,直到q和p指向的是同一节点。说明pre就是p所指向结点的前驱。 所以在找前驱、后继,遍历频繁操作,以上的操作不方便。所以提出了“线索二叉树” 在这里插入图片描述

1.中序线索二叉树

将二叉树进行改造: 对于有n结点的二叉树,有n+1个空链域!可以用来记录前驱、后继信息。用空链域指向各个结点的前驱和后继。 比如说: 1.某一节点没有左右孩子,可以让左孩子指向他的前驱,右孩子指向后继结点。 2.第一个访问的结点没有前驱,可以让他左孩子指向NULL。

虚线表示线索、实线是左右孩子的指针、黄色是前驱、紫色是后继 在这里插入图片描述

2、线索二叉树存储结构

在二叉树的结点增加两个标志位,来区分是孩子还是线索。 在这里插入图片描述 在这里插入图片描述

3、三种线索二叉树

在这里插入图片描述

二、二叉树的线索化

在这里插入图片描述

1、土办法:

在这里插入图片描述

在这里插入图片描述

1、中序线索化

在这里插入图片描述 左右线索标志左右设置为0。说明结点指针指向的是左右孩子。并没有线索化。

让pre指向为NULl。第一个结点没有前驱,那么设为NULL。 在这里插入图片描述 在这里插入图片描述

一、访问第一个结点,没有左孩子。那么将第一个指针的左孩子进行线索化,在visit函数进行完成。 1.判断左孩子为空,那么将左孩子指针指向前驱。(用Pre来表示前驱) 并且已知Pre初始化为NULL。 2.把ltag设为1,表示是线索。 3.将pre指针指向当前的结点。 pre=q;因为我们要开始访问下一结点了。 在这里插入图片描述 二、下一节点是G结点 1.左孩子位置是空的,那么将左指针线索化 指向pre(也就是说指向了上一结点。) 2.将ltag=1;说明左指针指向上一节点。 3.第二个语句,右孩子是非空,所以不执行

在这里插入图片描述 三、下一节点是B结点 1.左右孩子的位置是非空的,第一个语句不执行 2.那么到了第二个if语句,现在的Pre指向的是B的前驱的不为空。而pre的右孩子是空的。那么将pre指向的G,G的右孩子进行线索化,让他指向G的后继。也就是q当然的结点。pre-rchild=q 3.进行了线索化,那么将pre->rtag=1。说明G的右孩子指向后继。 4.并且将pre指向了下一节点q。 pre=q在这里插入图片描述 …循环上面的流程… 当我们循环到q指向最后一个结点,Pre指向q的前驱时,还是会将pre指向q结点。然后就不会在进行visit(访问根节点了)。 出现了问题:本来最后一个结点的右孩子是空的,应该进行线索化。 解决:而我们设置的Pre是全局变量,所以我们可以在其他函数 中,对Pre指针当前指向的结点,在进行处理,让他的有孩子指针指向null,同时将rtag=1。也就是说对最后一个结点进行处理。

…最后的代码: 在这里插入图片描述

2、先序线索化

在这里插入图片描述 为什么要判断左子树是不是左孩子? 当访问了D结点后,我们已经将D的左子树指向了B结点。根据先序,我们就要进行根->左->右。那么如果我们现在要访问左子树了,要么就会导致q结点会再次指向B。因为D的左子树指向上一节点。从而导致无限循环。 解决方案:在访问完根D,并且将根D的左子树指向前驱后,并设为ltag=1。 访问完根,现在要访问D的左子树,现在要进行判断是不是左孩子(t->ltag==0)如果是左孩子,才进行访问。而显然不是,因为我们上边的左孩子是空,并指向前驱结点。

在这里插入图片描述

3、后序线索化

和上面的代码是一样的,唯一区别就是,先处理左->右->根。 在后序线索化,不会出现“转圈问题”,原因在于,当我们在访问,一个结点q的时候,这个左右孩子肯定处理完了。所以不可能回头访问左右孩子了。

在这里插入图片描述

三、线索二叉树->找前驱/后继

在这里插入图片描述 在这里插入图片描述

【p->ltag=0,0 代表的是有孩孩子,1代表是已经被线索了】。

一.中序 1、中序线索二叉树查找中序后继

在这里插入图片描述

1.有线索(第二行代码)

1.当指定结点的右孩子指针,已经被线索化(p->rtag = =1,next=p->rchild),该节点右指针存放的就是后继。那么直接return p->rchild。 在这里插入图片描述

2.没有线索(第一行代码)

2.当指定结点的右孩子指针,没有被线索化(p->rtag==0)。那么中序顺序是:“左根右”。所以由于rtag=0,那就说明有右孩子。根据中序规则,右子树当中第一个被中序遍历的结点就是p的后继。 规则:p结点的右子树当中最左下角的这一节点,就是p的后继结点。 在代码中,如果p指针有右孩子,那么调用:“Firstnode函数”去找第一个遍历的结点。

第一:p只有一个右孩子,而且是一个叶子结点,那么也就是P的后继

第二:从指定的结点出发,如果下一层还有左孩子,那么就一直顺着左孩子的左孩子找下去,直到(ltag!=0)为止,(也就是这个结点没有左孩子了)。 按照中序规则来说,那么最左下角的这个结点,肯定是这棵树中第一个被中序遍历的结点。

如果要找到指定结点p的后继结点,如果右指针没有被线索化,就应该去找右子树当中,第一个被中序遍历的结点。(右子树中最左的结点。) 在这里插入图片描述

3.中序遍历

那么既然能找到任意结点的后继,那就可以利用函数【Inorder】对中序线索二叉树进行中序遍历。 实现方法: 传入树的根节点指针T,找到第一个被中序遍历的结点,也就是说一直找结点的左节点(最左下角的结点),代码条件是for(初始化p=循环找到最左下角的结点;p!=null;p=Nextnode§) 【初始化:p的初始化是树的第一个结点。中序那么就是最左下角的结点】 【判断:只要p不为空就一直找,直到树中所有的结点都找完】 【循环体:访问该节点】 【循环的改变:找中序后继】 在这里插入图片描述 在这里插入图片描述

2、中序线索二叉树查找中序前驱(pre)

在这里插入图片描述

1.第二行代码有线索:

左孩子已经被线索化(p->ltag=1),那么左指针,所指的结点就是他的前驱。

2.第一行代码没有线索:

左孩子没有被线索化(p->ltag=0),那么就说明肯定有左孩子的,按中序遍历规则“左根右”,那么p结点的前驱,肯定是左子树当中,按中序遍历最后一个被访问的结点。 规则:结点p,他的前驱,肯定是左子树当中,按中序遍历最后一个 被访问的结点。如果左子树只有一个结点,那么左子树就是他的前驱,那么如果有下一层的分级,按中序遍历,他的右孩子结点显然是最后被访问的结点。(如果有p结点有右孩子的话,那么pre=p的左子树最后下的结点就是前驱)

【Lastnode】函数:可以找到一棵树当中,按中序遍历最后一个被访问的结点。(从跟出发,最右下角的结点)。就是p结点的前驱 在这里插入图片描述

所以左指针没有被线索化,那么需要找打P结点的左子树,最后一个被中序遍历的结点。就是p结点的前驱 第二有线索: 如果本来就是线索的话,那么只需要返回左指针指向的结点。 在这里插入图片描述

3.逆向中序遍历

在这里插入图片描述

二.先序 3、先序线索二叉树查找先序后继

在这里插入图片描述

1.右指针线索化(所以rtag=1)

直接返回后继线索(p->rage=1,则next=p->rchild) 在这里插入图片描述

2.右指针没有被线索化 (所以rtag=0)

说明P结点肯定有右孩子。 1.假设有左孩子,按先序遍历“根左右”,p结点的后继结点肯定是左子树当中第一个被访问的结点。 若p有左孩子,则先序后继为左孩子。 在这里插入图片描述 2.没有左孩子,肯定有右孩子。按先序“根左右”。左子树为空,那么顺序就是“根右”,那么p结点的后继结点,肯定是右子树当中,第一个被先序遍历的结点。无论他的右孩子,是分支还是结点。肯定是右子树当中第一个被访问的-》也就是右孩子。先序(根左右-》根右) 若p没有左孩子,则先序后继为右孩子。

4、先序线索二叉树查找先序前驱 1.左指针线索化(所以ltag=1)

那么,直接返回p的左指针指向的结点。

2.左指针没有线索化(所以ltag=0)(找不到前序遍历的前驱)

说明p结点有左孩子,所以没有被线索化 根据先序遍历的规则“根左右”,p的左子树和右子树当中的所有的结点,只可能是p的后继,不可能是P的前驱。所以不可能在p 的左右孩子找到前驱。 而我们的线索二叉树,只有指向孩子的指针,不能往回找。所以找不到先序的前驱的。除非用土办法,从头开始先序遍历,记录上一个结点,从而找到p的前驱。 以下是:三叉索引链表 在这里插入图片描述

三.后序 5、后序线索二叉树查找先序前驱 1.左指针线索化(所以ltag=1)

在这里插入图片描述

那么,直接返回p的左指针指向的结点。(pre=p->lchild)

2.左指针没有线索化(所以ltag=0)

说明肯定有左孩子,不确定有没有右孩子。 1.假设有右孩子: 后序遍历“左右根”,p结点的后序前驱,一定是右子树中安后序最后访问的一个结点。 规定:若p有右孩子,则后序前驱是为右孩子 2.假设p结点没有右孩子: 按后序遍历,右子树为空,那么“左根”,p结点的前驱就是左子树当中按后序遍历最后一个被访问的结点。那么就是他的左孩子 规定:若p没有右孩子,则后续前驱就是左孩子。

6、后序线索二叉树查找后序后继 1.右指针线索化(所以rtag=1)

直接返回p指向的右指针,(p->rage=1,则next=p->rchild)

2.右指针没有线索化(所以rtag=0)(找不到后序遍历的后继)

说明肯定有右孩子。 根据后序遍历“左右根” 结点P的左子树,和右子树当中,所有的结点都有可能是结点P的前驱。不可能是后继。所以不到后序遍历的后继。 在这里插入图片描述

07钉钉教育版05美国科幻战争电影第三次世界大战中印最大的边贸口岸中国阿富汗边境口岸01心经第一讲033夏禾窦梅双飞求收藏求收藏求收藏TNABO数据古今中外观影人次过亿的电影都有哪些川崎636官方报价OkHttp源码解析0844章豪门狗血剧剧终赘婿出山李闲鱼00后舞狮追梦人07年改款手动三厢307遥控钥匙丢了0897昔日红颜神之战超越时空全角色去疤的药膏哪种比较好iphone7锁屏密码解破苹果7怎么强制破解密码arcsinx绝对值的图像arcsinx的定义域046tv直播下载011多多和少少