0001 //通过zig旋转调整,将BST子树x拉伸成最右侧通路 0002 template <typename T> void stretchByZig( BinNodePosi<T>& x ) { 0003 if ( !x ) return; 0004 BinNodePosi<T> r = x; while ( r->lc ) r = r->lc; //最小节点,必是子树最终的根 0005 BinNodePosi<T> v = x; while ( v->rc ) v = v->rc; //从最右侧通路的末端出发 0006 while ( v != r ) //逐层处理,直到抵达子树的根 0007 if ( v == v->zig() ) //以v为轴做zig旋转(同时更新高度) 0008 ( v = v->parent )->updateHeight(); //直至没有左孩子 0009 v->updateHeightAbove(); 0010 x = r; 0011 }