高速の並べ替えと二叉の木が遍歴する非再帰的アルゴリズム

急速な並べ替えと二叉の木が遍歴する再帰的アルゴリズムはみんなよく知っていますが、再帰的でないアルゴリズムは複雑です.
高速ソート非再帰的アルゴリズム:

int partition(int a[],int low,int high)
{
    if(a==NULL)
        exit(1);
    int pvot=a[low];
    while(low<high)
    {
        while(low<high&&a[high]>=pvot)--high;
        a[low]=a[high];
        while(low<high&&a[low]<=pvot)++low;
        a[high]=a[low]
    }
    a[low]=pvot;
    return low;
}
void QuickSort(int a[],int low,int high)
{
    stack<int>st;
    if(low<high)
    {
        int mid=partition(a,low,high);
        if(low<mid-1)
        {
            st.push(low);
            st.push(mid-1);
        }
        if(mid+1<high)
        {
            st.push(mid+1);
            st.push(high);
        }
    }
    while(!st.empty())
    {
        high=st.top();
        st.pop();
        low=st.top();
        st.pop();
        int mid=partition(a,low,high);
        if(low<mid-1)
        {
            st.push(low);
            st.push(mid-1);
        }
        if(mid+1<high)
        {
            st.push(mid+1);
            st.push(high);
        }
    }
}

二叉の木の非再帰遍歴
1.前の順に訪問順にルートを優先的に訪問し、左の子供と右の子供をそれぞれ訪問します.つまり、いずれの結点についても、ルートの結点と見なすことができるので、直接に訪問してから、その左の子供が空でない場合は、同じ規則でその左の子樹を訪問することができる.左のツリーにアクセスすると、その右のツリーにアクセスします.したがって、その処理は以下の通りである.
任意の結点Pについて:
1)結点Pにアクセスし、結点Pをスタックに入れる.
2)結点Pの左の子供が空いているかどうかを判断し、空いている場合はスタックの一番上の結点を取って、そしてスタックの一番上の結点の右の子供を現在の結点Pに置いて、1に循環する.空でなければ、Pの左の子供を現在の結点Pにします.
3)PがNULLであり、スタックが空であるまで、遍歴は終了する.

void preOrder2(BinTree *root)     //        
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            s.pop();
            p=p->rchild;
        }
    }
}

2.中順は中順を経て、いずれの結点についても左の子供を優先的に訪問し、左の子供は結点として見られ、左の子供は結点を続けて訪問し、左の子供が結点が空いている結点に出会うまで訪問し、同じ規定で右の子樹を訪問します.したがって、その処理は以下の通りである.
任意の結点Pに対して、
1)左の子供が空でない場合、Pをスタックに入れて、Pの左の子供を現在のPにして、現在の結点Pに対して同じ処理を行う.
2)左の子供が空の場合、スタックの一番上の要素を取って、そのスタックの一番上の結点にアクセスして、現在のPをスタックの一番上の結点の右の子供にセットします.
3)PがNULLであり、スタックが空であるまで巡回して終了する.

void inOrder2(BinTree *root)      //       
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            cout<<p->data<<" ";
            s.pop();
            p=p->rchild;
        }
    }    
} 

3.後の順序の後に巡回する非再帰的な実装は、3つのエルゴード方式の中で最も難しいものです.後の順序が巡回しているので、左の子供と右の子供がすでに訪問されていて、左の子供が右の子供の前に訪問してこそルートを訪問することができます.これはプロセスのコントロールに難題をもたらします.

void postOrder2(BNode* root)   //       
{
    if(!root)
        return;
    stack<BNode*>st;
    BNode* p=root;
    BNode* r=nullptr;
    while(p||!st.empty())
    {
        if(p)
        {
            st.push(p);
            p=p->left;
        }
        else
        {
            p=st.top();
            if(p->right&&p->right!=r)
            {
                p=p->right;
                st.push(p);
                p=p->left;
            }
            else
            {
                p=st.top();
                st.pop();
                cout<<p->key<<" ";
                r=p;
                p=nullptr;
            }
        }
    }
}