二叉樹前序遍歷的非遞歸算法
更新時間：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;}
}
}
相關(guān)文章
本文是小結(jié)了一下C語言的函數(shù)語法，詳細介紹了C語言函數(shù)語法的概述、函數(shù)的定義、函數(shù)的返回值、函數(shù)調(diào)用等7個方面的內(nèi)容，非常詳細，這里推薦給小伙伴們2021-11-11
C++?Socket實現(xiàn)TCP與UDP網(wǎng)絡編程
本文主要介紹了C++?Socket實現(xiàn)TCP與UDP網(wǎng)絡編程，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
這篇文章主要為大家介紹了嵌入式C語言二級指針在鏈表中的應用，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步早日升職加薪2022-04-04
sockpp是一個開源、簡單、現(xiàn)代的C++套接字庫,這篇文章主要為大家詳細介紹一下套接字庫sockpp的使用,文中的示例代碼講解詳細,感興趣的小伙伴可以學習一下2023-11-11
本文主要介紹了C++多線程std::call_once的使用，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要介紹了c++和python實現(xiàn)順序查找實例，流程即將目標數(shù)值和數(shù)據(jù)庫中的每個數(shù)值進行比較，如果相同則搜索完成，如果不同則繼續(xù)比較下一處，下面來看看具體的實例操作吧,需要的朋友可以參考一下2022-03-03
本文主要介紹了C++解決TCP粘包的問題實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-08-08
這篇文章主要為大家詳細介紹了C語言實現(xiàn)窗口抖動，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-11-11
C++的try塊與異常處理及調(diào)試技術(shù)實例解析
這篇文章主要介紹了C++的try塊與異常處理及調(diào)試技術(shù)實例解析,有助于讀者加深對try塊調(diào)試技術(shù)的認識,需要的朋友可以參考下2014-07-07
這篇文章主要為大家介紹了C語言的選擇結(jié)構(gòu)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01