先順遍歴、中順遍歴、後続遍歴の非再帰遍歴、コードテスト済み

struct BinaryTreeNode 

{

    int                    m_nValue; 

    BinaryTreeNode*        m_pLeft;  

    BinaryTreeNode*        m_pRight; 

};



 struct StackNode

{

    BinaryTreeNode* treeNode;

    bool isRightHasVisited;//  

};





// 

void PreorderUnrec(BinaryTreeNode* root)

{

    stack<BinaryTreeNode*> s;

    BinaryTreeNode* p=root;

    while(NULL!=p||!s.empty())

    {

        while(NULL!=p)

        {

            printf("%d  ",p->m_nValue);

            s.push(p);

            p=p->m_pLeft;

        }

        if(!s.empty())

        {

            p=s.top();

            s.pop();

            p=p->m_pRight;

        }

    }

}



// 

void InorderUnrec(BinaryTreeNode* root)

{

    stack<BinaryTreeNode*> s;

    BinaryTreeNode* p=root;

    while(NULL!=p||!s.empty())

    {

        while(NULL!=p)

        {

            s.push(p);

            p=p->m_pLeft;

        }

        if(!s.empty())

        {

            p=s.top();

            s.pop();

            printf("%d  ",p->m_nValue);

            p=p->m_pRight;

        }

    }

}

// 

void PostOrderUnrec(BinaryTreeNode* root)

{

    stack<StackNode> s;

    StackNode stackNode;

    BinaryTreeNode* p=root;

    do

    {

        while(p!=NULL)

        {

            stackNode.treeNode=p;

            stackNode.isRightHasVisited=false;

            s.push(stackNode);

            p=p->m_pLeft;

        }

        while(!s.empty()&&s.top().isRightHasVisited==true)

        {

            stackNode=s.top();

            s.pop();

            p=stackNode.treeNode;

            printf("%d  ",p->m_nValue);

        }

        if(!s.empty())

        {

            s.top().isRightHasVisited=true;

            p=s.top().treeNode->m_pRight;

        }

    }while(!s.empty());

}