0001 template <typename T> //在以S栈顶节点为根的子树中,找到最高左侧可见叶节点 0002 static void gotoLeftmostLeaf( Stack<BinNodePosi<T>>& S ) { //沿途所遇节点依次入栈 0003 while ( BinNodePosi<T> x = S.top() ) //自顶而下,反复检查当前节点(即栈顶) 0004 if ( HasLChild( *x ) ) { //尽可能向左 0005 if ( HasRChild( *x ) ) S.push( x->rc ); //若有右孩子,优先入栈 0006 S.push( x->lc ); //然后才转至左孩子 0007 } else //实不得已 0008 S.push( x->rc ); //才向右 0009 S.pop(); //返回之前,弹出栈顶的空节点 0010 } 0011 0012 template <typename T, typename VST> 0013 void travPost_I( BinNodePosi<T> x, VST& visit ) { //二叉树的后序遍历(迭代版) 0014 Stack<BinNodePosi<T>> S; //辅助栈 0015 if ( x ) S.push( x ); //根节点入栈 0016 while ( !S.empty() ) { // x始终为当前节点 0017 if ( S.top() != x->parent ) ////若栈顶非x之父(而为右兄) 0018 gotoLeftmostLeaf( S ); //则在其右兄子树中找到HLVFL(相当于递归深入) 0019 x = S.pop(); visit( x->data ); //弹出栈顶(即前一节点之后继),并访问之 0020 } 0021 }