Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A breadth-first tree traversal. #notetoself
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment