非递归后序遍历 遍历二叉树:设根结点初始时非空 后序算法:1、结点(初始时为根)进栈(标志0),沿左指针查找左儿子(标志1) 2、左儿子非空,返回1。 3、退栈。若为标志1转4,否则标志2,转5。 4、进栈转向右子树(标志2),如右儿子非空,则转向1;空转向3 5、访问该结点,返回3 6、反复1到5,至栈空为止。 e.g. 后序:E、L、D、C、A 分析:1、二叉树最先被访问的结点是二叉树中最左方的叶子。 2、p的后序的直接后继q:1、p是父结点的右儿子,则q=该父结点。2、p是父结点的左 儿子,如果有右子树,则q=该右子树中最左的叶子。如果,无右子树,q=父结点 3、p无父结点,那么q=NULL。非递归后序遍历 • 遍历二叉树：设根结点初始时非空 •后序算法：1、结点（初始时为根）进栈（标志0），沿左指针查找左儿子（标志1） 2、左儿子非空，返回1。 3、退栈。若为标志1转4 ，否则标志2，转5。 4、进栈转向右子树（标志2），如右儿子非空，则转向1；空转向 3。 5、访问该结点，返回3 6、反复1 到 5 ，至栈空为止。 e.g: C D E L A 后序：E、L、D、C、A 分析：1、二叉树最先被访问的结点是二叉树中最左方的叶子。 2、p的后序的直接后继q: 1、p是父结点的右儿子，则q=该父结点。2、p是父结点的左 儿子，如果有右子树，则q=该右子树中最左的叶子。如果，无右子树，q=父结点。 3、p无父结点，那么q == NULL