先序遍歷二叉樹的遞歸實現(xiàn)與非遞歸實現(xiàn)深入解析
更新時間：2013年07月31日 10:04:42 作者：
以下是對先序遍歷二叉樹的遞歸實現(xiàn)與非遞歸實現(xiàn)進行了詳細的分析介紹，需要的朋友可以過來參考下
1、先序遍歷二叉樹 遞歸實現(xiàn)
思想：若二叉樹為空，返回。否則
1）遍歷根節(jié)點；
2）先序遍歷左子樹；
3）先序遍歷右子樹；
代碼：
復(fù)制代碼 代碼如下:
template<typename elemType>
void PreOrder(nodeType<elemType> *root)
{
if(root==NULL)
return ;
visit(root->data); // visit the data
PreOrder(root->lchild); //遞歸調(diào)用，先序遍歷左子樹
PreOrder(root->rchild); //遞歸調(diào)用，先序遍歷右子樹
}
2、先序遍歷二叉樹 非遞歸實現(xiàn)
思想：二叉樹的非遞歸先序遍歷，先序遍歷思想：先讓根進棧，只要棧不為空，就可以做彈出操作， 每次彈出一個結(jié)點，記得把它的左右結(jié)點都進棧，記得右子樹先進棧，這樣可以保證右子樹在棧中總處于左子樹的下面。
前序遍歷二叉樹的非遞歸算法思想
建立棧 Stack；
t 指向根；
當(dāng) t 不空 或 Stack 不空時反復(fù)做：
若 t 不空，訪問t，t 入 棧；t 指向左子女；
否則：出棧頂元素到 t 中；
t 指向右子女；
結(jié)束
復(fù)制代碼 代碼如下:
void PreOrder_Nonrecursive(BinaryTree T) //先序遍歷的非遞歸
{
if(!T) return ;
stack<BinaryTree> s;
s.push(T);
while(!s.empty())
{
BinaryTree temp = s.top();
visit(temp->data);
s.pop();
if(temp->rchild)
s.push(temp->rchild);
if(temp->lchild)
s.push(temp->lchild);
}
}
您可能感興趣的文章:
- 平衡二叉樹AVL操作模板
- 平衡二叉樹的實現(xiàn)實例
- 二叉樹的非遞歸后序遍歷算法實例詳解
- 二叉樹先序遍歷的非遞歸算法具體實現(xiàn)
- 二叉樹先根（先序）遍歷的改進
- c語言版本二叉樹基本操作示例(先序 遞歸 非遞歸)
- python二叉樹遍歷的實現(xiàn)方法
- python二叉樹的實現(xiàn)實例
- C++二叉樹結(jié)構(gòu)的建立與基本操作
- 二叉樹遍歷 非遞歸 C++實現(xiàn)代碼
- PHP Class&Object -- 解析PHP實現(xiàn)二叉樹
- PHP Class&Object -- PHP 自排序二叉樹的深入解析
- 如何在二叉樹中找出和為某一值的所有路徑
- 探討:C++實現(xiàn)鏈式二叉樹(用非遞歸方式先序,中序,后序遍歷二叉樹)
- 深入理解二叉樹的非遞歸遍歷
- 深入遍歷二叉樹的各種操作詳解（非遞歸遍歷）
- 深入二叉樹兩個結(jié)點的最低共同父結(jié)點的詳解
- 二叉樹前序遍歷的非遞歸算法
相關(guān)文章
如何優(yōu)雅地使用c語言編寫爬蟲，本文介紹cspider爬蟲庫，這個cspider爬蟲庫的使命在于，我們能夠使用c語言，依然能夠優(yōu)雅地編寫爬蟲程序，需要的朋友可以參考下2015-12-12
本文給大家分享的是個人寫的一段對C++中十種內(nèi)部排序算法的比較分析的代碼，主要在于測試10種排序方法的性能，給大家參考下吧。2015-03-03
解析Linux下的時間函數(shù):設(shè)置以及獲取時間的方法
本篇文章是對Linux下的時間函數(shù):設(shè)置以及獲取時間的方法進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要為大家詳細介紹了C++實現(xiàn)騎士走棋盤算法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07
深入剖析C語言中qsort函數(shù)的實現(xiàn)原理
這篇文章主要介紹了C語言中qsort函數(shù)的實現(xiàn)原理,本文將從回調(diào)函數(shù),qsort函數(shù)的應(yīng)用,qsort函數(shù)的實現(xiàn)原理三個方面進行講解,并通過代碼示例講解的非常詳細,需要的朋友可以參考下2024-03-03
C++數(shù)據(jù)結(jié)構(gòu)之實現(xiàn)循環(huán)順序隊列
這篇文章主要介紹了 C++數(shù)據(jù)結(jié)構(gòu)之實現(xiàn)循環(huán)順序隊列的相關(guān)資料,需要的朋友可以參考下2017-01-01
這篇文章主要為大家詳細介紹了C語言實現(xiàn)鏈隊列基本操作，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-09-09
這篇文章主要為大家詳細介紹了C語言實現(xiàn)一個簡易通訊錄，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07
本篇文章是對字符串移位包含的問題的解決方法進行了詳細的分析介紹，需要的朋友參考下2013-05-05
今天小編就為大家分享一篇關(guān)于C++堆和棧的區(qū)別與聯(lián)系講解，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-04-04