#include<iostream>
using  namespace std;
template <class T>
struct TreeNode
{
T  _data;
TreeNode<T>* _left;
TreeNode<T>* __right;
TreeNode(const T &data=0)
:_data(data),
_left(NULL),
__right(NULL)
{}
};
template<class T>
class BinaryTree
{
typedef TreeNode<T> Node;
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(const T* arr, const int& len, const T& inval)
{
int i = 0;
_root=CreatTree(arr, len, inval, i);
}
void pre_order()
{
_pre_order(_root);
}
void in_order()
{
_in_order(_root);
}
void late_order()
{
_late_order(_root);
}
private:
Node* CreatTree(const T* arr, const int& len, const T& inval, int& i)
{
Node* cur=NULL;
if (arr[i] == inval || i >= len)
{
return cur;
}
cur = new Node(arr[i]);
cur->_left = CreatTree(arr,len,inval,++i);
cur->__right = CreatTree(arr, len, inval, ++i);
return cur;
}
void _pre_order(Node* cur)
{
if (cur == NULL)
{
return;
}
cout << cur->_data << " ";
_pre_order(cur->_left);
_pre_order(cur->__right);
}
void _in_order(Node* cur)
{
if (cur == NULL)
{
return;
}
_pre_order(cur->_left);
cout << cur->_data << " ";
_pre_order(cur->__right);
}
void _late_order(Node* cur)
{
if (cur == NULL)
{
return;
}
_pre_order(cur->_left);
_pre_order(cur->__right);
cout << cur->_data << " ";
}
void _lever_by_lever(Node* cur)
{


}
private:
Node* _root;
};