0001 template <typename T> BinNodePosi<T> BinNode<T>::succ() { //定位节点v的直接后继 0002 BinNodePosi<T> s = this; //记录后继的临时变量 0003 if ( rc ) { //若有右孩子,则直接后继必在右子树中,具体地就是 0004 s = rc; //右子树中 0005 while ( HasLChild( *s ) ) s = s->lc; //最靠左(最小)的节点 0006 } else { //否则,直接后继应是“将当前节点包含于其左子树中的最低祖先”,具体地就是 0007 while ( IsRChild( *s ) ) s = s->parent; //逆向地沿右向分支,不断朝左上方移动 0008 s = s->parent; //最后再朝右上方移动一步,即抵达直接后继(如果存在) 0009 } 0010 return s; 0011 }