【轉】更簡單的非遞歸遍歷二叉樹的方法

解決二叉樹的很多問題的方案都是基于對二叉樹的遍歷。遍歷二叉樹的前序，中序，后序三大方法算是計算機科班學生必寫代碼了。其遞歸遍歷是人人都能信手拈來，可是在手生時寫出非遞歸遍歷恐非易事。正因為并非易事，所以網上出現無數的介紹二叉樹非遞歸遍歷方法的文章。可是大家需要的真是那些非遞歸遍歷代碼和講述嗎？代碼早在學數據結構時就看懂了，理解了，可為什么我們一而再再而三地忘記非遞歸遍歷方法，卻始終記住了遞歸遍歷方法？

三種遞歸遍歷對遍歷的描述，思路非常簡潔，最重要的是三種方法完全統一，大大減輕了我們理解的負擔。而我們常接觸到那三種非遞歸遍歷方法，除了都使用棧，具體實現各有差異，導致了理解的模糊。本文給出了一種統一的三大非遞歸遍歷的實現思想。

三種遞歸遍歷

//前序遍歷 void preorder(TreeNode *root, vector<int> &path) { if(root != NULL) { path.push_back(root->val); preorder(root->left, path); preorder(root->right, path); } } //中序遍歷 void inorder(TreeNode *root, vector<int> &path) { if(root != NULL) { inorder(root->left, path); path.push_back(root->val); inorder(root->right, path); } } //后續遍歷 void postorder(TreeNode *root, vector<int> &path) { if(root != NULL) { postorder(root->left, path); postorder(root->right, path); path.push_back(root->val); } }

由上可見，遞歸的算法實現思路和代碼風格非常統一，關于“遞歸”的理解可見我的《人腦理解遞歸》。

教科書上的非遞歸遍歷

//非遞歸前序遍歷 void preorderTraversal(TreeNode *root, vector<int> &path) { stack<TreeNode *> s; TreeNode *p = root; while(p != NULL || !s.empty()) { while(p != NULL) { path.push_back(p->val); s.push(p); p = p->left; } if(!s.empty()) { p = s.top(); s.pop(); p = p->right; } } } //非遞歸中序遍歷 void inorderTraversal(TreeNode *root, vector<int> &path) { stack<TreeNode *> s; TreeNode *p = root; while(p != NULL || !s.empty()) { while(p != NULL) { s.push(p); p = p->left; } if(!s.empty()) { p = s.top(); path.push_back(p->val); s.pop(); p = p->right; } } } //非遞歸后序遍歷-迭代 void postorderTraversal(TreeNode *root, vector<int> &path) {stack<TempNode *> s;TreeNode *p = root;TempNode *temp;while(p != NULL || !s.empty()) { while(p != NULL) //沿左子樹一直往下搜索，直至出現沒有左子樹的結點 { TreeNode *tempNode = new TreeNode; tempNode->btnode = p; tempNode->isFirst = true; s.push(tempNode); p = p->left; } if(!s.empty()) { temp = s.top(); s.pop(); if(temp->isFirst == true) //表示是第一次出現在棧頂 { temp->isFirst = false; s.push(temp); p = temp->btnode->right; } else //第二次出現在棧頂 { path.push_back(temp->btnode->val); p = NULL; } } } }

看了上面教科書的三種非遞歸遍歷方法，不難發現，后序遍歷的實現的復雜程度明顯高于前序遍歷和中序遍歷，前序遍歷和中序遍歷看似實現風格一樣，但是實際上前者是在指針迭代時訪問結點值，后者是在棧頂訪問結點值，實現思路也是有本質區別的。而這三種方法最大的缺點就是都使用嵌套循環，大大增加了理解的復雜度。

更簡單的非遞歸遍歷二叉樹的方法

這里我給出統一的實現思路和代碼風格的方法，完成對二叉樹的三種非遞歸遍歷。

//更簡單的非遞歸前序遍歷 void preorderTraversalNew(TreeNode *root, vector<int> &path) { stack< pair<TreeNode *, bool> > s; s.push(make_pair(root, false)); bool visited; while(!s.empty()) { root = s.top().first; visited = s.top().second; s.pop(); if(root == NULL) continue; if(visited) { path.push_back(root->val); } else { s.push(make_pair(root->right, false)); s.push(make_pair(root->left, false)); s.push(make_pair(root, true)); } } } //更簡單的非遞歸中序遍歷 void inorderTraversalNew(TreeNode *root, vector<int> &path) { stack< pair<TreeNode *, bool> > s; s.push(make_pair(root, false)); bool visited; while(!s.empty()) { root = s.top().first; visited = s.top().second; s.pop(); if(root == NULL) continue; if(visited) { path.push_back(root->val); } else { s.push(make_pair(root->right, false)); s.push(make_pair(root, true)); s.push(make_pair(root->left, false)); } } } //更簡單的非遞歸后序遍歷 void postorderTraversalNew(TreeNode *root, vector<int> &path) { stack< pair<TreeNode *, bool> > s; s.push(make_pair(root, false)); bool visited; while(!s.empty()) { root = s.top().first; visited = s.top().second; s.pop(); if(root == NULL) continue; if(visited) { path.push_back(root->val); } else { s.push(make_pair(root, true)); s.push(make_pair(root->right, false)); s.push(make_pair(root->left, false)); } } }

以上三種遍歷實現代碼行數一模一樣，如同遞歸遍歷一樣，只有三行核心代碼的先后順序有區別。為什么能產生這樣的效果？下面我將會介紹。

有重合元素的局部有序一定能導致整體有序

這就是我得以統一三種更簡單的非遞歸遍歷方法的基本思想：有重合元素的局部有序一定能導致整體有序。
如下這段序列，局部2 3 4和局部1 2 3都是有序的，但是不能由此保證整體有序。

而下面這段序列，局部2 3 4,4 5 6,6 8 10都是有序的，而且相鄰局部都有一個重合元素，所以保證了序列整體也是有序的。

應用于二叉樹

基于這種思想，我就構思三種非遞歸遍歷的統一思想：不管是前序，中序，后序，只要我能保證對每個結點而言，該結點，其左子結點，其右子結點都滿足以前序/中序/后序的訪問順序,整個二叉樹的這種三結點局部有序一定能保證整體以前序/中序/后序訪問，因為相鄰的局部必有重合的結點，即一個局部的“根”結點是另外一個局部的“子”結點。

如下圖，對二叉樹而言，將每個框內結點集都看做一個局部，那么局部有A,A B C,B D E,D,E,C F,F,并且可以發現每個結點元素都是相鄰的兩個局部的重合結點。發覺這個是非常關鍵的，因為知道了重合結點，就可以對一個局部排好序后，通過取出一個重合結點過渡到與之相鄰的局部進行新的局部排序。我們可以用棧來保證局部的順序（排在順序前面的后入棧，排在后面的先入棧，保證這個局部元素出棧的順序一定正確），然后通過棧頂元素(重合元素)過渡到對新局部的排序，對新局部的排序會導致該重合結點再次入棧，所以當棧頂出現已完成過渡使命的結點時，就可以徹底出棧輸出了（而這個輸出可以保證該結點在它過渡的那個局部一定就是排在最前面的），而新棧頂元素將會繼續完成新局部的過渡。當所有結點都完成了過渡使命時，就全部出棧了，這時我敢保證所有局部元素都是有序出棧，而相鄰局部必有重合元素則保證了整體的輸出一定是有序的。這種思想的好處是將算法與順序分離，定義何種順序并不影響算法，算法只做這么一件事：將棧頂元素取出，使以此元素為“根”結點的局部有序入棧，但若此前已通過該結點將其局部入棧，則直接出棧輸出即可。

從實現的程序中可以看到：三種非遞歸遍歷唯一不同的就是局部入棧的三行代碼的先后順序。所以不管是根->左->右,左->根->右,左->右->根,甚至是根->右->左,右->根->左,右->左->根定義的新順序，算法實現都無變化，除了改變局部入棧順序。

值得一提的是，對于前序遍歷，大家可能發現取出一個棧頂元素，使其局部前序入棧后，棧頂元素依然是此元素，接著就要出棧輸出了，所以使其隨局部入棧是沒有必要的，其代碼就可以簡化為下面的形式。

void preorderTraversalNew(TreeNode *root, vector<int> &path) {stack<TreeNode *> s;s.push(root); while(!s.empty()) { root = s.top(); s.pop(); if(root == NULL) { continue; } else { path.push_back(root->val); s.push(root->right); s.push(root->left); } } }

這就是我要介紹的一種更簡單的非遞歸遍歷二叉樹的方法。

?

轉自http://www.jianshu.com/p/4db970d8ddc1

posted on 2016-01-23 19:00 kernel_main 閱讀(...) 評論(...) 編輯 收藏

轉載于:https://www.cnblogs.com/kernel0815/p/5153813.html

總結

以上是生活随笔為你收集整理的【转】更简单的非递归遍历二叉树的方法的全部內容，希望文章能夠幫你解決所遇到的問題。

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