二叉树的非递归遍历

中序非递归遍历

1. 遇到一个结点，就把他压入栈，并去遍历它的左子树
2. 当左子树遍历结束后，从栈顶弹出这个结点并访问它
3. 然后按其右指针再去钟中序遍历该节点的右子树

void InOrderTraversal( BinTree BT )
{
    BinTree T = BT;
    Stack S = CreatStack( MaxSize );  //  创建堆栈
    while ( T || !IsEmpty( S ) ) {
        while ( T ) {  // 遍历左子树，并将左子树压入堆栈
            Push( S, T );
            T = T->Left;
        }
        if ( !IsEmpty( S ) ) {
            T = Pop( S );  // 将结点弹出堆栈
            printf( "%5d", T->Data );
            T = T->Data;  // 转向右子树
        }
    }
}