二叉树中序遍历分析

重点理解栈的应用：栈是用来存放未访问的结点，栈顶结点是需要先访问的结点；

访问结点的条件：左子树为空指针。也就是说只有当某个结点的左子树为空树时才能调用print()函数访问该结点。

大概思路：将一个树的根结点入栈，然后循环检查这棵树中是否含有未访问过的结点（含有空结点）并根据情况在循环内做入栈和出栈处理。

1、访问该结点的左子树

2、访问该结点

3、访问该结点的右子树

具体过程：

将树的根结点作为需要访问的第一个结点压入栈中，然后判断该结点是否存在，若该结点存在，则把其左子树入栈（），所以要先访问其左子树结点，访问完左子树结点后，然后再访问该结点。

中序遍历需要把每个结点要做入栈和出栈操作。注意：空结点也做压栈操作，根据情况再退栈。

int InOrderTraverse(Bitree T, int (*Print)(TElemType e)){

    InitStack(S);

    Push(S,T);  //根结点可能为空指针

    while(!StackEmpty(S)){

        while(GetTop(S,p) && p)

        push(S, p->lchild);  //向左走到尽头

        Pop(S,p);  //空指针退栈（空结点退栈）

        if(!StackEmpty(S)){ //判断是否存在未访问过的结点。此时栈中存放的都是实结点。

            Pop(S,p);

            if(!Print(p->data)) return 0;

            Push(S,p->rchild);

        }//if

    }//while

    return 1;

}//InOrderTraverse