広さ優先

  
  
  
  

   
   
   
   
#include <iostream> 
   
   
   
   
#include <stdio.h> 
   
   
   
   
#include <queue> 

   
   
   
   
using namespace std; 
   
   
   
   
 
   
   
   
   
struct node  
   
   
   
   
{ 
   
   
   
   
    int self; //    
   
   
   
   
    node *left; //     
   
   
   
   
    node *right; //     
   
   
   
   
 }; 
   
   
   
   
 
   
   
   
   
void main() 
   
   
   
   
{ 
   
   
   
   
    const int TREE_SIZE = 9; 
   
   
   
   
    std::queue <node*> visited, unvisited; 
   
   
   
   
    node nodes[TREE_SIZE];  
   
   
   
   
    node* current; 
   
   
   
   
    for( int i=0; i<TREE_SIZE; i++) //     
   
   
   
   
    { 
   
   
   
   
        nodes[i].self = i; 
   
   
   
   
        int child = i*2+1; 
   
   
   
   
        if( child<TREE_SIZE ) //Left child 
   
   
   
   
            nodes[i].left = &nodes[child]; 
   
   
   
   
        else 
   
   
   
   
            nodes[i].left = NULL; 
   
   
   
   
        child++; 
   
   
   
   
        if( child<TREE_SIZE ) //Right child     
   
   
   
   
            nodes[i].right = &nodes[child]; 
   
   
   
   
        else 
   
   
   
   
            nodes[i].right = NULL; 
   
   
   
   
    }            
   
   
   
   
     
   
   
   
   
    unvisited.push(&nodes[0]); //  0  UNVISITED stack 
   
   
   
   
     
   
   
   
   
    while(!unvisited.empty()) //  UNVISITED   
   
   
   
   
         
   
   
   
   
    { 
   
   
   
   
        current=(unvisited.front()); //        
   
   
   
   
        unvisited.pop();  
   
   
   
   
         
   
   
   
   
        if(current->left!=NULL)  
   
   
   
   
            unvisited.push(current->left); 
   
   
   
   
 
   
   
   
   
        if(current->right!=NULL)  
   
   
   
   
            unvisited.push(current->right);   
   
   
   
   
         
   
   
   
   
     
   
   
   
   
         
   
   
   
   
        visited.push(current); 
   
   
   
   
         
   
   
   
   
        cout<<current->self<<endl; 
   
   
   
   
        //if (current->self==7) return; 
   
   
   
   
         
   
   
   
   
 } 
   
   
   
   
}