#include <iostream>
#include <stack>
#include <cassert>
using namespace std;

struct node
{
  node* lchild;
  node* rchild;
  int key;
  node(int data=0, node* left=NULL, node* right=NULL)
  {
    key = data;
    lchild = left;
    rchild = right;
  }
};

class Tree
{
  
public:
  Tree()
  {
    root = NULL;
  }
  Tree(int array[], int size);
  ~Tree();
  void traverse();
  void postTraverse();
  void recur_postTraverse(node* cur);
  void preTraverse();
  void recur_preTraverse(node* cur);
  void inTraverse();
  void recur_inTraverse(node* cur);

private:
  Tree(const Tree& t);
  Tree& operator=(const Tree& t);
  node* createTree(int array[], int size);
  void destroyTree(node* cur);
private:
  node* root;
  
};

Tree::Tree(int array[], int size)
{
  if ((array==NULL)||(size<=0))
    root = NULL;
  else
    root = createTree(array, size);
}

node* Tree::createTree(int array[], int size)
{
  if ((array==NULL)||(size<=0))
    return NULL;
  int mid=size/2;
  node* cur=new node(array[mid]);
  cur->lchild = createTree(array, mid);
  cur->rchild = createTree(array+mid+1, size-mid-1);
  return cur;
}

Tree::~Tree()
{
  destroyTree(root);
}

void Tree::destroyTree(node* cur)
{
  if (cur != NULL)
  {
    destroyTree(cur->lchild);
    destroyTree(cur->rchild);
    delete cur;
  }
  
}


//后序递归遍历

void Tree::recur_postTraverse(node* cur)
{
  if (cur!=NULL)
  {
    recur_postTraverse(cur->lchild);
    recur_postTraverse(cur->rchild);
    cout << cur->key << " ";
  }
}

//先序递归遍历

void Tree::recur_preTraverse(node* cur)
{
  if (cur!=NULL)
  {
    cout << cur->key << " ";
    recur_preTraverse(cur->lchild);
    recur_preTraverse(cur->rchild);
  }
}

//中序递归遍历

void Tree::recur_inTraverse(node* cur)
{
  if (cur!=NULL)
  {
    recur_inTraverse(cur->lchild);
    cout << cur->key << " ";
    recur_inTraverse(cur->rchild);
  }
}

//后序非递归遍历

void Tree::postTraverse()
{
  stack<node*> treeStack;
  node *pre, *cur;
  cur = root;
  pre = NULL;
  
  if (cur!=NULL)
    treeStack.push(cur);
  
  while(!treeStack.empty())
  {
    cur = treeStack.top();
    if (((cur->lchild==NULL)&&(cur->rchild==NULL))|| //没有孩子结点或者

        ((pre!=NULL)&&((pre==cur->lchild)||(pre==cur->rchild)))) //孩子遍历过了

    {
      treeStack.pop();
      cout << cur->key << " ";
      pre = cur;
    }
    else
    {
      if (cur->rchild!=NULL)
        treeStack.push(cur->rchild);
      if (cur->lchild!=NULL)
        treeStack.push(cur->lchild);
    }
   
  }
  
}

//中序非递归遍历

void Tree::inTraverse()
{
  stack<node*> treeStack;
  node *pre, *cur;
  cur = root;
  
  if (cur!=NULL)
    treeStack.push(cur);
  
  while(!treeStack.empty())
  {
    cur = treeStack.top();
    treeStack.pop();
    if (cur == NULL)
      continue;
    if ((cur->lchild==NULL)|| //没有左孩子或者

        ((!treeStack.empty())&&(treeStack.top()==cur->rchild))) //右孩子已经入过栈

      cout << cur->key << " ";
    else
    {
      treeStack.push(cur->rchild);
      treeStack.push(cur);
      if (cur->lchild!=NULL)
        treeStack.push(cur->lchild);
    }
   
  }
}

//先序非递归遍历

void Tree::preTraverse()
{
  stack<node*> treeStack;
  node *pre, *cur;
  cur = root;
  
  if (cur!=NULL)
    treeStack.push(cur);
  
  while(!treeStack.empty())
  {
    cur = treeStack.top();
    treeStack.pop();
    cout << cur->key << " ";
    if (cur->rchild!=NULL)
      treeStack.push(cur->rchild);
    if (cur->lchild!=NULL)
      treeStack.push(cur->lchild);
  }
}


void Tree::traverse()
{
  recur_preTraverse(root);
  cout << endl;
  preTraverse();
  cout << endl << endl;

  recur_inTraverse(root);
  cout << endl;
  inTraverse();
  cout << endl << endl;
  
  recur_postTraverse(root);
  cout << endl;
  postTraverse();
  cout << endl << endl;
}

int main(int argc, char* argv[])
{
  int array[] = {2, 4, 5, 6, 8, 10, 11, 13, 15, 17, 20};
  Tree tr(array, sizeof(array)/sizeof(array[0]));
  tr.traverse();
}