二叉树遍历的递归和非递归实现

void preOrderR(const BTreeNode* pRoot)
{
    if (pRoot != nullptr)
    {
        cout << pRoot->value << '\t';
        preOrderR(pRoot->pLeft);
        preOrderR(pRoot->pRight);
    }
}

void inOrderR(const BTreeNode* pRoot)
{
    if (pRoot != nullptr)
    {
        inOrderR(pRoot->pLeft);
        cout << pRoot->value << '\t';
        inOrderR(pRoot->pRight);
    }
}

void postOrderR(const BTreeNode* pRoot)
{
    if (pRoot != nullptr)
    {
        postOrderR(pRoot->pLeft);
        postOrderR(pRoot->pRight);
        cout << pRoot->value << '\t';
    }
}

void preOrder(BTreeNode* pRoot)
{
    if (pRoot == nullptr) return;

    stack<BTreeNode*> nodes;
    BTreeNode* pTempNode = pRoot;
    while (pTempNode != nullptr || !nodes.empty())
    {
        while (pTempNode != nullptr)
        {
            cout << pTempNode->value << '\t';
            nodes.push(pTempNode);
            pTempNode = pTempNode->pLeft;
        }

        if (!nodes.empty())
        {
            pTempNode = nodes.top();
            nodes.pop();
            pTempNode = pTempNode->pRight;
        }
    }
}

void inOrder(BTreeNode* pRoot)
{
    if (pRoot == nullptr) return;

    stack<BTreeNode*> nodes;
    BTreeNode* pTempNode = pRoot;
    while (pTempNode != nullptr || !nodes.empty())
    {
        while (pTempNode != nullptr)
        {
            nodes.push(pTempNode);
            pTempNode = pTempNode->pLeft;
        }

        if (!nodes.empty())
        {
            pTempNode = nodes.top();
            cout << pTempNode->value << '\t';
            nodes.pop();
            pTempNode = pTempNode->pRight;
        }
    }
}

void postOrder(BTreeNode* pRoot)
{
    if (pRoot == nullptr) return;
    stack<BTreeNode*> nodes;
    BTreeNode* pTempNode = pRoot;
    nodes.push(pTempNode);
    BTreeNode* pPastNode = nullptr;

    while(!nodes.empty())
    {
        pTempNode = nodes.top();
        if (// this node is leaf
             (pTempNode->pLeft==nullptr && pTempNode->pRight==nullptr) 
           ||//its children are visited
             (pPastNode!=nullptr && 
               (pPastNode==pTempNode->pLeft || pPastNode==pTempNode->pRight)
             )
           )
        {
            cout << pTempNode->value << '\t';
            nodes.pop();
            pPastNode = pTempNode;
        }
        else
        {
            if (pTempNode->pRight != nullptr)
                nodes.push(pTempNode->pRight);
            if (pTempNode->pLeft != nullptr)
                nodes.push(pTempNode->pLeft);
        }
    }

}