树的非递归遍历——中序

中序遍历比前序相对复杂一些，分析如下
1、对于任意一个节点p,左节点不为空则其入栈，一直循环到左节点为空
2、输出栈顶，pop栈顶
2、p更新为栈顶节点的右节点

//中序遍历
void midorder(Node *root)
{
    if (root == NULL)
        return;
    midorder(root->left);
    cout<<root->val<<" ";
    midorder(root->right);
}

//非递归实现
/*对于任一结点P，
1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
3)直到P为NULL并且栈为空则遍历结束*/
void midorderloop(Node *root)
{
    if (root == NULL)
        return;
    stack<Node *> sn;
    Node *p = root;
    while(p!=NULL||sn.size())
    {
        while(p!=NULL)
        {
            sn.push(p);
            p = p->left;
        }
        if (sn.size())
        {
            p = sn.top();
            sn.pop();
            cout<<p->val<<" ";
            p = p->right;
        }
    }
}