Binary Tree Iterators

binary_tree_iterators.cpp

#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;
}