数据结构二叉树代码

使用C++模版写的二叉树，适用于C++数据结构的学习参考。

#include 
using namespace std;

template
class TreeNode
{
public:
	TreeNode（）:lson（NULL）rson（NULL）freq（1）{}
	T data;
	unsigned int freq;
	TreeNode *lson;
	TreeNode *rson;
};

template
class BST
{
private:
	TreeNode* root;//根节点
	void insertpri（TreeNode* &nodeT x）;//插入
	TreeNode* findpri（TreeNode* nodeT x）;//查找
	void insubtree（TreeNode* node）;//中序遍历
	void Deletepri（TreeNode* &nodeT x）;//删除
public:
	BST（）:root（NULL）{}//BST构造函数
	void insert（T x）;//插入接口
	TreeNode* find（T x）;//查找接口
	void Delete（T x）;//删除接口
	void traversal（）;//遍历接口
};
/*插入*/
template
void BST::insertpri（TreeNode* &nodeT x）
{
	if（node == NULL）
	{
		node = new TreeNode;
		node->data = x;
		return;
	}
	if（node->data>x）
	{
		insertpri（node->lsonx）;
	}
	else if（node->data	{
		insertpri（node->rsonx）;
	}
	else 
	{
		++（node->freq）;
	}
}
/*插入接口*/
template
void BST::insert（T x）
{
	insertpri（rootx）;
}
/*查找*/
template
TreeNode* BST::findpri（TreeNode* nodeT x）
{
	if（node == NULL）
	{
		return NULL;
	}
	if（node->data>x）
	{
		return findpri（node->lsonx）;
	}
	else if（node->data	{
		return findpri（node->rsonx）;
	}
	else
	{
		return node;
	}
}
/*查找接口*/
template
TreeNode* BST::find（T x）
{
	return findpri（rootx）;
}
/*删除---相当复杂考虑的要比较的全面*/
template
void BST::Deletepri（TreeNode* &nodeT x）
{
	if（node == NULL）//没有找到节点
	{
		return;
	}
	if（node->data>x）//如果x小于节点的值，就继续在节点的左子树中删除
	{
		Deletepri（node->lsonx）;
	}
	else if（node->data	{
		Deletepri（node->rsonx）;
	}
	else//如果节点相等
	{
		if（node->lson&&node->rson）//此节点右两个儿子
		{
			TreeNode* temp = node->rson;//temp指向节点的右儿子
			while（temp->lson!=NULL）//找到右子树中最小的节点
			{
				temp = temp->lson;
			}
			node->data = temp->data;//把右子树中最小的节点赋值给本节点
			node->freq = temp->freq;
			Deletepri（node->rsontemp->data）;//删除右子树中最小值的节点
		}
		else//此节点右1个或0个儿子
		{
			TreeNode* temp = node;
			if（node->lson == NULL）
			{
				node = node->rson;
			}
			else if（node->rson == NULL）
			{
				node = node->lson;
			}
			delete（temp）;
		}
	}
	return;
}
/*删除接口*/
template
void BST::Delete（T x）
{
	Deletepri（rootx）;
}

template
void BST::insubtree（TreeNode* node）
{
	if（node == NULL）
	{
		return;
	}
	insubtree（node->lson）;
	cout<data<<“ “;
	insubtree（node->rson）;
}

template
void BST::traversal（）
{
	insubtree（root）;
}

int main（）
{
	BST bb;
	bb.insert（6）;
	bb.insert（2）;
	bb.insert（7）;
	bb.insert（1）;
	bb.insert（4）;
	bb.insert（3）;
	bb.traversal（）;
	cout<	TreeNode *tree;
	tree = bb.find（6）;
	cout<<“data=“<data<	cout<<“freq=“<freq<	bb.Delete（2）;
	bb.traversal（）;
	cout<}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       3104  2013-02-21 19:56  bst.cpp

----------- ---------  ---------- -----  ----

                 3104                    1