二叉树 —— 中序遍历结点的后继

时间:2021-12-26 10:12:00

想要获取中序遍历时某一节点的直接后继,

  • 首先在数据结构上,结点必须维护指向父节点的指针(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;
}