#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