A breadth-first tree traversal. #notetoself

bft-test.cpp

#include <iostream>
#include <list>

using namespace std;

struct Node {
	int value;
	list<Node *> children;
};

void visit(Node* node) {
	list<Node *> stack;
	stack.push_front(node);
	for(auto it = stack.rbegin(); it != stack.rend(); ++it) {
		for(auto e : (*it)->children) {
			stack.push_front(e);
		}
	}
	
	for(auto e : stack) {
		cout << e->value << " ";
	}
}

int main(void) {
	Node* root = new Node();
	root->value = 1;
	
	Node* a = new Node();
	a->value = 2;
	Node* b = new Node();
	b->value = 3;
	Node* c = new Node();
	c->value = 4;
	root->children.push_back(a);
	root->children.push_back(b);
	root->children.push_back(c);
	
	Node* d = new Node();
	d->value = 5;
	Node* e = new Node();
	e->value = 6;
	b->children.push_back(d);
	b->children.push_back(e);
	
	Node* g = new Node();
	g->value = 8;
	e->children.push_back(g);
	
	Node* f = new Node();
	f->value = 7;
	c->children.push_back(f);
	
	visit(root);
	
	return 0;
}