0001 template <typename T, typename VST> //元素类型、操作器
0002 void travIn_I3( BinNodePosi<T> x, VST& visit ) { //二叉树中序遍历算法（迭代版#3，无需辅助栈）
0003    bool backtrack = false; //前一步是否刚从左子树回溯——省去栈，仅O(1)辅助空间
0004    while ( true )
0005       if ( !backtrack && HasLChild( *x ) ) //若有左子树且不是刚刚回溯，则
0006          x = x->lc; //深入遍历左子树
0007       else { //否则——无左子树或刚刚回溯（相当于无左子树）
0008          visit( x->data ); //访问该节点
0009          if ( HasRChild( *x ) ) { //若其右子树非空，则
0010             x = x->rc; //深入右子树继续遍历
0011             backtrack = false; //并关闭回溯标志
0012          } else { //若右子树空，则
0013             if ( !( x = x->succ() ) ) break; //回溯（含抵达末节点时的退出返回）
0014             backtrack = true; //并设置回溯标志
0015          }
0016       }
0017 }