BinTraversal v2, C++ (gcc)

BinTraversal v2

//Title of this code

#include <iostream>
#include <list>
using namespace std;

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

void post_order_recursive(BinTree *root) {
    if (root != NULL) {
        post_order_recursive(root->left);
        post_order_recursive(root->right);
        cout << root->data << " ";
    }     
}

void pre_order_recursive(BinTree *root) {
    if (root != NULL) {
        cout << root->data << " ";
        post_order_recursive(root->left);
        post_order_recursive(root->right);
    }     
}

void post_order_traversal(BinTree *root) {

list<BinTree*> stack;
    BinTree *current = root;
    BinTree *head;

do {

if (!stack.empty())
            head = stack.front();
        else
            head = NULL;
        
        if (current->left && current != head) {
            stack.push_front(current);
            current = current->left;
            continue;
        } 
        
        if (current->right && current != head) {
            stack.push_front(current);
            current = current->right;
            continue;
        } 
        
        if (current == head) {
            stack.pop_front();
        }
        
        // operate on leaf
        cout << current->data << " ";
        
        // go through children
        if (stack.front()->right == current || !stack.front()->right)
            current = stack.front(); // jump up
        else if (stack.front()->right)
            current = stack.front()->right;  // next child

} while (!stack.empty());
    
    
    
}

int main()
{
    BinTree *j = new BinTree(9, NULL, NULL);
    BinTree *h = new BinTree(8, NULL, NULL);
    BinTree *g = new BinTree(7, NULL, NULL);
    BinTree *f = new BinTree(6, h, j);
    BinTree *e = new BinTree(5, NULL, NULL);
    BinTree *d = new BinTree(4, NULL, NULL);
    BinTree *c = new BinTree(3, f, g);
    BinTree *b = new BinTree(2, d, e);
    BinTree *a = new BinTree(1, b, c);
    
    post_order_traversal(a);
    cout << endl;
    post_order_recursive(a);
    cout << endl;
    pre_order_recursive(a);

}


run \| edit \| history \| help	0

Please log in to post a comment.