bitree.h

数据结构实例 可以学一下。。

#pragma once
#include "mylib.h"

namespace mylib {
	template<typename elemtype> class bitnode {
	public:
		typedef elemtype value_type;
		bitnode(void);                              //构造函数
		bitnode(const bitnode<elemtype>&);          //拷贝构造函数
		const elemtype date(void) const;            //读取数据
		const bitnode<elemtype>* lchild(void) const;//返回左指针
		const bitnode<elemtype>* rchild(void) const;//返回右指针
		void get_date(const elemtype);              //输入数据
		void get_lchild (const bitnode<elemtype>*); //输入左指针
		void get_rchild (const bitnode<elemtype>*); //输入右指针
		const bitnode<elemtype>&
			operator= ( const bitnode<elemtype>& );  //赋值,只声明
	private:
		elemtype          _date;                    //节点数据
		bitnode<elemtype> *_lchild, *_rchild;       //左右孩子指针
	};//二叉树的节点

	//bitnode类函数实现
	template<typename elemtype>
		bitnode<elemtype>::bitnode()
	{ 
       get_date( 0 );
       get_rchild( 0 );
       get_lchild( 0 );
    }
	
	template<typename elemtype >const
		bitnode<elemtype>* bitnode<elemtype>::lchild() const 
    { 
       return _lchild; 
    }

	template<typename elemtype> const 
		bitnode<elemtype>* bitnode<elemtype>::rchild() const
    { 
       return _rchild;
    }

	template<typename elemtype> const
		elemtype bitnode<elemtype>::date () const
    { 
       return _date;
    }

	template<typename elemtype>
		void bitnode<elemtype>::get_date(const elemtype de) 

    { 
       _date = de;
    }

	template<typename elemtype> 
		void bitnode<elemtype>::
		get_lchild(const bitnode<elemtype>* pev) 
    {
       _lchild = (bitnode<elemtype>*) pev;
    }

	template<typename elemtype>
		void bitnode<elemtype>::
		get_rchild (const bitnode<elemtype>* pev) 
    {
       _rchild = (bitnode<elemtype>*) pev; 
    }

	//tree类
	template<typename elemtype> class BiTree{
	public:
		typedef elemtype value_type;

		BiTree(void);                             //构造函数
		BiTree(const BiTree<elemtype>&);
		const bitnode<elemtype>* 
			copy(const bitnode<elemtype>*);
		void print(void) const;                  //打印树中数据  
		bool empty(void) const;            //测试树是否为空
		const int node(void) const;              //返回节点个数
		const BiTree<elemtype>&
			operator= (const BiTree<elemtype>&); //赋值
	
	private:
		size_t             node_nu;               //节点个数
		bitnode<elemtype> *pv;                    //根指针
		void add_node(void);                      //增加节点
		const bitnode<elemtype>* init(void);      //初始化
		void fvisit(const bitnode<elemtype>*) const;//先序遍历
		void mvisit(const bitnode<elemtype>*) const;//中序遍历
		void hvisit(const bitnode<elemtype>*) const;//后序遍历
	};

	//二叉树类代码实现
	//公有函数集合
	template<typename elemtype>
		BiTree<elemtype>::BiTree()
    {
       pv = NULL;
       node_nu = 0;
       pv = ( bitnode* ) init();
    }

	template<typename elemtype> BiTree<elemtype>::
		BiTree(const BiTree<elemtype>& tree)
   {
       if(tree.empty())
       pv = (bitnode<elemtype>*) copy(tree.pv);
   }   

   template<typename elemtype>
	   void BiTree<elemtype>::print() const
    {
       cout << "请选择打印顺序：先序[x]？中序[z]？后序[h]？:";
       char ch;
       cin >> ch;
       if ( empty() != 0 )
	   {
           switch ( ch ) 
           {
              case 'x':  fvisit( pv ); break; 
              case 'z':  mvisit( pv ); break; 
              case 'h':  hvisit( pv ); break; 
              default: cerr << "错误操作。无法输出!" << endl;
           }
       }
       else 
           cerr << "树为空" << endl;
    }

	template<typename elemtype> 
		bool BiTree<elemtype>::empty() const
    {
       if(node_nu == 0)
           return false;
       else 
           return true;
    }

	template<typename elemtype> const
		int BiTree<elemtype>::node() const
    {
       return node_nu;
    }

	template<typename elemtype> const 
		bitnode<elemtype>* BiTree<elemtype>::
		copy(const bitnode<elemtype>* ptr)
    {
       bitnode<elemtype> *pev;
       if(ptr == 0)
           return 0;
       if (ptr->date() == 0)
           pev = 0;
       else
	   {
           if ( !(pev = new bitnode<elemtype>) )
              return 0 ;

           add_node();
           pev->get_date(ptr->date());
           pev->get_lchild( copy(ptr->lchild()) );
           pev->get_rchild( copy(ptr->rchild()) ); 

       }
       return pev;
    }

	template<typename elemtype> 
		const BiTree<elemtype>& BiTree<elemtype>::
		operator =( const BiTree<elemtype>& tree )
	{
		if(this != &tree)
		{
			if( tree.empty() )
				pv = copy( tree.pv );
		}
		return *this;
	}

	//私有函数集合

	template<typename elemtype> const 
		bitnode<elemtype>* BiTree<elemtype>::init()
    {
       bitnode<elemtype> *pev;
       elemtype de;
       cout << "请输入第"
            << node() + 1
            << "个数据：";
       cin >> de;
       if ( de == 0 )
           pev = NULL;
       else
	   {
           if ( !( pev = new bitnode<elemtype> ) )
              return 0 ;

           add_node();
           pev->get_date( de );
           pev->get_lchild( init() );
           pev->get_rchild( init() );      
       }

       return pev;
    }

	template<typename elemtype>
		void BiTree<elemtype>::add_node() 
    { 
       ++node_nu;
    }

	template<typename elemtype>
		void BiTree<elemtype>::
		fvisit(const bitnode<elemtype> *pev) const
   {
       if ( pev != NULL ) 
           cout << pev->date() << endl;    
       if ( pev->lchild() != NULL )
           fvisit( pev->lchild() );
       if ( pev->rchild() != NULL )
           fvisit( pev->rchild() );
    }

   template<typename elemtype>
	   void BiTree<elemtype>::
	   mvisit(const bitnode<elemtype> *pev) const
    {
       if ( pev->lchild() != NULL )
           mvisit( pev->lchild() );
       if ( pev != NULL ) 
           cout << pev->date() << endl;
       if ( pev->rchild() != NULL )
           mvisit( pev->rchild() );
    }

	template<typename elemtype>
		void BiTree<elemtype>::
		hvisit(const bitnode<elemtype> *pev) const
    {
       if (pev->lchild() != NULL)
           hvisit( pev->lchild() );
       if (pev->rchild() != NULL)
           hvisit( pev->rchild() );
       if (pev != NULL) 
          cout << pev->date() << endl;
    }

};