直接看代码啦！
前中后指的是跟被访问的次序！
递归很好理解，重点是非递归！！！
1 #define _CRT_SECURE_NO_WARNINGS 2 #include <iostream> 3 #include<fstream> 4 using namespace std; 5 6 typedef struct TreeNode 7 { 8 int data; 9 int flag; 10 struct TreeNode* lchid; 11 struct TreeNode* rchid; 12 }TreeNode; 13 14 typedef struct StackNode 15 { 16 TreeNode* data; 17 StackNode* next; 18 }StackNode; 19 20 typedef struct QueueNode 21 { 22 TreeNode* data; 23 struct QueueNode* pre; 24 struct QueueNode* next; 25 }QueueNode; 26 27 QueueNode* initQueue() 28 { 29 QueueNode* Q = (QueueNode*)malloc(sizeof(QueueNode)); 30 Q->data = NULL; 31 Q->next = Q; 32 Q->pre = Q; 33 return Q; 34 } 35 36 void enQueue(TreeNode* data, QueueNode* Q) 37 { 38 QueueNode* node= (QueueNode*)malloc(sizeof(QueueNode)); 39 node->data = data; 40 node->next = Q; 41 node->pre = Q->pre; 42 Q->pre->next = node; 43 Q->pre = node; 44 } 45 46 int isEmpty(QueueNode* Q) 47 { 48 if (Q->next == Q) 49 return 1; 50 return 0; 51 } 52 53 QueueNode* deQueue(QueueNode* Q) 54 { 55 if (isEmpty(Q)) 56 return NULL; 57 QueueNode* node = Q->next; 58 Q->next->next->pre = Q; 59 Q->next = Q->next->next; 60 return node; 61 } 62 63 StackNode* initStack() 64 { 65 StackNode* S = (StackNode*)malloc(sizeof(StackNode)); 66 S->data = NULL; 67 S->next = NULL; 68 return S; 69 } 70 71 void Push(TreeNode* data, StackNode* S) 72 { 73 StackNode* node = (StackNode*)malloc(sizeof(StackNode)); 74 node->data = data; 75 node->next = S->next; 76 S->next = node; 77 } 78 79 int isEmptyS(StackNode* S) 80 { 81 if (S->next == NULL) 82 return 1; 83 return 0; 84 } 85 86 StackNode* Pop(StackNode* S) 87 { 88 if (isEmptyS(S)) 89 return NULL; 90 StackNode* node = S->next; 91 S->next = node->next; 92 return node; 93 } 94 95 StackNode* GetPop(StackNode* S) 96 { 97 if (isEmptyS(S)) 98 return NULL; 99 StackNode* node = S->next; 100 return node; 101 } 102 103 void createTree(TreeNode** T,int* data,int*index) 104 { 105 int ch; 106 ch= data[*index]; 107 *index+=1; 108 if (ch == 0) 109 *T = NULL;//此时为空节点 110 else 111 { 112 *T = (TreeNode*)malloc(sizeof(TreeNode)); 113 (*T)->data = ch; 114 (*T)->flag = 0; 115 //创建左子树 116 createTree(&((*T)->lchid),data,index); 117 //创建右子树 118 createTree(&((*T)->rchid),data,index); 119 } 120 } 121 122 //先序遍历(递归) 123 void preOrderFun(TreeNode* T) 124 { 125 if (T == NULL) 126 return; 127 else 128 { 129 //输出节点 130 cout << T->data<<" "; 131 //左孩子 132 preOrderFun(T->lchid); 133 //右孩子 134 preOrderFun(T->rchid); 135 } 136 } 137 138 //先序遍历(非递归) 139 void preOrder(TreeNode* T) 140 { 141 TreeNode* node = T; 142 StackNode* S = initStack(); 143 while (node || !isEmptyS(S)) 144 { 145 if (node) 146 { 147 cout << node->data<<" "; 148 Push(node, S); 149 node = node->lchid; 150 } 151 else 152 { 153 node=Pop(S)->data; 154 node = node->rchid; 155 } 156 } 157 } 158 159 //中序遍历(递归) 160 void inOrderFun(TreeNode* T) 161 { 162 if (T == NULL) 163 return; 164 else 165 { 166 //左孩子 167 inOrderFun(T->lchid); 168 //输出节点 169 cout << T->data<<" "; 170 //右孩子 171 inOrderFun(T->rchid); 172 } 173 } 174 175 //中序遍历(非递归) 176 void inOrder(TreeNode* T) 177 { 178 TreeNode* node = T; 179 StackNode* S = initStack(); 180 while (node || !isEmptyS(S)) 181 { 182 if (node) 183 { 184 Push(node, S); 185 node = node->lchid; 186 } 187 else 188 { 189 node = Pop(S)->data; 190 cout << node->data << " "; 191 node = node->rchid; 192 } 193 } 194 } 195 196 197 //后续遍历(递归) 198 void postOrderFun(TreeNode* T) 199 { 200 if (T == NULL) 201 return; 202 else 203 { 204 //左孩子 205 postOrderFun(T->lchid); 206 //右孩子 207 postOrderFun(T->rchid); 208 //输出节点 209 cout << T->data<<' '; 210 } 211 } 212 213 //后序遍历(非递归) 214 void postOrder(TreeNode* T) 215 { 216 TreeNode* node = T; 217 StackNode* S = initStack(); 218 while (node || !isEmptyS(S)) 219 { 220 if (node) 221 { 222 Push(node, S); 223 node = node->lchid; 224 } 225 else 226 { 227 TreeNode*top = GetPop(S)->data; 228 if (top->rchid && top->rchid->flag == 0) 229 { 230 top = top->rchid; 231 Push(top, S); 232 node = top->lchid; 233 } 234 else 235 { 236 top = Pop(S)->data; 237 cout << top->data << " "; 238 top->flag = 1;//重点是标记已经访问过的 239 } 240 } 241 242 } 243 } 244 245 246 //层次遍历 247 void leveltravel(QueueNode* Q, TreeNode* T) 248 { 249 enQueue(T, Q); 250 while (!isEmpty(Q)) 251 { 252 QueueNode* node = deQueue(Q); 253 cout << node->data->data<<' '; 254 if (node->data->lchid) 255 enQueue(node->data->lchid, Q); 256 if (node->data->rchid) 257 enQueue(node->data->rchid, Q); 258 } 259 } 260 261 int main() 262 { 263 TreeNode* T; 264 QueueNode* Q = initQueue(); 265 int data[26] = { 1,2,4,7,0,0,6,0,0,5,8,0,0,10,0,0,3,0,9,11,0,0,12,0,0}; 266 //16进制 267 int index = 0; 268 createTree(&T,data,&index); 269 270 cout << "前序遍历递归:" << endl; 271 preOrderFun(T); 272 cout << endl; 273 274 cout << "中序遍历递归:" << endl; 275 inOrderFun(T); 276 cout << endl; 277 278 cout << "后序遍历递归:" << endl; 279 postOrderFun(T); 280 cout << endl; 281 282 cout << "层次遍历:" << endl; 283 leveltravel(Q, T); 284 cout << endl; 285 286 cout << "前序遍历非递归:" << endl; 287 preOrder(T); 288 cout << endl; 289 290 cout << "中序遍历非递归:" << endl; 291 inOrder(T); 292 cout << endl; 293 294 cout << "后序遍历非递归:" << endl; 295 postOrder(T); 296 cout << endl; 297 }