#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;
    }

};