0001 template <typename T, typename VST> //元素类型、操作器 0002 void travIn_I2 ( BinNodePosi(T) x, VST& visit ) { //二叉树中序遍历算法(迭代版#2) 0003 Stack<BinNodePosi(T)> S; //辅助栈 0004 while ( true ) 0005 if ( x ) { 0006 S.push ( x ); //根节点进栈 0007 x = x->lc; //深入遍历左子树 0008 } else if ( !S.empty() ) { 0009 x = S.pop(); //尚未访问的最低祖先节点退栈 0010 visit ( x->data ); //访问该祖先节点 0011 x = x->rc; //遍历祖先的右子树 0012 } else 0013 break; //遍历完成 0014 }