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:06 abilitytao 阅读(158) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理