本文介绍: 当访问到某个节点时先看是否目标节点一致,一致就保存final指针中,不一致就更新当前节点赋值pre指针然后依次访问一个节点。

线索二叉树概念

在这里插入图片描述
找到某个节点得按照遍历得到的序列开始遍历才能遍历全部节点,非常繁琐
在这里插入图片描述

中序线索二叉树

在这里插入图片描述

线索二叉树存储结构

在这里插入图片描述

先序线索二叉树

在这里插入图片描述

后序线索二叉树

在这里插入图片描述

三种线索二叉树的对比

对应前驱后后继判断标准不同
在这里插入图片描述

小结

在这里插入图片描述

二叉树的线索化

在这里插入图片描述

用土办法找中序前驱

访问到某个节点时先看是否目标节点一致,一致就保存final指针中,不一致就更新当前节点赋值pre指针然后依次访问一个节点

在这里插入图片描述

中序线索化

判断前驱的右孩子当前节点的左孩子,二者符合条件连接然后更新前驱节点位当前节点
在这里插入图片描述
在这里插入图片描述

王道教材版

pre参数引用类型,这样才能做到修改变量的值
在这里插入图片描述

先序线索化

此时访问第三个节点后还需遍历左子树,但左孩子已经在visit中被更新第二个节点,这样又会开始遍历第二个节点,从而陷入反复循环
在这里插入图片描述

多了个判断左孩子

在这里插入图片描述

王道教材版

在这里插入图片描述

后序线索化

不会出现访问节点后再去遍历节点的左孩子
在这里插入图片描述

王道教材版

在这里插入图片描述

小结

在这里插入图片描述

在线二叉树中找前驱后继

中序线索二叉树找中序后继

在这里插入图片描述

中序线索二叉树找中序前驱

在这里插入图片描述

先序线索二叉树找先序后继

在这里插入图片描述

先序线索二叉树找先序前驱

因为节点的左右孩子都只可能是后继,不用不能通过左右孩子来找前驱。此时需要加入一个父节点的元素或从头遍历
三种情况中优先右走,没有子树则左走
在这里插入图片描述

后序线索二叉树找后序前驱

在这里插入图片描述

后序线索二叉树找后序后继

左右孩子只可能是前驱不可能是后继,所以得加个父节点元素或从头遍历
在这里插入图片描述
三种情况中优先左走,没有子树则右走

小结

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

原文地址:https://blog.csdn.net/llovewuzhengzi/article/details/134761763

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_37718.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注