上码：
1 #include <iostream>
2 #include <string>
3 #include <stack>
4 #include <queue>
5 using namespace std;
6
7 template<class T>
8 struct BiNode {
9 T data;
10 BiNode<T> *lchild, *rchild;//左子树、右子树
11 };
12
13 template<class T>
14 class BiTree
15 {
16 public:
17 BiTree(); //构造函数，初始化二叉树，前序序列由键盘输入
18 ~BiTree(); //析构函数，释放二叉链表中的各结点的存储空间
19 BiNode<T>* Getroot(); //获得指向根节点的指针
20 void PreOrder(BiNode<T>* root); //前序遍历二叉树
21 void InOrder(BiNode<T>* root); //中序遍历二叉树
22 void PostOrder(BiNode<T>* root); //后序遍历二叉树
23 void LeverOrder(BiNode<T>* root); //层序遍历二叉树
24
25 void NonPreOrder(BiNode<T>* root);
26 void NonInOrder(BiNode<T>* root);
27 void NonPostOrder(BiNode<T>* root);
28 private:
29 BiNode<T> *root; //指向根节点的头指针
30 BiNode<T> *Create(); //有参构造函数调用
31 void ReLease(BiNode<T> *root); //析构函数调用
32 };
33 template<class T>
34 BiTree<T>::BiTree() {
35 this->root = Create(); //创建对象时，构造函数被调用后，调用Great函数进行初始化
36 }
37
38 template<class T>
39 BiTree<T>::~BiTree() {
40 ReLease(root); //调用ReLease释放二叉树链表
41 }
42
43 template<class T>
44 BiNode<T>* BiTree<T>::Getroot() {
45 return root; //返回根节点地址
46 }
47
48 template<class T>
49 void BiTree<T>::PreOrder(BiNode<T>* root) {
50 if (root == NULL)
51 return;
52 cout << root->data << " ";
53 PreOrder(root->lchild); //前序遍历二叉树（根，左，右）
54 PreOrder(root->rchild);
55 }
56
57 template<class T>
58 void BiTree<T>::InOrder(BiNode<T> *root) {
59 if (root == NULL)
60 return;
61 InOrder(root->lchild); //中序遍历二叉树（左，根，右）
62 cout << root->data << " ";
63 InOrder(root->rchild);
64 }
65
66 template<class T>
67 void BiTree<T>::PostOrder(BiNode<T>* root) {
68 if (root == NULL)
69 return;
70 PostOrder(root->lchild); //后序遍历二叉树（左，右，根）
71 PostOrder(root->rchild);
72 cout << root->data << " ";
73 }
74
75 template<class T>
76 void BiTree<T>::LeverOrder(BiNode<T>* root) {
77 BiNode<T> *p; //层序遍历
78 if (root == NULL)
79 return;
80 queue<BiNode<T>*> q;
81 q.push(root);
82 while (!q.empty()) {
83 p = q.front();
84 cout << p->data << " ";
85 q.pop();
86 if (p->lchild != NULL) {
87 q.push(p->lchild);
88 }
89 if (p->rchild != NULL) {
90 q.push(p->rchild);
91 }
92 }
93 }
94
95 template<class T>
96 BiNode<T>* BiTree<T>::Create() {
97 BiNode<T>* root; //构造二叉树
98 T ch;
99 cout << "请输入创建的一颗二叉树的结点数据：" << endl;
100 cin >> ch;
101 if (ch == "#")
102 root = NULL;
103 else {
104 root = new BiNode<T>;
105 root->data = ch;
106 root->lchild = Create();
107 root->rchild = Create();
108 }
109 return root;
110 }
111
112 template<class T>
113 void BiTree<T>::ReLease(BiNode<T>* root) {
114 if (root != NULL) { //删除二叉树
115 ReLease(root->lchild);
116 ReLease(root->rchild);
117 delete root;
118 }
119 }
120
121 template<class T>
122 void BiTree<T>::NonPreOrder(BiNode<T>* root) {
123 if (root == NULL)
124 return;
125 stack<BiNode<T>*> s;
126 BiNode<T> *p = root, *q;
127 while (p != NULL || !s.empty())
128 {
129 if (p != NULL) {
130 cout << p->data << ' ';
131 s.push(p);
132 p = p->lchild;
133 }
134 else {
135 q = s.top();
136 s.pop();
137 p = q->rchild;
138 }
139 }
140 }
141 template<class T>
142 void BiTree<T>::NonInOrder(BiNode<T>* root) {
143 if (root == NULL)
144 return;
145 stack<BiNode<T>*> s;
146 BiNode<T> *p = root, *q;
147 while (!s.empty() || p != NULL)
148 {
149 while (p != NULL) {
150 s.push(p);
151 p = p->lchild;
152 }
153 if (!s.empty()) {
154 q = s.top();
155 s.pop();
156 cout << q->data << ' ';
157 p = q->rchild;
158 }
159
160 }
161
162 }
163 template<class T>
164 void BiTree<T>::NonPostOrder(BiNode<T>* root) {
165 if (root == NULL)
166 return;
167 stack<BiNode<T>*> s;
168 stack<int> symbol; //visit 记录访问的次数0，1，与s栈一一对应
169 BiNode<T> *p = root, *q;
170 while (!s.empty() || p != NULL)
171 {
172 while (p != NULL) {
173 s.push(p);
174 symbol.push(0); //对应位置入栈 0，表示未经访问
175 p = p->lchild;
176 }
177 //栈不空，且栈顶元素未经访问
178 if (!s.empty() && !symbol.top()) {
179 symbol.pop();
180 symbol.push(1);
181
182 q = s.top();
183 p = q->rchild;
184 }
185 //栈不空，且栈顶元素已经被访问
186 else if (!s.empty() && symbol.top()) {
187 //经过循环体 右子树结束
188 while (symbol.top()) { //清空栈中已被访问过的元素，即symbol为 1者
189 q = s.top();
190 cout << q->data << ' ';
191 s.pop();
192
193 symbol.pop();
194 if (!symbol.size())
195 break;
196 }
197
198 if (!s.empty()) {
199 symbol.pop();
200 symbol.push(1);
201
202 q = s.top();
203 p = q->rchild;
204 }
205 else {
206 p = NULL;
207 }
208 }
209 else
210 continue;
211
212 }
213 }
214
215 int main()
216 {
217 BiTree<string> bt;//创建一棵树
218 BiNode<string>* root = bt.Getroot();
219 cout << "------前序遍历------" << endl;
220 bt.PreOrder(root);
221 cout << endl;
222 cout << "------后序遍历------" << endl;
223 bt.PostOrder(root);
224 cout << endl;
225 cout << "------中序遍历------" << endl;
226 bt.InOrder(root);
227 cout << endl;
228 cout << "------层序遍历------" << endl;
229 bt.LeverOrder(root);
230 cout << endl;
231 cout << "---非递归前序遍历---" << endl;
232 bt.NonPreOrder(root);
233 cout << endl;
234 cout << "---非递归后序遍历---" << endl;
235 bt.NonPostOrder(root);
236 cout << endl;
237 cout << "---非递归中序遍历---" << endl;
238 bt.NonInOrder(root);
239 cout << endl;
240 return 0;
241 }
后序遍历有点蹩脚，需要注意几点细节，避免死循环陷阱。