遍历线索二叉树

（3）在后线索二叉树中，找到指定节点* p

的后继节点

在后线索线索二叉树中，找到指定节点* p的后继前任节点的特定规则是:

①如果* p的左子树为空，则p-> lchild是前导线索，指示其前任结点.

[示例]在下图所示的后序线索二叉树中线索二叉树后序遍历，H的后序前任是B，F的后序前任是C.

②如果* p的左子树不为空，则p-> lchild并非前任线索. 由于在后序遍历期间遍历其左右子树后才访问根，因此* p的后继前驱必须是两个子树中的最后一个遍历节点.

* p的右子树不为空时，* p的右子级必须是其前任

[示例]在上面显示的后序线索二叉树中，A的后序前任是E;

当* p没有右子树时，* p的后序必须是其左子级

[示例]在上面显示的后序线索二叉树中，E的后序前任是F

（4）在后序线索二叉树中，搜索指定节点* p

的后序后继节点.

特定规则:

①如果* p是根，则* p是在二叉树的后遍历过程中访问的最后一个节点. * p的后继者为空

②如果* p是其父母的正确子代，则* p的后续节点是他的父节点

[示例]在上图所示的后线索的二叉树中，E的后继者是A.

③如果* p是其父母的左子，但* P没有右兄弟，则* p的后继节点是他的父节点

[示例]在上图所示的后线索的二叉树中，F的后继者为E.

④如果* p是其父母的左子，但* p有一个右兄弟，则* p的后继者是其父母的右子树中的第一个遍历节点，即“最左边的最左叶节点” “在子树中

[示例]在上图所示的后线索的二叉树中，B的后继继承者是父A的右子树中最左下的叶子节点H

注意:

F是子树中的“左下”节点，但不是叶子.

从上面的讨论中我们可以看到线索二叉树后序遍历，在后订单线索树中，您只能从* p找到后订单的前任节点；仅当* p的右子代时，才查找* p的后继后继节点. 当树为空时，可以直接从* p的右线索p-> rchild获得. 否则，您必须知道* p的父节点才能找到其后继节点. 因此，如果线索二叉树中的节点没有指向其父节点的指针，则可能有必要从根执行遍历以查找节点* P的后继继承者. 因此，提示对于找到指定节点的后继者不是很有帮助.

（5）在预示线索二叉树中，找到指定节点* p

的前任和后继节点

【请参阅练习】

（6）在预想线索二叉树中，找到指定节点* p

的前任节点

[请参阅参考书]

在预示线索的二叉树中，找到* p的某个前任和后继也是非常简单的，并且只能从* p中找到；但是要找到其前身，您还必须知道* p的父节点. 如果树中未设置父指针，则还需要从根开始进行遍历才能找到节点* p的前任.

2. 遍历线索二叉树

只要线索从该顺序的起始节点开始发展，就以一定顺序遍历线索的二叉树，然后反复查找该顺序的节点的后继节点，直到到达终端节点为止.

遍历有序线索二叉树算法:

void TraverseInorderThrTree（BinThrTree p）

{//遍历订单线索的二叉树

if（p）{//树不为空

while（p-> ltag == Link）

p = p-> lchild; //从根向下查找最左边的节点，它是中间序列的起始节点

做{

printf（“％c”，p-> data）; //访问节点

p = InorderSuccessor（p）; //找到* p

的中阶后继

} while（p）

} // endif

} // TraverseInorderThrTree

分析:

①中间序列终端节点的右线索为空，因此do语句的终止条件为p == NULL.

②该算法的时间复杂度为O（n）. 由于它是非递归算法，因此常数因子小于递归遍历算法. 因此，如果要频繁遍历二叉树，或以指定顺序查找节点的前任和后继，则应使用线索链接列表作为存储结构.

③上面介绍的线索二叉树是完整的线索树（即，将建立左右线索）. 在许多应用中，只需建立左右引线之一即可.

④如果将头节点添加到线程列表中，则使头节点的左指针指向其遍历序列的根节点，而将右指针指向其遍历序列的起点或终点更为方便.

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