二叉樹前序遍歷的非遞歸算法
更新時間：2014年02月28日 15:17:40 投稿：shangke
這篇文章主要介紹了二叉樹前序遍歷的非遞歸算法,需要的朋友可以參考下
二叉樹的前序遍歷是先根節(jié)點，然后如果有左子樹則再先序遍歷左子樹，然后如果有右子樹則再先序遍歷其又子樹。
遞歸算法如下
復制代碼 代碼如下:
void preorder(Betree *t)
{ if(t==null) return;visit(t);//訪問該節(jié)點preorder(t->lchild);preorder(t->rchild); }
當然遞歸算法是隱式使用了棧。我們仔細分析這個過程，先是取出了根節(jié)點進行了訪問，然后我們把根節(jié)點退棧，退棧后必然有節(jié)點進棧，怎么辦呢？根節(jié)點只能直接訪問到rchild和lchild，如果是左子樹的根節(jié)點進了棧，那么必然是后訪問之，所以必然是rchild先進棧，lchild后進棧?？梢援媹D加深理解。
那么現(xiàn)在寫出先序遍歷二叉樹的算法。
復制代碼 代碼如下:
void preorder(Betree *t)
{ //算法中我們使用一維數(shù)組來模擬一個順序棧
if(t==null) return;//為空樹的話完全沒有必要進行下面的操作
Betree *stack[max];
top=1;stack[top]=t;//根節(jié)點入棧
while(top>0)
{ nd=stack[top];//取出根節(jié)點 top=top-1;//退棧 visit(nd->data); //訪問根節(jié)點 if(nd->rchild!=null) { top=top+1;stack[top]=nd->rchild;} //根節(jié)點有右子樹，將其進棧，等到左子樹訪問完后再訪問之
if(nd->lchild!=null) { top=top+1;stack[top]=nd->lchild;}
}
}
相關文章
這篇文章主要為大家詳細介紹了C語言實現(xiàn)圖形化打磚塊游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
C++繼承和虛繼承的內存模型是一個老生常談的話題，實現(xiàn)方法主要依賴于編譯器，本文從多個角度通過代碼詳解C++中虛繼承的內存模型知識，感興趣的朋友跟隨小編一起看看吧2021-09-09
本篇文章是對C++中“#”號的使用技巧進行了分析介紹，需要的朋友參考下2013-05-05
本篇文章是對C語言中如何正確使用const，進行了詳細的分析介紹。需要的朋友參考下2013-05-05
C++實現(xiàn)LeetCode(149.共線點個數(shù))
這篇文章主要介紹了C++實現(xiàn)LeetCode(149.共線點個數(shù)),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07
下面小編就為大家?guī)硪黄獜膮R編看c++中的多態(tài)詳解。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-06-06
因為工作的需要，有時候我們離開時并不想讓別人看到我們電腦的內容，所以本文為大家分享了一個基于C++實現(xiàn)的假裝藍屏的小程序，需要的可以參考下2023-06-06
C++?容器中map和unordered?map區(qū)別詳解
這篇文章主要為大家介紹了C++?容器中map和unordered?map區(qū)別示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-11-11
Eigen是一個基于線性代數(shù)的C++模板庫,主要用于矩陣、向量、數(shù)值求解和相關算法,本文主要為大家簡單聊聊Eigen庫的使用,希望對大家有所幫助2023-12-12
OpenCV4.1.0+VisualStudio2019開發(fā)環(huán)境搭建(超級簡單)
這篇文章主要介紹了OpenCV4.1.0+VisualStudio2019開發(fā)環(huán)境搭建(超級簡單)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-03-03