#include<iostream>

using namespace std;


template<typename T>
//定义树的结点的结构
struct TreeNode{
    T data;
    TreeNode<T>* left;
    TreeNode<T>* right;
    TreeNode(T data) : data(data),left(nullptr),right(nullptr){}
    TreeNode() : data(T()),left(nullptr),right(nullptr){}
};

//定义树类
template<typename T>
class Tree{
    private:
        TreeNode<T>* root;//定义根结点
        TreeNode<T>* nodes;//定义结点池
        size_t size;
        TreeNode<T>* create(T data[],int size,int nodeIndex,T nullNode);
        void preOrder(TreeNode<T>* node);
        void midOrder(TreeNode<T>* node);
        void backOrder(TreeNode<T>* node);
    
    //获取结点地址;获取结点值;Tree类的构造析构;构造一棵树的Create方法; 前,中,后,层序遍历;设置某结点的值
    public:
    Tree();
    Tree(int maxSize);
    ~Tree();
    TreeNode<T>* getNode(int index);
    void visit(TreeNode<T>* node);
    void createTree(T data[],int size,T nullNode);
    void preOrderTraversal();
    void midOrderTraversal();
    void backOrderTraversal();
};

template<typename T>
Tree<T>::Tree(){
    size = 1001;//默认假设有这么多个结点
    nodes = new TreeNode<T>[size];//创造存储这么多个结点的结点池的空间
}

template<typename T>
Tree<T>::Tree(int maxSize){
    size = maxSize;
    nodes = new TreeNode<T>[maxSize];
}

template<typename T>
Tree<T>::~Tree(){
    delete[] nodes;
    size = 0;
}

template<typename T>
TreeNode<T>* Tree<T>::getNode(int index){
    return &nodes[index];
}

template<typename T>
void Tree<T>::visit(TreeNode<T>* node){
 // 忽略空结点的输出
     cout << node->data;

}

template<typename T>
TreeNode<T>* Tree<T>::create(T data[],int size,int nodeIndex,T nullNode){
    if(nodeIndex >= size || data[nodeIndex] == nullNode){
        return nullptr;
    }
    TreeNode<T>* now_node = getNode(nodeIndex);
    now_node->data = data[nodeIndex];
    now_node->left = create(data,size,nodeIndex*2,nullNode);
    now_node->right = create(data,size,nodeIndex*2+1,nullNode);
    return now_node;
}

template<typename T>
void Tree<T>::createTree(T data[],int size,T nullNode){
    root = create(data,size,1,nullNode);
}

template<typename T>
void Tree<T>::preOrder(TreeNode<T>* node){
    if (node == nullptr) {
        return;
    }
    visit(node);
    preOrder(node->left);
    preOrder(node->right);
}

template<typename T>
void Tree<T>::midOrder(TreeNode<T>* node){
    if(node){  
    midOrder(node->left);
    visit(node);
    midOrder(node->right);
    }
}

template<typename T>
void Tree<T>::backOrder(TreeNode<T>* node){
    if (node){
    backOrder(node->left);
    backOrder(node->right);
    visit(node);
    }

}

template<typename T>
void Tree<T>::preOrderTraversal(){
    cout << "前序遍历: ";
    preOrder(root);
}

template<typename T>
void Tree<T>::midOrderTraversal(){
    cout << "中序遍历: ";
    midOrder(root);
}

template<typename T>
void Tree<T>::backOrderTraversal(){
    cout << "后序遍历: ";
    backOrder(root);
}

void test(){
    const char _NULLNODE = '-';
    char data[10] = {_NULLNODE,'a','b','c','d','e',_NULLNODE,'f','g',_NULLNODE};
    Tree<char> tree(9);
    tree.createTree(data,9,_NULLNODE);
    tree.preOrderTraversal();
    tree.midOrderTraversal();
    tree.backOrderTraversal();
}

int main(){
    test();
    return 0;
}