线索二叉树思维导图
线索二叉树介绍
树图思维导图提供 线索二叉树 在线思维导图免费制作，点击“编辑”按钮，可对 线索二叉树 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：0190fc22decf3976c43da019a93eff7c
思维导图大纲
线索二叉树思维导图模板大纲
作用
方便从一个指定节点出发找其前驱与后继，方便遍历
三种线索二叉树
中序线索二叉树
前序线索二叉树
后序线索二叉树
概念
线索
指向前驱/后继的指针
中序前驱/中序后继：按中序遍历的前驱/后继
后序、前序同理
存储结构
在普通二叉树基础上新增两个标志位ltag 和 rtag
ltag == 1表示lchild指向前驱，==0表示指向左孩子
rtag == 1表示rchild指向前驱，==0表示指向右孩子
n+1个空链域连上自己的前（中）（后）序前驱/后继
画线索二叉树（例后序）
具体型
写出后序遍历，当前结点前一个即为前驱，后一个为后继
只有有空指针的结点才可以这么判断
例如
抽象型
后序遍历：左右根
如果当前结点为根（有孩子），则前驱为右（若存在）孩子 or 左（右孩子不存在）孩子
若当前结点有父节点（当前结点为右），后继为父节点
若当前结点有父节点（当前结点为左），后继为右兄弟中第一个被访问的，展开右兄弟，即右兄弟一直往左走，到头再往右走，再一直往左走，以此类推直到走到叶子
二叉树的线索化
核心
遍历算法的改造，当访问一个有空孩子的结点时，连接该节点与其前驱
用pre指向前驱结点
以先序线索化为例
注意点
先序线索化较特殊，必须ltag == 0才可以线索化，否则将无限循环
因为你是先visit的，而visit有可能会修改lchild指针！
中序后序不需要特殊处理，其余基本一模一样，就改一下遍历顺序
最后要处理一下遍历的最后一个结点
找前驱/后继，当ltag or rtag == 0
思想：遍历法，如上画线索二叉树抽象型的思想
如图
注意点
先序线索二叉树找前驱 and 后序线索二叉树找后继必须得知道父节点
正是由于后续线索二叉树找不到后继结点，所以遍历后序线索二叉树需要栈的支持
所谓右兄弟子树第一个被后序遍历的结点
见上述画线索二叉树抽象型的解释
所谓左兄弟子树最后一个被先序遍历的结点
同理
沪公网安备 31011502019485号
上海工商