二叉樹前序遍歷的非遞歸算法
更新時(shí)間：2014年02月28日 15:17:40 投稿：shangke
這篇文章主要介紹了二叉樹前序遍歷的非遞歸算法,需要的朋友可以參考下
二叉樹的前序遍歷是先根節(jié)點(diǎn)，然后如果有左子樹則再先序遍歷左子樹，然后如果有右子樹則再先序遍歷其又子樹。
遞歸算法如下
復(fù)制代碼 代碼如下:
void preorder(Betree *t)
{ if(t==null) return;visit(t);//訪問該節(jié)點(diǎn)preorder(t->lchild);preorder(t->rchild); }
當(dāng)然遞歸算法是隱式使用了棧。我們仔細(xì)分析這個(gè)過程，先是取出了根節(jié)點(diǎn)進(jìn)行了訪問，然后我們把根節(jié)點(diǎn)退棧，退棧后必然有節(jié)點(diǎn)進(jìn)棧，怎么辦呢？根節(jié)點(diǎn)只能直接訪問到rchild和lchild，如果是左子樹的根節(jié)點(diǎn)進(jìn)了棧，那么必然是后訪問之，所以必然是rchild先進(jìn)棧，lchild后進(jìn)棧?？梢援媹D加深理解。
那么現(xiàn)在寫出先序遍歷二叉樹的算法。
復(fù)制代碼 代碼如下:
void preorder(Betree *t)
{ //算法中我們使用一維數(shù)組來模擬一個(gè)順序棧
if(t==null) return;//為空樹的話完全沒有必要進(jìn)行下面的操作
Betree *stack[max];
top=1;stack[top]=t;//根節(jié)點(diǎn)入棧
while(top>0)
{ nd=stack[top];//取出根節(jié)點(diǎn) top=top-1;//退棧 visit(nd->data); //訪問根節(jié)點(diǎn) if(nd->rchild!=null) { top=top+1;stack[top]=nd->rchild;} //根節(jié)點(diǎn)有右子樹，將其進(jìn)棧，等到左子樹訪問完后再訪問之
if(nd->lchild!=null) { top=top+1;stack[top]=nd->lchild;}
}
}
相關(guān)文章
本文是小結(jié)了一下C語(yǔ)言的函數(shù)語(yǔ)法，詳細(xì)介紹了C語(yǔ)言函數(shù)語(yǔ)法的概述、函數(shù)的定義、函數(shù)的返回值、函數(shù)調(diào)用等7個(gè)方面的內(nèi)容，非常詳細(xì)，這里推薦給小伙伴們2021-11-11
C++?Socket實(shí)現(xiàn)TCP與UDP網(wǎng)絡(luò)編程
本文主要介紹了C++?Socket實(shí)現(xiàn)TCP與UDP網(wǎng)絡(luò)編程，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-01-01
嵌入式C語(yǔ)言二級(jí)指針在鏈表中的應(yīng)用
這篇文章主要為大家介紹了嵌入式C語(yǔ)言二級(jí)指針在鏈表中的應(yīng)用，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步早日升職加薪2022-04-04
sockpp是一個(gè)開源、簡(jiǎn)單、現(xiàn)代的C++套接字庫(kù),這篇文章主要為大家詳細(xì)介紹一下套接字庫(kù)sockpp的使用,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以學(xué)習(xí)一下2023-11-11
本文主要介紹了C++多線程std::call_once的使用，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
c++和python實(shí)現(xiàn)順序查找實(shí)例
這篇文章主要介紹了c++和python實(shí)現(xiàn)順序查找實(shí)例，流程即將目標(biāo)數(shù)值和數(shù)據(jù)庫(kù)中的每個(gè)數(shù)值進(jìn)行比較，如果相同則搜索完成，如果不同則繼續(xù)比較下一處，下面來看看具體的實(shí)例操作吧,需要的朋友可以參考一下2022-03-03
本文主要介紹了C++解決TCP粘包的問題實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-08-08
C語(yǔ)言實(shí)現(xiàn)窗口抖動(dòng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)窗口抖動(dòng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-11-11
C++的try塊與異常處理及調(diào)試技術(shù)實(shí)例解析
這篇文章主要介紹了C++的try塊與異常處理及調(diào)試技術(shù)實(shí)例解析,有助于讀者加深對(duì)try塊調(diào)試技術(shù)的認(rèn)識(shí),需要的朋友可以參考下2014-07-07
一篇文章帶你了解C語(yǔ)言的選擇結(jié)構(gòu)
這篇文章主要為大家介紹了C語(yǔ)言的選擇結(jié)構(gòu)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01