深さ優先ループ(先、後、中)非再帰実装(C++)

ツリーの深さ優先ループ再帰は簡単で,呼び出し順序を調整すればそれぞれ先順,後順,中順ループの結果が得られる.ここでは,非再帰的な考え方(スタックを用いた)を記録し,コードを与える.
先序遍歴:ルート-左-右スタックは先进的で后出で、ルート-左-右の顺番でスタックを出ることを望んで、私达はまずルートノードをスタックに押して、それから(ルート)を弾いて、弾き出す同时に、それぞれ右サブツリーのルートノードと左サブツリーのルートノードに押して、先に左を弾いて右を弾いて、次にスタックのトップ要素を弾いて、そしてその右、左サブツリーのルートノードをスタックに押して、スタックが空になるまで、このように押します.
後序遍歴:左-右-根は先序遍歴に類似し、それぞれルートノード、右サブツリーのルートノード、左サブツリーのルートノードを圧入し、異なるのは左右ノードを圧入する前にルートノードを弾き出さず、左-右-根のような順序で外に弾き出すことを保証する.根、右、左を押し込み、スタックトップ要素に子供がいるかどうかを判断し、ある場合はスタックトップ要素にサブツリーがなくなるまで右、左を押し込み続けます.問題は、私たちはいつもスタックの上の要素を右の左の子供に押し込み、スタックの上の多くは左の子の木で、そのすべての右の子の木の子供はスタックに押し込まれていません.これは、私たちがポップアップするときに操作する必要があります.子供がいる右の木に遭遇するときは、まずそれをポップアップしないで、前のルートノードの操作と同じように、右の左の子供をスタックの頂上要素のサブツリーがないまで押して、外に弾き続けます.では、桟の頂上に子供の右の木があるかどうかをどう判断しますか?前回ポップアップされたノードAを記録し、スタックトップノードに子供がいて、その左右のサブツリーがAでない場合、スタックトップが子供の右サブツリーであることを証明することができる.
中序遍歴:左-根-右は根ノードに圧入し、スタックの上部の要素に左の子供がいる場合は、葉ノードまで左の子供をスタックに圧入し続け、次に外にポップアップし、ポップアップした要素に対して右の子供がいる場合は、右の子供をスタックに圧入し(注意して、先にポップアップしてからスタックを圧入し、先根後右を保証する)、そして左の子供を葉ノードまで圧入し続ける.スタックが空になるまで、このプロセスを繰り返します.
 
C++実装を添付します.

#include
#include
#include
#include
using namespace std;

struct TreeNode
{
    int value;
    TreeNode *left,*right;
    TreeNode(int v, TreeNode* l, TreeNode* r):value(v), left(l), right(r){}
};

//  
vector treepre(TreeNode *root);
//  
vector treebehind(TreeNode *root);
//  
vector treemiddle(TreeNode *root);

//         （   ）
int main()
{
    TreeNode* node1 = new TreeNode(3,NULL,NULL);
    TreeNode* node2 = new TreeNode(2,NULL,NULL);
    TreeNode* node3 = new TreeNode(5,node1,node2);
    TreeNode* node4 = new TreeNode(1,NULL,node3);
    TreeNode* node6 = new TreeNode(6,NULL,NULL);
    TreeNode* node7 = new TreeNode(7,NULL,NULL);
    TreeNode* node5 = new TreeNode(4,node6,node7);
    TreeNode* node = new TreeNode(9,node4,node5);
    
    
    vector res = treemiddle(node);

    for(int i=0;i treepre(TreeNode *root)
{//  
    vector res;
    stack s;
    s.push(root);
    
    while(!s.empty())
    {
        TreeNode* t = s.top();
        res.push_back(t->value);
        s.pop();
        if(t->right)
            s.push(t->right);
        if(t->left)
            s.push(t->left);
    }
    
    return res;
}

vector treebehind(TreeNode *root)
{//  
    vector res;
    stack s;
    s.push(root);
    TreeNode* last = NULL;
    TreeNode* t;

    while(!s.empty())
    {
        t = s.top();
        while(!s.empty()&&(t->right||t->left))
        {
            if(t->right)
                s.push(t->right);
            if(t->left)
                s.push(t->left);
            t = s.top();
        }

        if(!s.empty())
            t = s.top();
        while(!s.empty()&&(!(t->right||t->left)||last==NULL ||(t->right&&t->right==last) ||(t->left&&t->left==last)))
        {
            res.push_back(t->value);
            last = t;
            s.pop();
            
            if(!s.empty())
                t = s.top();
        }
    }

    return res;
}

vector treemiddle(TreeNode *root)
{//  
    vector res;
    stack s;
    TreeNode* t;
    s.push(root);
    
    while(!s.empty())
    {
        t = s.top();
        while(t->left)
        {
            s.push(t->left);
            t = s.top();
        }
        while(!s.empty())
        {
            t = s.top();
            res.push_back(t->value);
            s.pop();
            if(t->right)
            {
                s.push(t->right);
                break;
            }
        }
    }
    
    return res;
}