数据结构题目41：二叉树的后序遍历（非递归）

题目：若二叉树为二叉链表存储结构，写出二叉树的后序遍历的非递归算法。

解题思路：当指针p指向某一个结点时，不能马上对它进行访问，而要先遍历它的左子树，因而要将此结点的地址进栈；当其左子树遍历完毕之后，再次搜索到该结点时（该结点的地址通过退栈得到），还不能对它进行访问，还需要遍历它的右子树，所以，再一次将此结点的地址进栈。只要当该结点的右子树被遍历后回到该结点，才访问该结点。为了标明某结点是否可以被访问，引入一个标志变量flag，并有 flag=0 表示该结点暂不访问，flag=1 表示该结点可以访问。标志flag的值随同进栈结点的地址一起进栈和出栈。因此算法中有两个stack，使用同一栈顶指针top。

具体算法如下：
这里使用到建立二叉树方法createBT(strBT)

function postOrder1(BT) {
    let stack1=new Array(MaxSize), p=BT, stack2=new Array(MaxSize), flag, top=-1
    if ( BT!=null ) {
        do {
            while ( p!=null ) {
                stack1[++top] = p
                stack2[top] = 0
                p = p.lchild
            }
            p = stack1[top]
            flag = stack2[top--]
            if ( flag==0 ) {
                stack1[++top] = p
                stack2[top] = 1
                p = p.rchild
            } else {
                console.log(p.data)
                p = null
            }
        } while ( !(p==null && top==-1) );
    }
}

var strBT="A(B(D,E(G)),C(F(,H)))@"
var BT = createBT(strBT)
postOrder1(BT)