template<typename T>
class TreeNode
{
public:
    T val;                //节点值
    TreeNode<T> *left;       //左节点
    TreeNode<T> *right;      //右节点
    TreeNode(T x=0):
        val(x), left(nullptr), right(nullptr){}
    //构造函数 左右节点默认为空
};

template<typename T>
class BinaryTree
{
public:
    void CreateTree(istream &in, TreeNode<T>* &pt);//创建树有很多种方式，先序，中序，后序，按层创建。
    void PreOrder(TreeNode<T> *root);
    void InOrder(TreeNode<T> *root);
    void PostOrder(TreeNode<T> *root);
    vector<vector<T>> LevelOrder(TreeNode<T> *root);
};

template<typename T>
void BinaryTree<T>::CreateTree(istream &in, TreeNode<T>* &pt)
{
    T item;
    if (in >> item){
        if (item == ‘#‘){
            pt = new TreeNode<T>(‘#‘);
        }
        else{
            pt = new TreeNode<T>(item);
            CreateTree(in, pt->left);                 //左节点递归调用
            CreateTree(in, pt->right);                //右节点递归调用
        }
    }
}

//先序递归遍历二叉树
template<typename T>
void BinaryTree<T>::PreOrder(TreeNode<T> *root)
{
    if (root->val == ‘#‘){
        cout << ‘#‘;
        return;
    }
    cout << root->val;
    PreOrder(root->left);
    PreOrder(root->right);
}

//中序递归遍历二叉树
template<typename T>
void BinaryTree<T>::InOrder(TreeNode<T> *root)
{
    if (root->val == ‘#‘){
        cout << "#";
        return;
    }
    InOrder(root->left);
    cout << root->val;
    InOrder(root->right);
}

template<typename T>
void BinaryTree<T>::PostOrder(TreeNode<T> *root)
{
    if (root->val == ‘#‘){
        cout << "#";
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    cout << root->val;
}

template<typename T>
vector<vector<T>> BinaryTree<T>::LevelOrder(TreeNode<T> *root)
{
    TreeNode<T>* last=root;                         //last表示当前层内最右的节点
    TreeNode<T>* nlast=root;                        //nlast表示下一层内最后的节点
    deque<TreeNode<T>*>sup = {root};                //层遍历辅助队列
    TreeNode<T> *top = root;                        //队列的头节点
    vector<vector<T>>vec;
    vector<T>temp;
    vector<vector<T>>::size_type level = 0;
    while (!sup.empty()){                           //队列为空时，按层遍历结束。
        top= sup.front();                           //获取并打印队列首元素
        sup.pop_front();                            //插入完首元素的子节点后，删除该首元素
    //    vec[level].push_back(top->val); 下标操作加入元素要确保初始化时有足够多的元素 
        temp.push_back(top->val);
        if (top->left && (top->left->val)!=‘#‘){    //把将要弹出的节点的非空左节点加入队列
            sup.push_back(top->left);
            nlast =sup.back();                    
        }
        if (top->right && (top->right->val) != ‘#‘){//把将要弹出的节点的非空右节点加入队列
            sup.push_back(top->right);
            nlast = sup.back();                     //nlast始终跟踪加入的尾节点，因为按层遍历，最后加入的元素一定是
                                                    //该行的最右元素
        }
        if (top== last){                            //如果last的值和弹出的值相等 更新last到下一行
            last = nlast;                           //输出完一行时再更新last的值！即更新每一行最右的节点
            vec.push_back(temp);
            temp.clear();
        }
    }
    return vec;
}