快捷導(dǎo)航

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

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

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

1、先序遍歷二叉樹遞歸實現(xiàn)
思想：若二叉樹為空，返回。否則
1）遍歷根節(jié)點；
2）先序遍歷左子樹；
3）先序遍歷右子樹；

代碼：

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)
思想：二叉樹的非遞歸先序遍歷，先序遍歷思想：先讓根進(jìn)棧，只要棧不為空，就可以做彈出操作，每次彈出一個結(jié)點，記得把它的左右結(jié)點都進(jìn)棧，記得右子樹先進(jìn)棧，這樣可以保證右子樹在棧中總處于左子樹的下面。

前序遍歷二叉樹的非遞歸算法思想
建立棧 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);  
    }  
}  

您可能感興趣的文章:

相關(guān)文章

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