the 3 ways of iterating a binary tree.

tree.cpp

/*
 * =====================================================================================
 *
 *       Filename:  tree.cpp
 *
 *    Description:  some operations with binary tree
 *
 *        Version:  1.0
 *        Created:  09/29/2013 01:16:19 AM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Ji.Zhilong (), [email protected]
 *   Organization:  SJTU
 *
 * =====================================================================================
 */

#include <iostream>
#include <stack>
#include <queue>
#include <string>
using namespace std;

template <typename T>
class node {
  typedef void (*processor)(T &data);
private:
  node *left;
  node *right;
public:
  T data;
  node(const T& d, node *left=NULL, node *right=NULL): left(left), right(right), data(d) {}

  void pre_order_rec(processor p)
  {
 	if (this == NULL)
	  return;
	p(data);
    left->pre_order_rec(p);
    right->pre_order_rec(p);
  }

  void pre_order_loop(processor p)
  {
	queue<node *> q;
	node *tmp;
	if (this != NULL) q.push(this);

	while (!q.empty()) {
	  tmp = q.front();
	  q.pop();
	  p(tmp->data);
	  if (tmp->left != NULL) q.push(tmp->left);
	  if (tmp->right != NULL) q.push(tmp->right);
	}
  }

  void infix_order_rec(processor p)
  {
	if (this == NULL)
	  return;
	left->infix_order_rec(p);
	p(data);
	right->infix_order_rec(p);
  }

  void infix_order_loop(processor p)
  {
	stack<node *> s;
	node * tmp;
	
	for(tmp = this; tmp != NULL; tmp = tmp->left) s.push(tmp);

	while (!s.empty()) {
	  tmp = s.top();
	  s.pop();
	  p(tmp->data);
	  for(tmp = tmp->right; tmp != NULL; tmp = tmp->left) s.push(tmp);
	}
  }

  void pos_order_rec(processor p)
  {
	if (this == NULL)
	  return;
    left->pos_order_rec(p);
    right->pos_order_rec(p);
	p(data);
  }

  void pos_order_loop(processor p)
  {
	stack<node *> s;
	node *tmp;
	for (tmp = this; tmp != NULL; tmp = tmp->left) {
	  s.push(tmp); s.push(tmp);
	}

	while (!s.empty()) {
	  tmp = s.top();
	  s.pop();
	  if (s.empty() || tmp != s.top()) {
		p(tmp->data);
	  } else {
		for (tmp = tmp->right; tmp != NULL; tmp = tmp->left) {
		  s.push(tmp); s.push(tmp);
		}
	  }
	}
  }

};

template <typename T>
node<T> *t(T data, node<T> *left=NULL, node<T> *right=NULL)
{
  return new node<T>(data, left, right);
}

void print_with_pre_inf(int *pre, int *inf, int len) {
  if (len <= 0)
    return;
  int node = pre[0];
  int i;
  for (i = 0; inf[i] != node; i++);
  print_with_pre_inf(pre + 1, inf, i);
  print_with_pre_inf(&pre[i+1], &inf[i+1], len - i - 1);
  cout << node;
}


template <typename T>
void print(T data)
{
  cout << data << endl;
}

int
main()
{
  node<string> *root = t<string>("root", t<string>("rl"), t<string>("rr", t<string>("rrl")));
  cout << "pre order" << endl;
  root->pre_order_rec(print);
  cout << endl;
  root->pre_order_loop(print);
  cout << endl;
  cout << "infix order" << endl;
  root->infix_order_rec(print);
  cout << endl;
  root->infix_order_loop(print);
  cout << endl;
  cout << "pos order" << endl;
  root->pos_order_rec(print);
  cout << endl;
  root->pos_order_loop(print);
  cout << endl;

  int pre[] = {1,2,4,5,3};
  int inf[] = {4,2,5,1,3};
  print_with_pre_inf(pre, inf, 5);
}