先序遍歷二叉樹(shù)的遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn)深入解析
1、先序遍歷二叉樹(shù) 遞歸實(shí)現(xiàn)
思想:若二叉樹(shù)為空,返回。否則
1)遍歷根節(jié)點(diǎn);
2)先序遍歷左子樹(shù);
3)先序遍歷右子樹(shù);
代碼:
template<typename elemType>
void PreOrder(nodeType<elemType> *root)
{
if(root==NULL)
return ;
visit(root->data); // visit the data
PreOrder(root->lchild); //遞歸調(diào)用,先序遍歷左子樹(shù)
PreOrder(root->rchild); //遞歸調(diào)用,先序遍歷右子樹(shù)
}
2、先序遍歷二叉樹(shù) 非遞歸實(shí)現(xiàn)
思想:二叉樹(shù)的非遞歸先序遍歷,先序遍歷思想:先讓根進(jìn)棧,只要棧不為空,就可以做彈出操作, 每次彈出一個(gè)結(jié)點(diǎn),記得把它的左右結(jié)點(diǎn)都進(jìn)棧,記得右子樹(shù)先進(jìn)棧,這樣可以保證右子樹(shù)在棧中總處于左子樹(shù)的下面。
前序遍歷二叉樹(shù)的非遞歸算法思想
建立棧 Stack;
t 指向根;
當(dāng) t 不空 或 Stack 不空時(shí)反復(fù)做:
若 t 不空,訪問(wèn)t,t 入 棧;t 指向左子女;
否則:出棧頂元素到 t 中;
t 指向右子女;
結(jié)束
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);
}
}
- 平衡二叉樹(shù)AVL操作模板
- 平衡二叉樹(shù)的實(shí)現(xiàn)實(shí)例
- 二叉樹(shù)的非遞歸后序遍歷算法實(shí)例詳解
- 二叉樹(shù)先序遍歷的非遞歸算法具體實(shí)現(xiàn)
- 二叉樹(shù)先根(先序)遍歷的改進(jìn)
- c語(yǔ)言版本二叉樹(shù)基本操作示例(先序 遞歸 非遞歸)
- python二叉樹(shù)遍歷的實(shí)現(xiàn)方法
- python二叉樹(shù)的實(shí)現(xiàn)實(shí)例
- C++二叉樹(shù)結(jié)構(gòu)的建立與基本操作
- 二叉樹(shù)遍歷 非遞歸 C++實(shí)現(xiàn)代碼
- PHP Class&Object -- 解析PHP實(shí)現(xiàn)二叉樹(shù)
- PHP Class&Object -- PHP 自排序二叉樹(shù)的深入解析
- 如何在二叉樹(shù)中找出和為某一值的所有路徑
- 探討:C++實(shí)現(xiàn)鏈?zhǔn)蕉鏄?shù)(用非遞歸方式先序,中序,后序遍歷二叉樹(shù))
- 深入理解二叉樹(shù)的非遞歸遍歷
- 深入遍歷二叉樹(shù)的各種操作詳解(非遞歸遍歷)
- 深入二叉樹(shù)兩個(gè)結(jié)點(diǎn)的最低共同父結(jié)點(diǎn)的詳解
- 二叉樹(shù)前序遍歷的非遞歸算法
相關(guān)文章
如何優(yōu)雅地使用c語(yǔ)言編寫爬蟲(chóng)
如何優(yōu)雅地使用c語(yǔ)言編寫爬蟲(chóng),本文介紹cspider爬蟲(chóng)庫(kù),這個(gè)cspider爬蟲(chóng)庫(kù)的使命在于,我們能夠使用c語(yǔ)言,依然能夠優(yōu)雅地編寫爬蟲(chóng)程序,需要的朋友可以參考下2015-12-12解析Linux下的時(shí)間函數(shù):設(shè)置以及獲取時(shí)間的方法
本篇文章是對(duì)Linux下的時(shí)間函數(shù):設(shè)置以及獲取時(shí)間的方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05深入剖析C語(yǔ)言中qsort函數(shù)的實(shí)現(xiàn)原理
這篇文章主要介紹了C語(yǔ)言中qsort函數(shù)的實(shí)現(xiàn)原理,本文將從回調(diào)函數(shù),qsort函數(shù)的應(yīng)用,qsort函數(shù)的實(shí)現(xiàn)原理三個(gè)方面進(jìn)行講解,并通過(guò)代碼示例講解的非常詳細(xì),需要的朋友可以參考下2024-03-03C++數(shù)據(jù)結(jié)構(gòu)之實(shí)現(xiàn)循環(huán)順序隊(duì)列
這篇文章主要介紹了 C++數(shù)據(jù)結(jié)構(gòu)之實(shí)現(xiàn)循環(huán)順序隊(duì)列的相關(guān)資料,需要的朋友可以參考下2017-01-01C語(yǔ)言實(shí)現(xiàn)鏈隊(duì)列基本操作
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)鏈隊(duì)列基本操作,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-09-09C語(yǔ)言實(shí)現(xiàn)一個(gè)簡(jiǎn)易通訊錄
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)一個(gè)簡(jiǎn)易通訊錄,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-07-07