The Fourth Dimension Space

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

排序二叉树模板(转）

#include<iostream>
#include<cassert>
using namespace std;


/**////////////////////////A_CLASS_TEMPLATE_FOR_BST//////////////////////////////
template< class NODETYPE > class Tree;

template< class NODETYPE >
class TreeNode
{
    friend class Tree< NODETYPE >;
public:
    TreeNode( const NODETYPE &d ):leftPtr( 0 ), data( d ), rightPtr( 0 ){ }
    NODETYPE getData() const 
    {
        return data; 
    }
private:
    TreeNode< NODETYPE > *leftPtr;
    NODETYPE data;
    TreeNode< NODETYPE > *rightPtr;
};



template< class NODETYPE >
class Tree{
public:
   Tree();
   void insertNode( const NODETYPE & );
   void preOrderTraversal() const;
   void inOrderTraversal() const;
   void postOrderTraversal() const;
private:
   TreeNode< NODETYPE > *rootPtr;

   void insertNodeHelper(
    TreeNode< NODETYPE > **, const NODETYPE & );
   void preOrderHelper( TreeNode< NODETYPE > * ) const;
   void inOrderHelper( TreeNode< NODETYPE > * ) const;
   void postOrderHelper( TreeNode< NODETYPE > * ) const;
};

template< class NODETYPE >
Tree< NODETYPE >::Tree() { rootPtr = 0; }

template< class NODETYPE >
void Tree< NODETYPE >::insertNode( const NODETYPE &value )
{
insertNodeHelper( &rootPtr, value );
}

template< class NODETYPE >
void Tree< NODETYPE >::insertNodeHelper(TreeNode< NODETYPE > **ptr, const NODETYPE &value )
{
    if( *ptr == 0 )
    {
       *ptr = new TreeNode< NODETYPE >( value );
       assert( *ptr != 0 );
    }
else
   if( value < ( *ptr )->data )
       insertNodeHelper( &( ( *ptr )->leftPtr ), value );
   else
       if( value > ( *ptr )->data )
           insertNodeHelper( &( ( *ptr )->rightPtr ), value );
   else
     cout<< value << " dup" << endl;
} 

template< class NODETYPE >
void Tree< NODETYPE >::preOrderTraversal() const
{
    preOrderHelper( rootPtr ); 
}

template< class NODETYPE >
void Tree< NODETYPE >::preOrderHelper(TreeNode< NODETYPE > *ptr ) const
{
    if( ptr != 0 )
    {
       cout<< ptr->data << ' ';
       preOrderHelper( ptr->leftPtr );
       preOrderHelper( ptr->rightPtr );
    }
}

template< class NODETYPE >
void Tree< NODETYPE >::inOrderTraversal() const
{ 
    inOrderHelper( rootPtr );
}

template< class NODETYPE >
void Tree< NODETYPE >::inOrderHelper( TreeNode< NODETYPE > *ptr ) const
{
if( ptr != 0 )
    {
       inOrderHelper( ptr->leftPtr );
       cout<< ptr->data << ' ';
       inOrderHelper( ptr->rightPtr );
    }
}

template< class NODETYPE >
void Tree<NODETYPE >::postOrderTraversal() const
{
    postOrderHelper( rootPtr );
}

template< class NODETYPE >
void Tree< NODETYPE >::postOrderHelper(    TreeNode< NODETYPE > *ptr ) const
{
    if( ptr != 0 )
    {
       postOrderHelper( ptr->leftPtr );
       postOrderHelper( ptr->rightPtr );
       cout<< ptr->data << ' ';  
    }
}
/**///////////////////////////////END_TEMPLATE/////////////////////////////////

int main()
{
    Tree< int > intTree;
    int intVal;
    
    cout<< "Enter 10 integer values:\n";
    for( int i = 0; i < 10; i++ )
    {
        cin>> intVal;
        intTree.insertNode( intVal );
    }
    
    cout<< "\nPreorder traversal\n";
    intTree.preOrderTraversal();
    
    cout<< "\nInorder traversal\n";
    intTree.inOrderTraversal();
    
    cout<< "\nPostorder traversal\n";
    intTree.postOrderTraversal();
    
    return 0;
}

网上看到的模板，感觉写得很不错，呵呵。不过排序二叉树本来是用来查找的，没有查找函数真是可惜了丫，等下次有时间我来加个查找删除函数，这个模板就可以真正的使用了。


PS:其实学完数据结构以后我自己也写了一个排序二叉树的模板，可惜的是，由于新建结点里面有指针，似乎无法用上模板类了，今天看了这个模板才恍然大悟，原来可以写一个结点类，呵呵；我还有一个地方不太明白，就是friend class Tree< NODETYPE >;这条语句里面用到了friend关键字，我以前只学过友元函数，难道还有友元类么？希望知道的朋友能给我解释一下。如果能告诉我相关的知识点的出处，让我自己去学习一下就更好了，谢谢呵   :-)

posted on 2009-05-24 02:10 abilitytao 阅读(1031) 评论(1)  编辑 收藏 引用

评论

# re: 排序二叉树模板(转） 2009-05-24 15:13 longe

一个类A中定义一个友元类B的话，B成员是可以访问A成员的,包括private .这个在c++primer 三版 里有讲过的。  回复  更多评论   


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