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

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

解题思路：设置一个假设空间足够、且采用顺序存储结构的堆栈STACK[0..M-1]来保存遍历过程中连接点的地址，并设栈顶指针为top，初始时top的值为-1；同时，算法中还设置了一个活动指针变量p，用来指向当前要访问的那个结点，初始时它指向二叉树的根结点。
核心思想为：当p所指的结点不为空时，即将该结点所在链结点的地址进栈，然后再将p指向该结点的左孩子结点；当p所指的结点为空时，则丛堆栈中退出栈顶元素送p，并访问该结点，然后再将p指向该结点的右孩子结点。重复上述过程，直到p为null，并且堆栈也为空，遍历结束。

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

function inOrder1(BT) {
    let stack=new Array(MaxSize), p=BT, top=-1
    do {
        while ( p!=null ) {
            stack[++top] = p
            p = p.lchild
        }
        p = stack[top--]
        console.log(p.data)
        p = p.rchild
    } while (!(p==null&&top==-1));
}

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

性能：
时间和空间复杂度都为O(n)