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