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 阅读(1381) 评论(1)  编辑 收藏 引用

评论

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

写得不错  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理