// tree.h

class TreeNode {
public:
	// Construtor
	TreeNode(int &d);
	// Nó anterior
	TreeNode *leftPtr;
	// Nó posterior
	TreeNode *rightPtr;

	// Retorna o dado da classe
	int getData() { return data; };

private:
	// Dado da classe
	int data;
};

class Tree {
public:
	// Construtor
	Tree();

	// Insere um nó
	void insertNode(int value);
	// Remove um nó
	void removeNode();
	// Caminha por uma árvore
	void traversal(int flag);

private:
	// Indica a raiz da árvore
	TreeNode *rootPtr;
	void insertNodeHelper(TreeNode *node, int value);
	void traversalHelper(TreeNode *node, int order);

};

enum {
	ORDER_PREFIX = 0,
	ORDER_NORMAL,
	ORDER_POSTFIX,
};

// tree.cpp
#include <stdlib.h>
#include <iostream>
#include "tree.h"


TreeNode::TreeNode(int &d) {
	leftPtr = NULL;
	rightPtr = NULL;
	data = d;
}


Tree::Tree() {
	rootPtr = NULL;
}


void Tree::insertNode(int value) {
	insertNodeHelper(rootPtr, value);
}


void Tree::insertNodeHelper(TreeNode *node, int value) {
	// se a sub-árvore estiver vazia, criamos uma
	if (node == NULL)
		node = new TreeNode(value);
	else {
		// se os dados forem menores que os valores do nó atual
		// colocamos o valor em um node anterior a ele
		if (value < node->getData())
			insertNodeHelper(node->leftPtr, value);
		else if (value > node->getData())
			insertNodeHelper(node->rightPtr, value);
		else
			std::cerr << value << " dup" << std::endl;
	}
}


void Tree::traversal(int flag) {
	traversalHelper(rootPtr, flag);
}


void Tree::traversalHelper(TreeNode *node, int order)
{
	if (node != NULL) {
		if (order == ORDER_PREFIX) {
			std::cout << node->getData() << " ";
			traversalHelper(node->leftPtr, ORDER_PREFIX);
			traversalHelper(node->rightPtr, ORDER_PREFIX);
		}
		else if (order == ORDER_NORMAL) {
			traversalHelper(node->leftPtr, ORDER_NORMAL);
			std::cout << node->getData() << " ";
			traversalHelper(node->rightPtr, ORDER_NORMAL);
		}
		else if (order == ORDER_POSTFIX) {
			std::cout << node->getData() << " ";
			traversalHelper(node->leftPtr, ORDER_POSTFIX);
			traversalHelper(node->rightPtr, ORDER_POSTFIX);
		}
	}
}