后序线索二叉树中求后序后继

在二叉树的后序线索化算法中，每个节点的后继是指在后序遍历中，该节点的后继节点，也是该节点在整个二叉树中的后继节点，未线索化的二叉树需要通过遍历来查找后继节点，而线索化过的二叉树可以通过右线索来直接寻找后继节点，因此，求后序后继是一个比较常见的问题。

在本文中，我们将从以下几个角度分析如何在后序线索二叉树中求后继：

1.后序线索二叉树的定义及其应用

2.求后序后继的常规方法

3.利用后序线索二叉树求后继的实现方法

一、后序线索二叉树的定义及其应用

后序线索二叉树是指在二叉树中，每个节点除了左右指针外还有两个额外的标记指针：前驱指针和后继指针。这两个指针将整个二叉树串联起来，形成后序线索二叉树，它的应用主要在于优化二叉树的遍历算法。

二、求后序后继的常规方法

在未线索化的二叉树中，求后继节点需要遍历整个二叉树，在后序遍历中顺序寻找下一个节点，直到找到该节点的后继。这个算法时间复杂度为O(n)，当搜索的深度比较大时，该算法的效率会比较低。

三、利用后序线索二叉树求后继的实现方法

利用后序线索二叉树求后继的方法比较简单，只需要在后序遍历中寻找当前节点的右线索节点即可。具体实现方法如下：

1.如果该节点没有右儿子或者右儿子是指向自己的线索节点，则该节点的后继是右儿子节点

2.如果该节点有右儿子，并且右儿子不是指向自己的线索节点，则该节点的后继是从右儿子开始沿着左儿子链一直找到最后一个叶子节点

代码如下：

```

Node* GetPostOrderNext(Node* p)

{

if (p == NULL) return NULL;

if (p->rightTag == 1)

return p->right;

Node *q = p->right;

while (q->leftTag == 0 || q->rightTag == 0) {

if (q->leftTag == 0) {

q = q->left;

} else {

q = q->right;

}

}

return q;

}

```

这个算法的时间复杂度为O(1)，因此，可以大大提高求后继节点的效率。