The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

神奇的二叉排序树

//////////////////////////////////////////////////////////////////////////
//
//                            BINARY_SORT_TREE 
//                                            GET_GUIDANCE_BY_MR_ZHANGHONG
//                                            2009年4月21日0:05:22    
//    
//////////////////////////////////////////////////////////////////////////
#include<iostream>
#include<cmath>
#include<cassert>
#include<algorithm>
#include<cstdio>
using namespace std;

struct node 
{
    int data;
    node *lchild;
    node *rchild;
};

template<class T>
void InsertBST(node *&tree,T key)
{
    if(tree==NULL)
    {

        tree=new node;
        tree->lchild=tree->rchild=NULL;
        tree->data=key;
        return;
    }
    if(key<tree->data)
    {
        InsertBST(tree->lchild,key);
    }
    else
    {

        InsertBST(tree->rchild,key);
    }
}
template<class T>
////////////////////////////////////////////////////
node *SearchBST(node *tree,T key)
{

    if(tree==NULL||key==tree->data)
        return tree;
    else 
        if(key<tree->data)
            return SearchBST(tree->lchild,key);
        else
            return SearchBST(tree->rchild,key);
}//SearchBST


int  delete_node(node *&p)//0代表删除不成功，1代表删除成功
{ 
    node *q;
    node *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  DeleteBST(node *&tree,T key)
{

    if(tree==NULL)
        return false;
    else if(tree->data==key)
    {

        delete_node(tree);
        return true;
    }
    else if(tree->data>key)
    {

        DeleteBST(tree->lchild,key);

    }
    else DeleteBST(tree->rchild,key);
}
/*由于需要将进行删除操作后的子树和父亲结点连起来
  我认为需要用上面这个函数来完成查找+删除功能,而
  不能先调用Search函数然后再调用DeleteBST函数!*/
//////////////////////////////////////////////////////////////////////////


void print(node *tree)
{

    if(tree==NULL)
        return;
    print(tree->lchild);
    cout<<tree->data<<' ';
    print(tree->rchild);
}



int main()
{

    int arr[]={5,4,8,1,9,7,6,2,12,11,10,3};
    int i;
    node *tree=NULL;
    for(i=0;i<sizeof(arr)/sizeof(int);i++)
    {
        InsertBST(tree,arr[i]);
    }
    print(tree);
    cout<<endl;
    bool test;
    for(i=12;i>=0;i--)
    {
        test=DeleteBST(tree,i);
        print(tree);
        cout<<endl;
    }
    return 0;

}



posted on 2009-04-21 00:58 abilitytao 阅读(1475) 评论(1)  编辑 收藏 引用

评论

# re: 神奇的二叉排序树 2009-04-21 11:59 true

写得不错  回复  更多评论   


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