二叉树基础模板

#include 

using namespace std;

template
struct Node{
    T data;
    Node *Left, *Right;

    Node(const T &val,Node *Lptr = nullptr, Node *Rptr = nullptr):data(val),Left(Lptr),Right(Rptr){}
};


template
class BiTree
{
    Node *root;
    int len;
public:
    BiTree():root(nullptr),len(0){}
    BiTree(const T &val):root(new Node(val)),len(1){}
    BiTree(const BiTree &tree):root(nullptr),len(0){
        *this = tree;
    }
    ~BiTree(){
        clear();
    }

    void Copy(Node *p,Node * &Np){
        if(!p) return;
        Np = new Node(p->data);
        Copy(p->Left,Np->Left);
        Copy(p->Right,Np->Right);
    }
    BiTree & operator=(const BiTree &tree){
        clear();
        Copy(tree.root,root);
        len = tree.len;
        return *this;
    }


    void clear_dfs(Node *p){
        if(!p) return;//注意跳出
        clear_dfs(p->Left);
        clear_dfs(p->Right);
        delete p;
        len--;
    }
    void clear(){
        clear_dfs(root);
        root = nullptr;//不能忘
    }


    void Revolute_dfs(Node *p){
        if(!p) return;
        Revolute_dfs(p->Left);
        Revolute_dfs(p->Right);
        Node *tmp = p->Left;
        p->Left = p->Right;
        p->Right = tmp;
    }
    void Revolute(){
        Revolute_dfs(root);
    }


    int size()const{
        return len;
    }
    bool empty()const{
        return !len;
    }

    void Leefsize_dfs(Node *p,int &cnt)const{
        if(!p) return;
        Leefsize_dfs(p->Left,cnt);
        Leefsize_dfs(p->Right,cnt);
        if(!p->Left && !p->Right){
            cnt++;
            return;
        }
    }
    int Leefsize()const{
        int cnt = 0;
        Leefsize_dfs(root,cnt);
        return cnt;
    }

    Node *find_dfs(Node *p,const T &val)const{
        if(!p) return nullptr;
        if(p->data == val) return p;
        Node *tmp = nullptr;
        if(tmp = find_dfs(p->Left,val)) return tmp;
        if(tmp = find_dfs(p->Right,val)) return tmp;
        return nullptr;
    }
    Node *find(const T &val)const{
        return find_dfs(root,val);
    }

    int Depth_dfs(Node *p)const{
        if(!p) return 0;
        return max(Depth_dfs(p->Left),Depth_dfs(p->Right))+1;

    }
    int Depth()const{
        return Depth_dfs(root);
    }
    int Depth(const T &val)const{
        return Depth_dfs(find(val));
    }

    Node *Create_dfs(vector &v,T &fin,int &n){//必须引用不然没法累加
        clear();
        T val = v[n++];
        if(val == fin)
            return nullptr;
        else{
            Node *p = new Node(val,Create_dfs(v,fin,n),Create_dfs(v,fin,n));
            len++;
            return p;//记得返回
        }
    }
    void Create(vector &v,T &fin,int n = 0){//设另外个函数把root接上
        root = Create_dfs(v,fin,n);
    }


    void Traverse_dfs(Node *p,vector &v,int mode = 0)const{
        if(!p) return;//递归注意跳出
        if(mode == 0) v.push_back(p->data);
        Traverse_dfs(p->Left,v,mode);
        if(mode == 1) v.push_back(p->data);
        Traverse_dfs(p->Right,v,mode);
        if(mode == 2) v.push_back(p->data);
    }
    void Traverse_fo_uc(Node *p,vector &v)const{
        stack *> s;
        Node *ptr = p;///先判断节点，在入栈，可以在出栈把根节点pop，防止死循环，如果先入栈就会麻烦
        while(ptr || !s.empty()){
            if(ptr){//遍历左树节点
                s.push(ptr);
                v.push_back(ptr->data);
                ptr = ptr->Left;
            }
            else{//转移到右树
                Node *q = s.top();
                s.pop();//踢掉根节点
                ptr = q->Right;
            }
        }
    }
    void Traverse_io_uc(Node *p,vector &v)const{///基本和上面一样
        stack *> s;
        Node *ptr = p;
        while(ptr || !s.empty()){
            if(ptr){//遍历左树节点
                s.push(ptr);
                ptr = ptr->Left;
            }
            else{//转移到右树
                Node *q = s.top();
                s.pop();//踢掉根节点
                v.push_back(q->data);
                ptr = q->Right;
            }
        }
    }
    void Traverse_po_uc(Node *p,vector &v)const{
        stack *> s;
        if(p) s.push(p);
        Node *last = nullptr;
        while(!s.empty()){
            Node *ptr = s.top();
            if(!ptr->Left && !ptr->Right || last && last == ptr->Left && !ptr->Right || last && last == ptr->Right){///叶节点||有左孩子&&上次访问左孩子&&无右孩子||有右孩子&&访问了右孩子
                v.push_back(ptr->data);
                last = ptr;
                s.pop();
            }
            else{
                if(ptr->Right) s.push(ptr->Right);
                if(ptr->Left) s.push(ptr->Left);
            }
        }
    }
    void Traverse_bfs(Node *p,vector &v)const{
        queue *> q;
        q.push(p);
        while(!q.empty()){
            v.push_back(q.front()->data);
            if(q.front()->Left) q.push(q.front()->Left);
            if(q.front()->Right) q.push(q.front()->Right);
            q.pop();
        }
    }

    void Traverse(vector &v,int mode = 0)const{
        if(mode<=2) Traverse_dfs(root,v,mode);
        else if(mode == 3) Traverse_fo_uc(root,v);
        else if(mode == 4) Traverse_io_uc(root,v);
        else if(mode == 5) Traverse_po_uc(root,v);
        else if(mode == 6) Traverse_bfs(root,v);
    }
    void write(int mode = 0)const{
        vector v;
        Traverse(v,mode);
        for(int i = 0;i v;
    while(ss>>tmp,v.push_back(tmp),ss.get() == ' ');
    ss.str("");
    ss.clear();



    BiTree tree;
    tree.Create(v,fin);

    for(int i = 0;i<=6;i++){
        tree.write(i);
    }

    cout< tree2 = tree;
    tree.clear();
    cout<