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

2020-01-26 15:57:13

字體：大中小

供稿：網(wǎng)友

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