随笔 - 87  文章 - 279  trackbacks - 0
<2024年12月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214823
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

#include  < iostream >
using   namespace  std;

template 
< class  T >
struct  BSTreeNode
{
    T info;
    BSTreeNode 
* ls;
    BSTreeNode 
* rs;
}
;

template 
< class  T >
class  BSTree
{
public :
    BSTree();
    
bool  insert(T key);
    
bool  find(T key);
    
void  travel();
    
int  size();
private :
    
bool  insert_inner(BSTreeNode < T >   *& root, BSTreeNode < T >   * p);
    
bool  find_inner(BSTreeNode < T >   * root, T key);
    
void  travel_inner(BSTreeNode < T >   * root);
    BSTreeNode
< T >   * root;
    
int  _size;
}
;

template 
< class  T >
BSTree
< T > ::BSTree()
{
    root 
=  NULL;
    _size 
=   0 ;
}


template 
< class  T >
bool  BSTree < T > ::insert(T key)
{
    BSTreeNode
< T >   * =   new  BSTreeNode < T > ;
    p
-> info  =  key;
    p
-> ls  =  NULL;
    p
-> rs  =  NULL;
    
if  (insert_inner(root, p))
        
return   true ;
    
else
        
return   false ;
}


template 
< class  T >
bool  BSTree < T > ::insert_inner(BSTreeNode < T >   *& root, BSTreeNode < T >   * p)
{
    
if  (root  ==  NULL)
    
{
        root 
=  p;
        _size
++ ;
        
return   true ;
    }


    
if  (root -> info  ==  p -> info)
        
return   false ;

    
if  (p -> info  <  root -> info)
        insert_inner(root
-> ls, p);
    
else
        insert_inner(root
-> rs, p);
}


template 
< class  T >
bool  BSTree < T > ::find(T key)
{
    
if  (find_inner(root, key))
        
return   true ;
    
else
        
return   false ;
}


template 
< class  T >
bool  BSTree < T > ::find_inner(BSTreeNode < T >   * root, T key)
{
    
if  (root  ==  NULL)
        
return   false ;

    
if  (root -> info  ==  key)
        
return   true ;

    
if  (key  <  root -> info)
        find_inner(root
-> ls, key);
    
else
        find_inner(root
-> rs, key);
}


template 
< class  T >
int  BSTree < T > ::size()
{
    
return  _size;
}


template 
< class  T >
void  BSTree < T > ::travel()
{
    travel_inner(root);
}


template 
< class  T >
void  BSTree < T > ::travel_inner(BSTreeNode < T >   * root)
{
    
if  (root  ==  NULL)  return  ;
    travel_inner(root
-> ls);
    cout 
<<  root -> info  <<  endl;
    travel_inner(root
-> rs);
}



int  main()
{
    BSTree
< int >  bst;
    
int  a[]  =   { 3 2 5 1 4 } ;
    
for  ( int  i = 0 ; i < sizeof (a) / sizeof ( int ); i ++ )
        bst.insert(a[i]);
    bst.travel();
    
return   0 ;
}
posted on 2006-09-03 04:24 阅读(304) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法

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