二叉树非递归遍历

转载自 二叉树遍历

struct BTNode_s{    int value;    

                                BTNode_s* pLeft;   

                             BTNode_s* pRight;}BTNode; 

 //非递归 前序

void preOrder(BTNode * pRoot){

            if(pRoot !=NULL){

                    return;

           }

    BTNode* p = pRoot;

    std::stack treeStack;

    while(p !=NULL || !treeStack.empty()){

                while(p !=NULL)   {

                    printf("%d\t", p->value);

                            treeStack(p);

                            p= p->pLeft;

                }

            if(!treeStack.empty()）   {

                        p= treeStack.top();

                        treeStack.pop();

                        p= p->pRight;

              }

    }

}

//非递归 中序

void inOrder(BTNode* pRoot)

{

if(pRoot ==NULL)

    {

         retrun;

    }

BTNode* p = pRoot;

std::stack treeStack;

while(p !=NULL || !treeStack.empty()) {

        while(p !=NULL){

            treeStack.push(p);

            p= p->pLeft;

        }

if(!treeStack.empty()) {

p= treeStack.top();

printf("%d\t", p->value);

            treeStack.pop();

p= p->pRight;

        }

    }

}    

//非递归 后序

void postOrder(BTNode* pRoot)

{

if(pRoot ==NULL)

return;

std::stack treeStack;

std::stack<int>nodeState;

BTNode* p = pRoot;

while(p !=NULL)

    {

        treeStack.push(p);

nodeState.push(0);

p= p->pLeft;

    }

while(!treeStack.empty())

    {

p= treeStack.top();

while(p->pRight!= NULL &&nodeState.top() == 0)

        {

            nodeState.pop();

nodeState.push(1);

p= p->pRight;

while(p !=NULL)

            {

                treeStack.push(p);

nodeState.push(0);

p= p->pLeft;

            }

p= treeStack.top();

        }

p= treeStack.top();

printf("%d\t", p->value);

        treeStack.pop();

        nodeState.pop();

    }

}