#include <iostream>

using namespace std;

template <typename DataType>
struct BiNode
{
    DataType data;
    BiNode<DataType> * lchild, * rchild;  // 左右孩子指针
};

template <typename DataType>
class BiTree
{
public:
    BiTree( ){root = Creat();} //构造函数，建立一棵二叉树
    ~BiTree( ){Release(root);} //析构函数，释放各结点的存储空间
    void PreOrder( ){PreOrder(root);}  //前序遍历二叉树
    void InOrder( ){InOrder(root);} //中序遍历二叉树
    void PostOrder( ){PostOrder(root);}  //后序遍历二叉树
    void LevelOrder( ); //层序遍历二叉树
private:
    BiNode<DataType> *Creat(); //构造函数调用
    void Release(BiNode<DataType> *bt);  //析构函数调用
    void PreOrder(BiNode<DataType> *bt); //前序遍历函数调用
    void InOrder(BiNode<DataType> *bt);  //中序遍历函数调用
    void PostOrder(BiNode<DataType> *bt); //后序遍历函数调用
    BiNode<DataType> * root;  //指向根结点的头指针
};

// 利用二叉树的扩展构造二叉树
template <typename DataType>
BiNode<DataType> * BiTree<DataType> :: Creat()
{
    BiNode<DataType> * bt;
    char ch;
    cin >> ch; // 输入结点的数据信息,假设为字符
    if (ch == '#') bt = nullptr;  // 建设一个空树
    else if (ch == '!') return bt;
    else
    {
        bt = new BiNode<DataType>;
        bt->data = ch;
        bt->lchild = Creat(); // 递归建立左子树
        bt->rchild = Creat(); // 递归建立右子树
    }
    return bt;
}

// 析构函数
template <typename DataType>
void BiTree<DataType> :: Release(BiNode<DataType> * bt)
{
    if (bt == nullptr) return; // 递归调用的结束条件
    else
    {
        Release(bt->lchild); // 释放左子树
        Release(bt->rchild); // 释放右子树
        delete bt; // 释放根节点
    }
}

// 前序遍历二叉树
template <typename DataType>
void BiTree<DataType> :: PreOrder(BiNode<DataType> * bt)
{
    if (bt == nullptr) return; // 递归调用的结束条件
    else
    {
        cout << bt->data << "\t"; // 访问根节点bt的数据域
        PreOrder(bt->lchild); // 前序遍历结点bt的左子树
        PreOrder(bt->rchild); // 前序遍历结点bt的右子树
    }
}

// 中序遍历二叉树
template <typename DataType>
void BiTree<DataType> :: InOrder(BiNode<DataType> * bt)
{
    if (bt == nullptr) return; // 递归调用的结束条件
    else
    {
        InOrder(bt->lchild); // 中序遍历结点bt的左子树
        cout << bt->data << "\t"; // 访问根节点bt的数据域
        InOrder(bt->rchild); // 中序遍历结点bt的右子树
    }
}

// 后序遍历二叉树
template <typename DataType>
void BiTree<DataType> :: PostOrder(BiNode<DataType> * bt)
{
    if (bt == nullptr) return; // 递归调用的结束条件
    else
    {
        PostOrder(bt->lchild); // 后序遍历结点bt的左子树
        PostOrder(bt->rchild); // 后序遍历结点bt的右子树
        cout << bt->data << "\t"; // 访问根节点bt的数据域
    }
}

// 层序遍历二叉树
template <typename DataType>
void BiTree<DataType> :: LevelOrder()
{
    BiNode<DataType> * Q[100], *q = nullptr;
    int front = -1, rear = -1; // 队列初始化
    if (root == nullptr) return; // 二叉树为空
    Q[++ rear] = root; // 根指针入队
    while (front != rear) // 当队非空时
    {
        q = Q[++ front]; // 出队
        cout << q->data << "\t";
        if (q->lchild != nullptr) Q[++ rear] = q->lchild;
        if (q->rchild != nullptr) Q[++ rear] = q->rchild;
    }
}

int main()
{
    // 测试输入: a b # d # # c # #
    BiTree<char> T{ }; // 建立一颗树
    cout << "二叉树的前序遍历是 " << endl; 
    T.PreOrder();
    cout << endl;
    cout << "二叉树的中序遍历是 " << endl;
    T.InOrder();
    cout << endl;
    cout << "二叉树的后序遍历是 " << endl; 
    T.PostOrder();
    cout << endl;
    cout << "二叉树的层序遍历是 " << endl; 
    T.LevelOrder();
    cout << endl;
    return 0;
}