线索⼆叉树（中序、先序、后续的前驱和后继）
线索⼆叉树
线索⼆叉树基本概念
遍历⼆叉树可以按⼀定规则得到⼀个线性序列（先序序列、中序序列、后序序列）。这些序列除头尾之外，都有且仅有⼀个前驱和⼀个后继。
当遍历⼆叉树时，只能得到结点的左右孩⼦信息，⽽不能直接得到结点的前驱和后继信息，只能从根节点遍历得到，由此引⼊线索⼆叉树。
线索⼆叉树就是为了加快查结点前驱和后继的速度。
规定：
若结点有左孩⼦，则 lchild 域指向其左孩⼦，否则， lchild 域指向其前驱；
若结点有右孩⼦，则 rchild 域指向其右孩⼦，否则， rchild 域指向其后继；
为了避免混淆，在原来的结点基础上增加两个表⽰域：
lchild ltag data rchild rtag
ltag = 0：lchild 域指向结点左孩⼦
ltag = 1：lchild 域指向结点前驱
rtag = 0：rchild 域指向结点右孩⼦
rtag = 1：rchild 域指向结点后继
以这种结点结构构成的⼆叉链表作为⼆叉树的存储结构，叫做线索链表
其中指向结点前驱和后继的指针，叫做线索
加上线索的⼆叉树，叫做线索⼆叉树
对⼆叉树以某种次序遍历使其变为线索⼆叉树的过程，叫做线索化，线索化的过程就是在遍历的过程中修改空指针的过程。
构造线索⼆叉树
中序线索⼆叉树
中序线索⼆叉树，就是⾮空⼆叉树进⾏中序线索化之后所得到的。
树中所有叶⼦结点的右链是线索，则右链直接指向了结点的后继；b结点的后继为 * 。
⾮叶⼦结点右链是指针，⽆法得到后继信息。
根据中序遍历的规律知：
结点的后继：遍历其右⼦树时访问的第⼀个结点，即右⼦树中最左下的结点；
结点的前驱：若没有左孩⼦其左标志为 1 ，则左链为线索，指向其前驱 ；否则，遍历左⼦树时最后⼀个访问的结点（左⼦树中最右下的结点）位其前驱。
先序线索⼆叉树
黄⾊结点有左孩⼦，⽆法记录其前驱结点，则不到其前驱结点。
根据先序遍历的规律知：
结点的后继：若有左孩⼦，则左孩⼦就是其后继，若没有左孩⼦但有右孩⼦，则右孩⼦就是其后继，若是叶⼦结点右标志为1，则右链为线索，指向其后继；
结点的前驱：若没有左孩⼦其左标志为 1 ，则左链为线索，指向其前驱 ；否则，有左孩⼦，⽆法存储左链，不能直接到其前驱结点。
后序线索⼆叉树
黄⾊结点有左孩⼦，⽆法记录其前驱结点，则不到其前驱结点。
根据后序遍历的规律知：
结点的后继：
1、若结点是⼆叉树的根，则后继为空；
2、若结点是其双亲的右孩⼦，或是其双亲的左孩⼦且其双亲没有右⼦树，则其后继就是其双亲结点；
3、若结点是其双亲的左孩⼦，且其双亲有右⼦树，则其后继为双亲的右⼦树上按后序遍历列出的第⼀个结点
结点的前驱：若没有左孩⼦其左标志为 1 ，则左链为线索，指向其前驱 ；否则，有左孩⼦，⽆法存储左链，不能直接到其前驱结点。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论