想要获取中序遍历时某一节点的直接后继,
- 首先在数据结构上,结点必须维护指向父节点的指针(parent),
- 因为当前结点的后继有可能是其父节点,
- 如果其本身没有右孩子;
- 或者本身是左孩子结点;
- 因为当前结点的后继有可能是其父节点,
- 注意对当前结点进行分类讨论
- 是否有右孩子
- 有:递归遍历右孩子的左孩子,直到没有左孩子为止;
- 无:当前结点是否为右孩子,
- 是:
- 否:返回其父结点;
- 是否有右孩子
template<typename T>
BinNodePosi(T) BinNode<T>::succ(){
BinNodePosi(T) s = this;
if (rChild) {
s = rChild;
while (HasLChild(s)) s = s->lChild;
} else{
while (IsRChild(s)) s = s->parent;
s = s->parent;
}
return s;
}