先序遍歷二叉樹(shù)的遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn)深入解析

更新時(shí)間：2013年07月31日 10:04:42 作者：

以下是對(duì)先序遍歷二叉樹(shù)的遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn)進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以過(guò)來(lái)參考下

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é)束

復(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);  
    }  
}  

您可能感興趣的文章:

相關(guān)文章

C++詳解非類(lèi)型模板參數(shù)Nontype與Template及Parameters的使用
除了類(lèi)型可以作為模板參數(shù)，普通值也可以作為模板函數(shù)，即非類(lèi)型模板參數(shù)（Nontype Template Parameters）。下面讓我們一起了解一下
2022-06-06
C++零基礎(chǔ)精通數(shù)據(jù)結(jié)構(gòu)之帶頭雙向循環(huán)鏈表
帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來(lái)很多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡(jiǎn)單
2022-03-03
深入單鏈表的快速排序詳解
本篇文章是對(duì)單鏈表的快速排序進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
2013-05-05
C語(yǔ)言實(shí)現(xiàn)萬(wàn)年歷效果
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)萬(wàn)年歷效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2019-11-11
詳解C++11中模板的優(yōu)化問(wèn)題
這篇文章主要介紹了C++11中模板的優(yōu)化問(wèn)題,通過(guò)實(shí)例代碼得出結(jié)論，當(dāng)所有模板參數(shù)都有默認(rèn)參數(shù)時(shí)，函數(shù)模板的調(diào)用如同一個(gè)普通函數(shù)，具體示例代碼跟隨小編一起看看吧
2021-09-09
C++編寫(xiě)生成不重復(fù)的隨機(jī)數(shù)代碼
本文給大家匯總介紹了3種c++實(shí)現(xiàn)生成不重復(fù)的隨機(jī)數(shù)的函數(shù)，十分的簡(jiǎn)單實(shí)用，有需要的小伙伴可以參考下。
2015-05-05
使用C語(yǔ)言調(diào)用luajit的方法詳解
C語(yǔ)言是一種非常流行的編程語(yǔ)言,而Lua是一種基于C語(yǔ)言開(kāi)發(fā)的腳本語(yǔ)言,在Lua的各種實(shí)現(xiàn)中,luajit也是其中一種非常流行的實(shí)現(xiàn),在本文中,我將為大家介紹如何使用C語(yǔ)言調(diào)用luajit,并且詳細(xì)介紹如何傳入?yún)?shù),傳入結(jié)構(gòu)體參數(shù),以及獲取返回值
2023-11-11
C語(yǔ)言實(shí)現(xiàn)掃雷游戲簡(jiǎn)易版
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)掃雷游戲簡(jiǎn)易版，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-11-11
C++實(shí)現(xiàn)商店倉(cāng)庫(kù)管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)商店倉(cāng)庫(kù)管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2022-03-03
總結(jié)UNIX/LINUX下C++程序計(jì)時(shí)的方法
本文總結(jié)了下UNIX/LINUX下C++程序計(jì)時(shí)的一些函數(shù)和方法，對(duì)日常使用C++程序的朋友很有幫助，有需要的小伙伴們可以參考學(xué)習(xí)，下面一起來(lái)看看吧。
2016-08-08