二叉樹遍歷分為三種：

先序遍歷：先訪問根結點，其次左節點，最后右節點

中序遍歷：先訪問左結點，其次跟節點，最后右節點

后序遍歷：先訪問左結點，其次右節點，最后根節點

三種遍歷的遞歸算法實現形式類似，僅僅是訪問順序不同，非常簡潔。如下：

//節點定義 typedef struct node {int val;struct node *left;struct node *right; }*pnode, node; //后序遍歷遞歸算法 void postOrderRecursive(pnode root) {if (root){//訪問左子樹postOrderRecursive (root->left);//訪問右子樹postOrderRecursive (root->right);//訪問根結點printf("%d ", root->val); }return ; }//中序遍歷遞歸算法 void inOrderRecursive(pnode root) {if (root){//訪問左子樹inOrderRecursive (root->left);//訪問根結點printf("%d ", root->val);//訪問右子樹inOrderRecursive (root->right); }return ; }//先序遍歷遞歸算法 void preOrderRecursive(pnode root) {if (root){printf("%d ", root->val);//訪問左子樹preOrderRecursive (root->left);//訪問右子樹preOrderRecursive (root->right); }return ; }

遞歸算法屬于必知必會的基礎，面試如果問到此類問題，一般都會讓給出非遞歸實現。話說，遞歸算法一般都可以轉換成循環和棧的非遞歸實現。

對于先序遍歷來說，先將根結點入棧，進入循環，取棧頂，先將節點右孩子和左孩子依次進棧，訪問該節點，按照此節奏，循環處理，直到棧空。即，每次取出棧頂元素，將其右左孩子節點依次進棧，訪問即可。

//先序遍歷非遞歸 void preOrderNonRec(pnode root) {pnode stack[1000], curr, prev;int top, end;if (root == NULL)return ;top = end = 0;//根結點入棧stack[top++] = root;while (top > 0){//取棧頂curr = stack[--top];//右子樹入棧if (curr->right)stack[top++] = curr->right;//左子樹入棧 if (curr->left)stack[top++] = curr->left;//訪問節點 printf ("%d ", curr->val); }printf("\n");return ; }

對于中序遍歷的非遞歸算法，依然是棧加循環的方式，處理上和上一步略微有點區別。

先將根結點入棧，當前節點指向左孩子，只要當前節點的左孩子存在，則繼續循環處理，即父節點進棧，節點指向左孩子，直到節點為空，這時，從棧中取出棧頂，對于棧中取出的元素，總是先訪問，然后指向右孩子，繼續第一步處理，即父節點進棧，節點指向左孩子。這里需要注意的有兩點：1. 從棧中取出來的元素訪問后無需再進棧。2. 對于棧中取出的元素，總是先訪問，然后指向右孩子。

//中序遍歷，非遞歸 void inorderNonRec(pnode root) {pnode stack[1000], curr;int top, end;if (root == NULL)return ;top = end = 0;//根結點進棧stack[top++] = root;//當前節點指向左孩子curr = root->left;while (curr || top > 0){//節點存在，則父節點進棧，指向左孩子if (curr){if (curr->left){stack[top++] = curr;curr = curr->left;continue;}}else{curr = stack[--top];}//取棧頂，訪問后，指向右孩子printf("%d ", curr->val);curr = curr->right;}printf("\n");return ; }

后序遍歷的非遞歸實現依然是循環加棧處理。和中序遍歷一樣，不過處理上略微有點不同。相當之處仍然是父節點先進棧，指向左孩子。不同的地方在于，從棧中取出元素時，此時不訪問，而是如果存在右孩子，則父節點繼續進棧，節點指向其右孩子。如果右孩子不存在，則訪問該節點，同時記錄當前訪問的節點。繼續出棧，同上步，如果存在右孩子，父節點繼續進棧，節點指向其右孩子，此時，為防止死循環，需要將右孩子和之前訪問的節點比較，如果相同，則無需進棧，此時直接訪問即可。不理解的同學請畫一顆二叉樹輔助思考。

//后序遍歷，非遞歸 void postOrderNonRec(pnode root) {pnode stack[1000], curr, prev;int top, end;if (root == NULL)return ;top = end = 0;//根結點入棧stack[top++] = root;//指向左孩子curr = root->left;while (curr || top > 0){//只要存在孩子節點，則父節點進棧，指向其孩子節點。if (curr){if (curr->left || curr->right){stack[top++] = curr;if (curr->left)curr = curr->left;elsecurr = curr->right; continue;}}else{//取棧頂，如果存在右孩子且和上一個訪問節點不一樣，則父節點//繼續進棧，指向右孩子。curr = stack[--top];if (curr->right && curr->right != prev){stack[top++] = curr; curr = curr->right;continue;}}//訪問節點同時保存訪問的位置。printf("%d ", curr->val);prev = curr;curr = NULL;}printf("\n");return ; }

=============================================================================================

Linux應用程序、內核、驅動、后臺開發交流討論群(745510310)，感興趣的同學可以加群討論、交流、資料查找等，前進的道路上，你不是一個人奧^_^。

總結

以上是生活随笔為你收集整理的二叉树遍历算法的六种c语言实现 递归与非递归的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。