#include<iostream>
using namespace std;

template<typename T>
struct TreeNode {
	T val;//结点值
	TreeNode* left;//左结点
	TreeNode* right;//右结点
	TreeNode() :val(0), left(NULL), right(NULL) {}
	TreeNode(T x) :val(x), left(NULL), right(NULL) {}
};
template<typename T>
class Tree {
private:
	TreeNode<T>* nodes;//所有结点的结点池（存储树里的所有节点）
	TreeNode<T>* root;//根结点
	size_t nodeSize;//总共有多少结点

	TreeNode<T>* Create(T a[], int size, int nodeId, T nullNode);//创建这棵树

	void visit(TreeNode<T>* node);//遍历时访问单个结点要做的事情
	void preOrder(TreeNode<T>* node);//前序遍历
	void inOrder(TreeNode<T>* node);//中序遍历
	void postOrder(TreeNode<T>* node);//后序遍历
public:
	Tree();
	Tree(int maxNodes);
	~Tree();
	TreeNode<T>* GetTreeNode(int id);//通过id获取到结点对应的地址
	void CreateTree(T a[], int size, T nullNode);//创建树
	void preOrderTraversal();//前序遍历
	void inOrderTraversal();//中序遍历
	void postOrderTraversal();//后序遍历
};
template<typename T>
Tree<T>::Tree() {
	nodeSize = 100001;
	nodes = new TreeNode<T>[nodeSize];
}
template<typename T>
Tree<T>::Tree(int maxNodes) {
	nodes = new TreeNode<T>[maxNodes];
}
template<typename T>
Tree<T>::~Tree() {
	delete[] nodes;
}
template<typename T>
TreeNode<T>* Tree<T>::GetTreeNode(int id) {
	return &nodes[id];
}
//为了方便调试，定义一个visit打印
template<typename T>
void Tree<T>::visit(TreeNode<T>* node) {
	cout << node->val;
}

template<typename T>
void Tree<T>::preOrder(TreeNode<T>* node) {
	if (node) {
		//如果node不为空则打印出来，先访问左子树，在访问右子树
		visit(node);
		preOrder(node->left);
		preOrder(node->right);
	}
}
template<typename T>
void Tree<T>::inOrder(TreeNode<T>* node) {
	//先访问左子树，在访问根节点，在访问右子树
	if (node) {
		inOrder(node->left);
		visit(node);
		inOrder(node->right);
	}
}
template<typename T>
void Tree<T>::postOrder(TreeNode<T>* node) {
	//先访问左子树，在访问右子树，在访问根节点
	if (node) {
		inOrder(node->left);
		inOrder(node->right);
		visit(node);	
	}
}
template<typename T>
TreeNode<T>* Tree<T>::Create(T a[], int size, int nodeId, T nullNode) {
	if (nodeId >= size || a[nodeId] == nullNode) {
		return NULL;
	}
	TreeNode<T>* newNode = GetTreeNode(nodeId);
	newNode->val = a[nodeId];
	newNode->left = Create(a, size, nodeId * 2, nullNode);
	newNode->right = Create(a, size, nodeId * 2 + 1, nullNode);
	return newNode;
}
template<typename T>
void Tree<T>::CreateTree(T a[], int size, T nullNode) {
	root = Create(a, size, 1, nullNode);
}
template<typename T>
void Tree<T>::preOrderTraversal() {
	preOrder(root);
}
template<typename T>
void Tree<T>::inOrderTraversal() {
	inOrder(root);
}
template<typename T>
void Tree<T>::postOrderTraversal() {
	postOrder(root);
}
int main() {
	const char nullNode = '-';
	char a[16] = {
		nullNode,'a','b','c','d',
		nullNode,'e','f','g','h',
		nullNode,nullNode,nullNode,nullNode,'i',
	};
	Tree<char>T(15);
	T.CreateTree(a, 15, nullNode);
	T.preOrderTraversal();
	cout << endl;
	T.inOrderTraversal();
	cout << endl;
	T.postOrderTraversal();
	cout << endl;
	return 0;
}