二叉树的非递归遍历

关于二叉树节点的经典定义

struct Node {
    int    data;
    struct Node *left;
    struct Node *right;
};

后序非递归实现

void PostTravelNoRecure(struct Node *root)
{
    stack<struct Node*> st;
    
    struct Node * prev = NULL;//最近一次访问节点
    struct Node * pNode = root;//最近一次访问节点

    while(pNode||!st.empty())
    {
        //找到最左节点
        while(pNode)
        {
            st.push(pNode);
            pNode = pNode->left;
        }
        pNode = st.top(); 
        //如果右子树空，或者右节点已经访问过
        if(!(pNode->right)||(prev == pNode->right))
        {
            printf("%d\n",pNode->data);//访问当前节点
            st.pop();
            prev = pNode;
            pNode = NULL;
        }else{
            pNode = pNode->right;//右节点入栈
        }

    }
}

中序遍历实现（优化版）

void InTravelNoRecureVersionOne(struct Node *root)
{
    
    stack<struct Node*> st;
    struct Node * pNode = root;//最近一次访问节点

    while(pNode ||!(st.empty()))
    {
        if(pNode)//有优化
        {
            st.push(pNode);
            pNode = pNode->left;
        }else{
            //根指针
            pNode = st.top();
            st.pop();
            printf("%d\n",pNode->data);

            pNode = pNode->right;
        }
            
    }
}

前序遍历类似版本（优化）

void PrevTravelNoRecure(struct Node *root)
{

    stack<struct Node*> st;
    struct Node * pNode = root;//最近一次访问节点
    
    while(pNode ||!(st.empty()))
    {
        if(pNode)
        {
            printf("%d\n",pNode->data);
            st.push(pNode);
            pNode = pNode->left;
        }else{
            pNode = st.top();
            st.pop();
            pNode = pNode->right;
        }
    }
}