模板实现二叉树的增删查改和遍历

#pragma once   //Tree.h
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<list>//队列  队尾插入  队头删除  
struct node
{
    struct node *lchild, *rchild, *father;
    int data;
};
template<class T>
class Tree
{
private:
    node *root;
public:
    Tree();
    ~Tree();
    void insert(T data);
    node* findNode(int data);
    void preOrder(node *p);//先序遍历
    void inOrder(node* p);
    void lasOrder(node* p);
    void clear(node* p);
    node* getRoot();
    void leverOrder();
    void deleByData(int data);
};
template<class T>
Tree<T>::Tree() :root(nullptr){}

template<class T>
Tree<T>::~Tree()
{
    clear(root);
    root = nullptr;
}
template<class T>
void Tree<T>::insert(T data)
{
    if (nullptr == root)//判断是否空树
    {
        root = new node;
        root->data = data;
        root->lchild = root->rchild = root->father = nullptr;
    }
    else
    {
        node *p = root;
        while (true)
        {
            if (p->data <= data)
            {
                if (nullptr == p->rchild)
                {
                    p->rchild = new node;
                    p->rchild->lchild = p->rchild->rchild = nullptr;
                    p->rchild->father = p->rchild;
                    p->rchild->data = data;
                    break;
                }
                p = p->rchild;
            }
            else
            {
                if (nullptr == p->lchild)
                {
                    p->lchild = new node;
                    p->lchild->lchild = p->lchild->rchild = nullptr;
                    p->lchild->data = data;
                    p->lchild->father = p->lchild;
                    break;
                }
                p = p->lchild;
            }
        }
    }
}

template<class T>
node * Tree<T>::findNode(int data)
{
    node * p = root;
    while (nullptr != p)
    {
        if (p->data == data)
            break;
        else if (p->data < data)
            p = p->rchild;
        else p = p->lchild;

    }
    return p;


}


template<class T>
void Tree<T>::preOrder(node* p)
{
    if (nullptr != p)
    {
        std::cout << p->data << '\t';
        preOrder(p->lchild);
        preOrder(p->rchild);

    }

}
template<class T>
void Tree<T>::inOrder(node*p)//中序遍历
{
    if (p != nullptr)
    {
        inOrder(p->lchild);
        std::cout << p->data << '\t';
        inOrder(p->rchild);
    }
}

template<class T>
void Tree<T>::lasOrder(node*p)
{
    if (p != nullptr)
    {
        lasOrder(p->lchild);
        lasOrder(p->rchild);
        std::cout << p->data << '\t';
    }
}

template<class T>
void Tree<T>::clear(node*p)
{
    if (p != nullptr)
    {
        clear(p->lchild);
        clear(p->rchild);
        delete p;
    }
}

template<class T>
node* Tree<T>::getRoot()
{
    return root;
}


template<class T>
void Tree<T>::leverOrder()
{
    using std::list;
    list<node*>lis;
    lis.push_back(root);
    node*p;
    while (lis.empty() == 0)//lis不空
    {
        p = lis.front();//得到队头元素
        if (nullptr!=p)
        {
            lis.push_back(p->lchild);
            lis.push_back(p->rchild);
            std::cout << p->data << '\t';
        }
        lis.pop_front();//出队
    }
}

template<class T>
void Tree<T>::deleByData(int data)
{
    node*p = findNode(data);//查找要删除的节点
    if (p == nullptr) return;
    else if (p == root)//要删除的是根节点
    {
        if (root->lchild == nullptr&&root->rchild == nullptr)//只有一个节点
        {
            delete root;//直接删除
            root = nullptr;
        }
        else if (root->lchild == nullptr)//左边为空  右边不为空
        {
            root = root->rchild;
            delete p;//释放节点
        }
        else if (root->rchild == nullptr)//右边为空  左边不为空
        {
            root = root->lchild;
            delete p;//释放节点
        }
        else
        {
            node*q = root->lchild;
            while (q->rchild != nullptr)
            {
                q = q->rchild;//继续往右找
            }

            q->father->rchild = nullptr;
            q->father = root->father;
            q->lchild = root->lchild;
            q->rchild = root->rchild;
            root = q;//新的根节点
            delete p;//释放之前的根节点
        }
    }

}