C++實現(xiàn)二叉樹非遞歸遍歷方法實例總結(jié)
更新時間：2014年08月27日 11:27:05 投稿：shichen2014
這篇文章主要介紹了C++實現(xiàn)二叉樹非遞歸遍歷方法實例總結(jié),是算法設(shè)計中比較經(jīng)典的一個遍歷算法,需要的朋友可以參考下
一般來說，二叉樹的遍歷是C++程序員在面試中經(jīng)常考察的，其實前中后三種順序的遍歷都大同小異，自己模擬兩個棧用筆畫畫是不難寫出代碼的?，F(xiàn)舉一個非遞歸遍歷的方法如下，供大家參考。
具體代碼如下：
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
vector<int> out;
stack<TreeNode*> s;
s.push(root);
while(!s.empty() && root){
TreeNode *node = s.top();
out.push_back(node->val);
s.pop();
if(node->right) s.push(node->right);
if(node->left) s.push(node->left);
}
return out;
}
vector<int> inorderTraversal(TreeNode *root) {
stack<TreeNode *> s;
vector<int> out;
TreeNode *node = root;
bool done = false;
while(!done){
if(node){
s.push(node);
node = node->left;
}else {
if(s.empty()) done = true;
else{
node = s.top();
s.pop();
out.push_back(node->val);
node = node->right;
}
}
}
return out;
}
vector<int> postorderTraversal(TreeNode *root) {
vector<int> out;
stack<TreeNode*> s;
TreeNode* node = root;
s.push(node);
while(!s.empty()&&node){
node = s.top();
out.push_back(node->val);
s.pop();
if(node->left) s.push(node->left);
if(node->right)s.push(node->right);
}
reverse(out.begin(),out.end());
return out;
}
};
希望本文所述對大家的C++算法學(xué)習(xí)有所幫助。
相關(guān)文章
這篇文章主要介紹了一波C語言字符數(shù)組實用技巧集錦,包括許多字符的轉(zhuǎn)換與提取等基本操作示例,需要的朋友可以參考下2016-04-04
進度條在很地方都可以使用到，Qt自帶的進度條或者操作系統(tǒng)的進度條樣式，不夠炫，本文就介紹一下Qt編寫自定義控件的提示進度條的實現(xiàn)示例，感興趣的可以了解一下2021-12-12
QDrag類為MIME-based拖拽數(shù)據(jù)轉(zhuǎn)換提供支持。本文為大家主要介紹如何利用QDrag類實現(xiàn)拖拽拼圖功能。左邊是打散的圖，拖動到右邊進行復(fù)現(xiàn)，此外程序還支持手動拖入原圖片，感興趣的可以了解一下2022-07-07
這篇文章介紹了在一定的周期范圍內(nèi)去抓取新浪中行情數(shù)據(jù)，通過更新數(shù)據(jù)來緩解構(gòu)造模擬數(shù)據(jù)與真實數(shù)據(jù)差異性，感興趣的朋友可以了解一下2015-07-07
C,語言常用的排序方法有很多種。比如說冒泡排序,直接交換排序,直接選擇排序,直接插入排序,二分插入排序,快速排序,歸并排序等等,下面這篇文章主要給大家介紹了關(guān)于c語言實現(xiàn)幾種常用的排序算法,需要的朋友可以參考下2021-06-06
數(shù)獨是源自瑞士的一種數(shù)學(xué)游戲。是一種運用紙、筆進行演算的邏輯游戲。本文將利用C語言實現(xiàn)數(shù)獨程序，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-03-03
C語言排序算法之冒泡排序?qū)崿F(xiàn)方法【改進版】
這篇文章主要介紹了C語言排序算法之冒泡排序?qū)崿F(xiàn)方法,結(jié)合具體實例形式分析了C語言實現(xiàn)的基本冒泡排序?qū)崿F(xiàn)方法及增設(shè)flag標(biāo)志位的改進型算法,需要的朋友可以參考下2017-09-09
本文主要介紹了淺談Qt實現(xiàn)HTTP的Get/Post請求，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05
C語言經(jīng)典算法例題求100-999之間的“水仙花數(shù)”
本文的主要內(nèi)容，設(shè)計一個程序，找出100-999之間的“水仙花數(shù)”,需要的朋友可以參考下2015-07-07
下面小編就為大家?guī)硪黄獙崿F(xiàn)一個內(nèi)存池管理的類方法。小編覺得挺不錯的現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01