|
问题描述：在二叉树中，一个节点的后续是在中序遍历过程中，在它之后访问的下一个节点，如果某节点是中序遍历的最后一个节点，那么它的后续为 NULL。
在 BST 中，给定节点的后续节点就是大于该节点的最小结点，这个性质对于查找比某元素大的下一个元素时非常有用。
如上图，8 的后续是 10，10 的后续是 12，14 的后续是 20。
现给定一个节点，请设计算法查找中序遍历中，该节点的后续节点。
解法一：使用双亲指针
这种解法需要每个节点都有指向双亲的指针，算法可分成两种情况来处理：
（1）如果给定节点的右子树不为空，则其后续是右子树中最小的那个节点；
（2）如果右子树为空，则其后续必是某个祖先节点，我们用双亲指针向上遍历，直到发现某节点是其双亲的左孩子，该节点就是所求的后续节点。
这种算法的复杂度为 O(h)，h 为树的高度。
在下面的算法实现中，inOrderSuccessor() 函数是查找给定节点后续的关键函数。
C 实现
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to r
| 
转播
