Skip to content

Instantly share code, notes, and snippets.

@zahlenteufel
Created July 8, 2015 16:20
Show Gist options
  • Save zahlenteufel/d661e5b22d6c3ecc4cab to your computer and use it in GitHub Desktop.
Save zahlenteufel/d661e5b22d6c3ecc4cab to your computer and use it in GitHub Desktop.
Binary Tree Iterators
#include <iostream>
#include <cassert>
using namespace std;
struct node {
int value;
node* left;
node* right;
node *parent;
node(int value, node* left, node* right) {
this->value = value;
this->parent = NULL;
this->left = left;
if (left)
left->parent = this;
this->right = right;
if (right)
right->parent = this;
}
~node() {
delete this->left;
delete this->right;
}
};
node* bin(int v, node* left, node* right) {
return new node(v, left, right);
}
node* leaf(int v) {
return bin(v, NULL, NULL);
}
void visit(node* n) {
cout << n->value << endl;
}
node* bottomleft(node* n) {
while (n->left)
n = n->left;
return n;
}
class Traversal {
public:
static node* first(node*) {};
static node* next(node*) {};
};
class Preorder : public Traversal {
public:
static node* first(node* n) {
return n;
}
static node* next(node* n) {
assert(n);
if (n->left)
return n->left;
if (n->right)
return n->right;
while (n->parent && n->parent->right == n)
n = n->parent;
if (!n->parent) // root
return NULL;
else
return n->parent->right;
}
};
class Inorder : public Traversal {
public:
static node* first(node* n) {
if (n)
return bottomleft(n);
else
return NULL;
}
static node* next(node* n) {
assert(n);
if (n->right)
return bottomleft(n->right);
while (n->parent && n->parent->right == n)
n = n->parent;
return n->parent;
}
};
class Postorder : public Traversal {
public:
static node* first(node* n) {
if (!n)
return NULL;
while (n->left || n->right) {
if (n->left)
n = n->left;
else
n = n->right;
}
return n;
}
static node* next(node* n) {
assert(n);
if (n->parent == NULL || n->parent->right == n)
return n->parent;
n = n->parent;
if (n->right)
n = bottomleft(n->right);
return n;
}
};
template<class T>
class iter
{
private:
node* _current;
public:
iter(node* n) {
_current = T::first(n);
}
void advance() {
_current = T::next(_current);
}
node* current() {
return _current;
}
};
int main() {
node* a = bin(3, bin(1, NULL, leaf(2)), bin(5, leaf(4), leaf(6)));
iter<Inorder> it(a);
while (it.current() != NULL) {
visit(it.current());
it.advance();
}
delete a;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment