# The Fourth Dimension Space

## 排序二叉树BST(beta 2.0)

#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
<T> *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
<T> *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(root,n);
}

template
<class T>
TreeNode
<T>* Tree<T>::SearchHelper(TreeNode<T> *tree,T key)
{

if(tree==NULL||key==tree->data)

return tree;

else

if(key<tree->data)

return SearchHelper(tree->lchild,key);

else

return SearchHelper(tree->rchild,key);
}

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()
{

int arr[]={5,4,8,1,9,7,6,2,12,11,10,3};

int i;
Tree
<int> test;

for(i=0;i<sizeof(arr)/sizeof(int);i++)

{
test.InsertNode(arr[i]);
}

TreeNode
<int> *p=test.SearchNode(4);

test.Print();
cout
<<endl;

bool temp;

for(i=12;i>=0;i--)

{
temp
=test.DeleteNode(i);
test.Print();
cout
<<endl;
}

return 0;

}

posted on 2009-05-24 15:36 abilitytao 阅读(1206) 评论(0)  编辑 收藏 引用