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

(91) 2024-04-27 21:01:01

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

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

发表回复