欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

先序遍歷二叉樹(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ù);

代碼:

復(fù)制代碼 代碼如下:

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)文章

最新評(píng)論