BInTree Traversal, C++ (gcc)

BInTree Traversal

//All tree traversal

#include <iostream>
#include <queue>
#include <string>
#include <list>

using namespace std;

struct node {
    int data;
    node* left;
    node* right;
    
    node(int d): data(d), left(NULL), right(NULL) {}
    node(int d, node* l, node* r): data(d), left(l), right(r) {}  
};

void recursivePreorder(node* root) {
    if (!root)
        return;
    
    cout << root->data << " ";
    recursivePreorder(root->left);
    recursivePreorder(root->right);
    
}

void iterativeLevelorder(node* root) {
 
    queue<node*> *cur = new queue<node*>();
    queue<node*> *next = new queue<node*>();
    
    cur->push(root);
    
    while (!cur->empty()) {
     
        node* n = cur->front();
        cur->pop();
        
        cout << n->data << " ";
        
        
        if (n->left)
            next->push(n->left);
        if (n->right)
            next->push(n->right);
        
        
        if (cur->empty()){
            swap(cur, next);
            cout << endl;
        } 
    }
}

void iterativeZigZagorder(node* root) {
 
    list<node*> *cur = new list<node*>();
    list<node*> *next = new list<node*>();
    
    cur->push_back(root);
    
    bool b = false;
    
    while (!cur->empty()) {
     
        node* n = cur->back();
        cur->pop_back();
     
        
        cout << n->data << " ";
        
        
        if (b) {
            if (n->left)
                next->push_back(n->left);
            if (n->right)
                next->push_back(n->right);
        } else {
            if (n->right)
                next->push_back(n->right);
            if (n->left)
                next->push_back(n->left); 
        }
        
        if (cur->empty()){
            swap(cur, next);
            b = !b;
            cout << endl;
        } 
    }
}

//           1
//         /   \
//        2     3   
//       / \   / \   
//      4  5  6   7
//           / \
//          8   9

int main()
{
    node *h = new node(9, NULL, NULL);
    node *j = new node(8, NULL, NULL);
    node *g = new node(7, NULL, NULL);
    node *f = new node(6, j, h);
    node *e = new node(5, NULL, NULL);
    node *d = new node(4, NULL, NULL);
    node *c = new node(3, f, g);
    node *b = new node(2, d, e);
    node *a = new node(1, b, c);
    
    //recursivePreorder(a);
    //iterativeLevelorder(a);
    iterativeZigZagorder(a);
}


run \| edit \| history \| help	0