0001 template <typename T, typename VST> //元素类型、操作器 0002 void travIn_I4 ( BinNodePosi(T) x, VST& visit ) { //二叉树中序遍历(迭代版#4,无需栈或标志位) 0003 while ( true ) 0004 if ( HasLChild ( *x ) ) //若有左子树,则 0005 x = x->lc; //深入遍历左子树 0006 else { //否则 0007 visit ( x->data ); //访问当前节点,并 0008 while ( !HasRChild ( *x ) ) //不断地在无右分支处 0009 if ( ! ( x = x->succ() ) ) return; //回溯至直接后继(在没有后继的末节点处,直接退出) 0010 else visit ( x->data ); //访问新的当前节点 0011 x = x->rc; //(直至有右分支处)转向非空的右子树 0012 } 0013 }