#include <iostream>
#include<algorithm>
#include<cmath>
using namespace std;
/**//////////////////////BEGIN_TEMPLATE_BALANCE_SORT_TREE_BY_ABILITYTAO_ACM/////////////////////////////template< class T > class Tree;
template< class T >
class TreeNode
{
friend class Tree< T >;
public:
TreeNode(T d ):lchild( NULL ), data( d ),rchild( NULL )
{ }
T getData() const
{
return data;
}
private:
TreeNode< T > *lchild;
T data;
TreeNode< T > *rchild;
};
template <class T>
class Tree
{
private:
TreeNode<T> *root;
void InsertNodeHelper(TreeNode<T> *&tree,T key);
TreeNode *SearchHelper(TreeNode<T> *tree,T key);
int DeleteNodeHelper(TreeNode<T> *&p);
bool DeleteNodeHelper2(TreeNode<T> *&tree,T key);
void PrintHelper(TreeNode<T> *tree);
public:
Tree();
void InsertNode(T n);
TreeNode *SearchNode(T n);
bool DeleteNode(T n);
void Print();
bool IsEmpty();
};
template<class T>
Tree<T>::Tree()
{
root=NULL;
}
template<class T>
void Tree<T>::InsertNodeHelper(TreeNode<T> *&tree,T key)
{
if(tree==NULL)
{
tree=new TreeNode<T>(0);
tree->lchild=tree->rchild=NULL;
tree->data=key;
return;
}
if(key<tree->data)
{
InsertNodeHelper(tree->lchild,key);
}
else
{
InsertNodeHelper(tree->rchild,key);
}
}
template<class T>
void Tree<T>::InsertNode(T n)
{
InsertNodeHelper(root,n);
}
template<class T>
TreeNode<T>* Tree<T>::SearchNode(T n)
{
return SearchHelper(TreeNode<T> root,T n);
}
template<class T>
int Tree<T>::DeleteNodeHelper(TreeNode<T> *&p)//0代表删除不成功，1代表删除成功
{
TreeNode<T> *q;
TreeNode<T> *s;
if(p==NULL)
return 0;
if(p->rchild==NULL)
{
q=p;
p=p->lchild;
delete q;
}
else if(p->lchild==NULL)
{
q=p;
p=p->rchild;
delete q;
}
else
{
q=p;
s=p->lchild;
while(s->rchild!=NULL)
{
q=s;
s=s->rchild;
}
p->data=s->data;
if(q!=p)
q->rchild=s->lchild;
else
q->lchild=s->lchild;//注意这个if else 语句 ，这是精髓
delete s;
}
}
template<class T>
bool Tree<T>::DeleteNodeHelper2(TreeNode<T> *&tree,T key)
{
if(tree==NULL)
return false;
else if(tree->data==key)
{
DeleteNodeHelper(tree);
return true;
}
else if(tree->data>key)
{
DeleteNodeHelper2(tree->lchild,key);
}
else DeleteNodeHelper2(tree->rchild,key);
}
/**//*************************************************/
/**//*由于需要将进行删除操作后的子树和父亲结点连起来
/*我认为需要用上面这个函数来完成查找+删除功能,而
/*不能先调用Search函数然后再调用DeleteBST函数!
/*************************************************/
template<class T>
bool Tree<T>::DeleteNode(T n)
{
bool temp;
temp=DeleteNodeHelper2(root,n);
return temp;
}
template<class T>
void Tree<T>::PrintHelper(TreeNode<T> *tree)
{
if(tree==NULL)
return;
PrintHelper(tree->lchild);
cout<<tree->data<<' ';
PrintHelper(tree->rchild);
}
template<class T>
void Tree<T>::Print()
{
PrintHelper(root);
}
template<class T>
bool Tree<T>::IsEmpty()
{
return root==NULL;
}
/**//////////////////////////END_TEMPLATA_BY_ABILITYTAO_ACM///////////////////////////////////
int main()
{
double arr[]={5,4,8,1,9,7,6,2,12,11,10,3};
int i;
Tree<double> test;
for(i=0;i<sizeof(arr)/sizeof(double);i++)
{
test.InsertNode(arr[i]);
}
test.Print();
cout<<endl;
bool temp;
for(i=12;i>=0;i--)
{
temp=test.DeleteNode(i);
test.Print();
cout<<endl;
}
return 0;
}
刚写的，能过自己的测试数据，如果方便的话，希望大家能帮我测试一下。