用非递归的方法实现二叉树中的层遍历，先序遍历，中序遍历和后序遍历

#include 
#include
#include
#include
#include

using namespace std;
class Node
{
public:
    Node() :m_left(NULL), m_right() {}
    Node(char v) :m_value(v), m_left(NULL), m_right() {}
    char m_value;
    Node* m_left;
    Node* m_right;
};
class Tree
{
public:
    Tree() :m_root(NULL), m_flag('*') {}
    Node* Create(const char*& str);
    void LevOrder();//层遍历（上下左右）
    void PreOrder();//非递归先序遍历
    void InOrder();//非递归中序遍历
    void PosOrder();//非递归后续遍历
public:
    Node* m_root;
private:
    int m_flag;

};
void Tree::LevOrder()
{
    queue<Node*>qq;
    Node* front = NULL;
    if (m_root != NULL)
    {
        qq.push(m_root);
        while (!qq.empty())
        {
            front = qq.front();//获取对头
            qq.pop();//出队

            cout << front->m_value << " ";
            //左右孩子入队
            if (front->m_left != NULL)
                qq.push(front->m_left);
            if (front->m_right!= NULL)
                qq.push(front->m_right);
        }
    }
}
Node* Tree::Create(const char*& str)
{
    if (*str == m_flag)
    {
        return NULL;
    }
    //根据先序遍历，创建根
    Node* node = new Node(*str);//new了个新节点
    node->m_left = Create(++str);
    node->m_right = Create(++str);
    return node;
}
//非递归 要借助栈
//先序遍历：根左右 根据右左根的顺序入栈
void Tree::PreOrder()
{
    stack<Node*>ss;
    Node* top = NULL;
    ss.push(m_root);
    while (!ss.empty())
    {
        top = ss.top();
        ss.pop();
        cout << top->m_value << " ";
        //根据右左顺序入栈
        if (top->m_right != NULL)
            ss.push(top->m_right);
        if (top->m_left != NULL)
            ss.push(top->m_left);
    }
    cout << endl;
}
//中序遍历：左根右
//1.先将当前节点以及所有的左子树入栈
//2.判断栈是否为空，如果不空，获得栈顶，并出栈，然后用p记住当前节点的右子树
//3.查看当前右子树是否有左孩子，如果有，则继续进行1,2,3步骤，直到p为空或者栈为空为止

void Tree::InOrder()
{
    if (m_root != NULL)
    {
        stack<Node* >ss;
        Node* p = m_root;
        Node* top = NULL;
        while (p || !ss.empty())
        {
            while (p != NULL)
            {
                ss.push(p);
                p = p->m_left;
            }
            if (!ss.empty())
            {
                top = ss.top();
                ss.pop();
                cout << top->m_value << " ";
                p = top->m_right;//当前节点遍历完后，p记住他的右子树
            }
        }
    }
}
//后序遍历:左右根 入栈顺序为根右左  需要一个指针记住已经遍历过得节点
//入栈：如果当前节点有孩子，则按照左右顺序入栈
//出栈：如果当前节点没有左右孩子；当前节点有孩子，但孩子已经遍历过，则出栈
void Tree::PosOrder()
{
    if (m_root != NULL)
    {
        stack<Node*>ss;
        Node* top = NULL;
        Node* pre = NULL;
        ss.push(m_root);//入栈
        while (!ss.empty())
        {
            top = ss.top();//获得栈顶
            //判断栈顶有无孩子
            //出栈：要么没孩子，要么孩子已经遍历
            if (top->m_left == NULL && top->m_right == NULL ||
                pre != NULL && top->m_left == pre || top->m_right == pre)
            {
                cout << top->m_value << " ";
                ss.pop();//出栈
                pre = top;//pre指针记住出栈的节点，为了下一次查看
            }
            else
            {
                if (top->m_right != NULL)
                    ss.push(top->m_right);
                if (top->m_left != NULL)
                    ss.push(top->m_left);
            }
        }
    }
}
int  main()
{
    Tree t;//定了一棵树
    const char* str = "abd**eh***cf*i**g**";
    t.m_root = t.Create(str);
    cout << "LevOrder: ";
    t.LevOrder();
    cout << endl;
    cout << "PreOrder: ";
    t.PreOrder();
    cout << endl;
    cout << "InOrder: ";
    t.InOrder();
    cout << endl;
    cout << "PosOrder ";
    t.PosOrder();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

运行结果：