程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> C語言基礎知識 >> 先序遍歷二叉樹的遞歸實現與非遞歸實現深入解析

先序遍歷二叉樹的遞歸實現與非遞歸實現深入解析

編輯:C語言基礎知識

1、先序遍歷二叉樹  遞歸實現
思想:若二叉樹為空,返回。否則
1)遍歷根節點;
2)先序遍歷左子樹;
3)先序遍歷右子樹;

代碼:
代碼如下:

template<typename elemType>
void PreOrder(nodeType<elemType> *root) 

    if(root==NULL) 
        return ; 
    visit(root->data); // visit the data
    PreOrder(root->lchild); //遞歸調用,先序遍歷左子樹 
    PreOrder(root->rchild); //遞歸調用,先序遍歷右子樹 


2、先序遍歷二叉樹 非遞歸實現
思想:二叉樹的非遞歸先序遍歷,先序遍歷思想:先讓根進棧,只要棧不為空,就可以做彈出操作, 每次彈出一個結點,記得把它的左右結點都進棧,記得右子樹先進棧,這樣可以保證右子樹在棧中總處於左子樹的下面。

前序遍歷二叉樹的非遞歸算法思想
建立棧 Stack;
t 指向根;
當 t 不空 或 Stack 不空時反復做:
      若 t 不空,訪問t,t 入 棧;t 指向左子女;
      否則:出棧頂元素到 t 中;
      t 指向右子女;
結束
代碼如下:

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved