[数据结构]线索二叉树

1. 介绍线索二叉树

二叉树的遍历本质上是线性化非线性结构的过程，因此每个节点（第一个节点和最后一个节点除外）在这些线性序列中只有一个直接的前驱体和直接的后继体. 但是后续线索二叉树，在二进制链表的存储结构中，只能找到一个节点的左子信息和右子信息，而不能以任何遍历顺序直接获得该节点的前任和后继信息. 该信息只能在动态遍历过程中获得. 因此，引入了线索二叉树来存储从动态过程中获得的信息.

2. 建立线索二叉树

为了以任何顺序保存节点的前任和后继信息，请考虑在每个节点中添加两个指针字段，以存储遍历过程中获得的前任和后继信息，从而为以后的访问带来方便. 但是，增加指针信息会减少存储空间的利用率后续线索二叉树，因此可以考虑使用其他方法.

如果N个节点的二进制树使用二进制链接列表作为存储结构，则链接列表中必须有N + 1个空指针字段，并且这些空指针字段可以完全用于存储前任和后继信息. 节点.

3. 参观线索二叉树

以中阶线索二叉树为例，让P指向该节点的某个节点. 查找p指向的节点的后继者:

（1）如果p-> rtag == 1，则p-> rchild指向其后继部分

（2）如果p-> rtag == 0，则p指向的节点的中阶后继者必须是在其右子树中进行中阶遍历时获得的第一个节点. 也就是说，从p指向的节点的右子树的根节点开始，向下看左子指针链，直到找到没有左子节点的节点. 该节点是p指向的节点的直接后继. 它也被称为p的右子树中的“最左侧”节点.

以中阶线索二叉树为例，让P指向的节点的某个节点. 找到p指向的节点的直接前驱方法:

（1）如果p-> ltag == 1，则p-> lchild指向其前驱节点

（2）如果p-> ltag == 0，则p指向的节点的中序前驱必须是其右子树中途遍历期间获得的最后一个节点. 也就是说，从p指向的节点的右子树的根节点开始，向下查看右子指针的链，直到找到没有右子节点的节点，该节点就是所指向节点的直接前体至第在p的右子树中，也称为“右下”节点.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-276305-1.html