线索化二叉树的实现(思路分析) [数据结构与算法]
admin
2024-04-03 05:18:20
0次

线索化二叉树的实现(思路分析)

线索二叉树: Threaded BinaryTree

我们先来看一个问题:(通过这个问题我们来引入我们将要进行讲解的线索化二叉树):

问题: 将数列{1,3,6,8,10,14}构成一颗二叉树(如下图)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FDAl4vk0-1667387750530)(E:\非凡英才\数据结构(java)]\数据结构图解\线索化二叉树(问题引入).png)

问题分析:

  1. 当我们对上面的二叉树进行中序遍历的时候,数列为{8,3,10,1,6,14}
  2. 但是6,8,10,14这几个结点的左右指针并没有完全的利用上(这四个结点都有指针是空缺的,也就是这几个结点都有左右指针指向null的情况)
  3. 如果我们希望充分的利用各个节点的左右指针,让各个节点可以指向自己前后的结点,这个时候要如何做? --> 这个时候就要使用到我们的线索化二叉树

线索化二叉树的基本介绍:

  1. n个结点的二叉链表(二叉树)中有n+1个空指针域,利用二叉链表中的空指针域存放指向结点在某种遍历次序之下的前序和后继结点的指针(这种附加的指针就称之为: 线索)
    • 为什么n个结点的二叉树中就会有n+1个空指针域?
    • 公式2n - (n - 1) :
      • 那么公式中的2n是什么? —> 这里公式中的2n就是我们这里n个结点的二叉树中总共有多少个指针域,每个结点都有两个指针域,所以一共有n个结点那么自然就是一共有2n个指针域
      • 那么公式中的n-1又是什么? --> 这里公式中的n- 1其实就是含有n个结点的二叉树中被使用的指针域的个数, 我们每两个结点之间就需要使用某个结点的某一个指针域进行一个连接, 这个时候有n个结点,那么自然就是需要n- 1个指针域进行连接了
      • 所以最终这个公式的含义其实就是: 总指针域个数 - 已经使用的指针域的个数 =空指针域的个数
  2. 这种加了线索的二叉链表称之为: 线索链表,相应的二叉树称之为线索二叉树(Threaded BinaryTree),根据线索的性质的不同线索二叉树可以分为: 前序线索二叉树 , 中序线索二叉树, 后序线索二叉树
  3. 一个节点的前一个节点我们就称之为当前节点的前驱结点
    • 但是要注意 : 这里的前驱结点和后继结点都是相对于在某种遍历次序之下而说的, 不同的遍历方式之下的结点的相对位置不同
  4. 一个节点的后一个节点我们就称之为当前节点的后继结点

这里我们给出一个中序线索化二叉树的实例图解:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wQ5vTdiI-1667387750531)(E:\非凡英才\数据结构(java)]\数据结构图解\二叉树中序线索化实例.png)

思路分析:

我们以中序线索化二叉树为例

  1. 首先我们要知道我们要完成当前节点连接到对应的前驱和后继,这个时候我们肯定是要使用两个指针来完成( 这里我们使用一个node和一个pre)

    • 我们使用node开始的时候指向我们的第一个遍历到的结点,让pre开始的时候指向null
  2. 我们先向左遍历二叉树

  3. 如果node此时的左指针为null,此时就将node的左指针指向前驱pre, 如果pre右指针为null,此时就将pre指向的结点的右指针指向后继node

    • 这里由一个难点: 由于我们只是使用了两个指针来连接我们的当前节点, 前驱 , 后继,这个时候如果是连接前驱和当前节点的时候我们的pre就是指向前驱节点的, node是指向当前节点的, 但是如果是连接当前节点和后继的时候我们的pre就是指向当前节点的 ,node是指向后继结点的
      • 也就时使用两个指针要完成两个位置的连接要通过两次连接才可以,两个指针一次只可以连接了两个位置,但是我们这个时候是三个位置的连接,需要两次连接
  4. 向右递归右子树

当线索化二叉树之后,二叉树结点属性left 和 right就有了两种状态:

  1. left

    ①指向的是左子树或者左子节点

    ②指向的是前驱结点

  2. right

    ①指向的是右子树或者右子节点

    ②指向的是后继结点

所以我们要给结点类设置两个属性: leftType和rightType,用这两个属性标记我们的结点的left和rihgt是指向子树(或者子节点)还是指向了前驱(或者后继)结点

补充:

(以中序为例:)其实我们可以发现: 中序线索化二叉树也罢,中序查找也罢,或者是中序的什么操作也罢,都是在中序遍历的基础上进行一些二外的操作, 所以我们掌握了遍历的操作只会我们就掌握了对应的很多操作的写法

补充二:

(以中序为例: )其实中序线索化二叉树就是将对应的有空指针域的节点的左空指针域指向当前节点中序遍历下的前驱结点, 将对应的有空指针域的结点的右空指针域指向此节点中序遍历下的后继结点

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...