数据结构是计算机考研的重要内容之一，数据结构的核心考点较多，复习较困难。为了帮助大家更好的了解和复习备考，小编为大家整理了2024计算机考研数据结构高频考点：线索二叉树的详细内容，一起来看看吧。
2024计算机考研数据结构高频考点：线索二叉树
　　一、含义
　　试做如下规定：若结点有左子树，则其Ichild域指示其左孩子，否则令Ichild域指示其前驱;若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。为了避免混淆，尚需改变结点结构，增加两个标志域。以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称之为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。
　　二、构造
　　1.线索化的实质
　　对二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前节点的左右指针域是否为空，若为空，将它们改为指向前驱结点或指向后继结点的线索。
　　线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继信息只有在遍历该二叉树时才能得到，所以，线索化的过程就是在遍历的过程中修改空指针的过程。
　　中序遍历序列中:第一个结点为较左侧结点。最后一个结点为较右侧结点。
　　前驱结点：左指针为线索,指向结点为前驱结点;左指针为左孩子，其左子树的较右侧结点为前驱结点。
　　后继结点：右指针为线索,指向结点为后继结点;右指针为右孩子，其右子树的较左侧结点为后继结点。
　　2.中序遍历线索化实现
　　3.有时在线索链表也添加一个头结点，构成双向线索链表：lchild指向根结点,rchild指向中序遍历最后一个结点，中序遍历第一个结点lchild和最后一个结点rchild指向头结点。
　　以上内容整理于网络，仅供参考。
　　以上就是学姐为大家整理的【2024计算机考研数据结构高频考点：线索二叉树】的全部内容！想了解更多关于考研的相关信息，请关注高顿考研官网查询，祝大家考研成功。另外，小编为2024考研的小伙伴们准备了丰富的学习资料，点击下方蓝色小卡片即可获取哦~
相关阅读
延伸阅读



展开全文