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

#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;//释放之前的根节点
		}
	}
 
}

//mian.cpp 

#include"Tree.h"
int main()
{
	srand((unsigned)time(NULL));
	Tree<char> mytree;
	for (int i = 0; i < 10; ++i)
	{
		mytree.insert(rand() % 100);
	}
	std::cout << "前序遍历"<< std::endl;
	mytree.preOrder(mytree.getRoot());
	std::cout << std::endl;
	std::cout << "中序遍历" << std::endl;
	mytree.inOrder(mytree.getRoot());
	std::cout << std::endl;
	std::cout << "后序遍历" << std::endl;
	mytree.lasOrder(mytree.getRoot());
	std::cout << std::endl;
	std::cout << "层次遍历" << std::endl;
	mytree.leverOrder();
	std::cout << std::endl;
	std::cin.get();
	return 0;
}