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

评论

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

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


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