考试资讯

咨询热线8:00-24:00 400-0999-680

首页 考试资讯考研专业课 2023计算机考研408数据结构知识:线索二叉树

2023计算机考研408数据结构知识:线索二叉树

时间:2021-11-23 14:04:33 编辑:leichenchen

      计算机考研专业课,很多学校以408为主!接下来,小编为帮助备考2023计算机考研408的学子们,在头脑中有一个专业课思维框架,特意精心为大家整理出-计算机考研408数据结构知识:线索二叉树,供考生参考。

2023计算机考研408数据结构知识:线索二叉树

  2023计算机考研408数据结构知识:线索二叉树

一、基本概念

目的: 加快查找结点前驱和后继的速度

规定:无左子树,令lchild指向前驱结点;无右子树,令rchild指向后继结点;增加两个标志域标明当前指针指的是前驱(1)还是左孩子(0)

线索:指向前驱和后继的指针

线索化: 对二叉树以某种次序遍历使其成为线索二叉树的过程

二、构造

1.线索化的实质

遍历一次二叉树,检查结点左右指针域是否为空。为空,改为指向前驱和后继的线索;

中序遍历序列中: 第一个结点为较左侧结点。最后一个结点为较右侧结点

前驱结点:左指针为线索,指向结点为前驱结点;左指针为左孩子,其左子树的较右侧结点为前驱结点

后继结点:右指针为线索,指向结点为后继结点;右指针为右孩子,其右子树的较左侧结点为后继结点

2.中序遍历线索化实现

3.有时在线索链表也添加一个头结点,构成双向线索链表:lchild指向根结点,rchild指向中序遍历最后一个结点,中序遍历第一个结点lchild和最后一个结点rchild指向头结点

三、遍历

利用线索二叉树可以实现二叉树遍历的非递归算法:中序下第一个结点Firstnode(较左侧结点),中序下的后继结点Nextnode

      综上是“2023计算机考研408数据结构知识:线索二叉树”,希望对计算机考研者们有所帮助!世界上唯一可以不劳而获的就是贫穷,唯一可以无中生有的是梦想。没有哪件事,不动手就可以实现。世界虽然残酷,但只要你愿意走,总会有路;看不到美好,是因为你没有坚持走下去。人生贵在行动,迟疑不决时,不妨先迈出小小一步。前进不必遗憾,若是美好,叫做精彩;若是糟糕,叫做经历!加油!

推荐阅读:

2023计算机考研408数据结构知识点总结

扫一扫

进考研专属交流群 获取更多考研干货资料

优先参加最新福利活动

我要吐槽

    • 文都考研课代表

    研友互动

    199管理类联考
      微信交流群

    396经济类联考
      微信交流群