二叉树---中序遍历分析

栈的作用：用来存放要访问的结点，把所有结点（包含空指针）先入栈，再把满足条件的结点出栈的过程，出栈的顺序就是遍历结点的顺序。栈有先入后出的特性，因此先将该结点入栈，再将该结点的左子树入栈，访问完该结点后，再将右子树入栈。

栈顶结点是需要第一个访问的结点。

访问结点的条件：该结点的左子树是空树。（因此要把该结点入栈，再将其所有左子树结点入栈。）

大体思路：

1、先将根结点入栈，遍历左子树。

2、访问根结点。

3、中序遍历右子树。

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

    BiTree p;

    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(p->rchild);//把右子树作为第一个要访问的结点入栈（即开始中序遍历右子树）。

        }//if

    }//while

}//InOrderPraverse