0001 template <typename T> //在以S栈顶节点为根的子树中,找到最高左侧可见叶节点 0002 static void gotoHLVFL ( 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() ) { 0017 if ( S.top() != x->parent ) //若栈顶非当前节点之父(则必为其右兄),此时需 0018 gotoHLVFL ( S ); //在以其右兄为根之子树中,找到HLVFL(相当于递归深入其中) 0019 x = S.pop(); visit ( x->data ); //弹出栈顶(即前一节点之后继),并访问之 0020 } 0021 }