template
       
         class BinaryTree;template
        
          void Huffman(Type *, int, BinaryTree
         
           &);template
          
            class BinTreeNode{public:	friend class BinaryTree
           
            ;    friend void Huffman
            
             (Type *, int, BinaryTree
             
               &); BinTreeNode():m_pleft(NULL),m_pright(NULL){} BinTreeNode(Type item,BinTreeNode
              
                *left=NULL,BinTreeNode
               
                 *right=NULL) :m_data(item),m_pleft(left),m_pright(right){} void Destroy(){ //destroy the tree with the root of the node if(this!=NULL){ this->m_pleft->Destroy(); this->m_pright->Destroy(); delete this; } } Type GetData(){ return m_data; } BinTreeNode
                
                  *Copy(const BinTreeNode
                 
                   *copy); //copy the nodeprivate: BinTreeNode
                  
                    *m_pleft,*m_pright; Type m_data;};template
                   
                     BinTreeNode
                    
                     * BinTreeNode
                     
                      ::Copy(const BinTreeNode
                      
                        *copy){ if(copy==NULL){ return NULL; } BinTreeNode
                       
                         *temp=new BinTreeNode
                        
                         (copy->m_data); temp->m_pleft=Copy(copy->m_pleft); temp->m_pright=Copy(copy->m_pright); return temp;}
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       

#include "BinTreeNode.h"template
       
         void Huffman(Type *, int, BinaryTree
        
          &);template
         
           class BinaryTree{public:        BinaryTree(BinaryTree
          
            &bt1, BinaryTree
           
             &bt2){        m_proot = new BinTreeNode
            
             (bt1.m_proot->m_data + bt2.m_proot->m_data, bt1.m_proot, bt2.m_proot); } BinaryTree(Type item){ m_proot = new BinTreeNode
             
              (item); } BinaryTree(const BinaryTree
              
                ©){ this->m_proot = copy.m_proot; } BinaryTree(){ m_proot = NULL; } void Destroy(){ m_proot->Destroy(); } ~BinaryTree(){// m_proot->Destroy(); } BinaryTree
               
                & operator=(BinaryTree
                
                  copy); //evaluate node friend void Huffman
                 
                  (Type *, int, BinaryTree
                  
                    &); friend bool operator < 
                   
                    (BinaryTree
                    
                      &l, BinaryTree
                     
                       & r); friend bool operator > 
                      
                       (BinaryTree
                       
                         &l, BinaryTree
                        
                          & r); friend bool operator <= 
                         
                          (BinaryTree
                          
                            &l, BinaryTree
                           
                             & r); friend ostream& operator<< 
                            
                             (ostream& ,BinaryTree
                             
                              &); //output the dataprivate: BinTreeNode
                              
                                *m_proot; void Print(BinTreeNode
                               
                                 *start,int n=0); //print the tree with the root of start};template
                                
                                  bool operator <(BinaryTree
                                 
                                   &l, BinaryTree
                                  
                                    &r){ return l.m_proot->GetData() < r.m_proot->GetData();}template
                                   
                                     bool operator >(BinaryTree
                                    
                                      &l, BinaryTree
                                     
                                       &r){ return l.m_proot->GetData() > r.m_proot->GetData();}template
                                      
                                        bool operator <=(BinaryTree
                                       
                                         &l, BinaryTree
                                        
                                          &r){ return l.m_proot->GetData() <= r.m_proot->GetData();}template
                                         
                                           void BinaryTree
                                          
                                           ::Print(BinTreeNode
                                           
                                             *start, int n){ if(start==NULL){ for(int i=0;i
                                            
                                             m_pright,n+1); //print the right subtree for(int i=0;i
                                             
                                              =0){ cout<
                                              
                                               m_data<<"--->"<
                                               
                                                m_pleft,n+1); //print the left subtree}template
                                                
                                                  ostream& operator<<(ostream& os,BinaryTree
                                                 
                                                  & out){ out.Print(out.m_proot); return os;}template
                                                  
                                                    BinaryTree
                                                   
                                                    & BinaryTree
                                                    
                                                     ::operator=(BinaryTree
                                                     
                                                       copy){ m_proot=m_proot->Copy(copy.m_proot); return *this;}
                                                     
                                                    
                                                   
                                                  
                                                 
                                                
                                               
                                              
                                             
                                            
                                           
                                          
                                         
                                        
                                       
                                      
                                     
                                    
                                   
                                  
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       

template
       
         class MinHeap{public:	MinHeap(Type heap[],int n);		//initialize heap by a array	~MinHeap(){		delete[] m_pheap;	}public:    bool Insert(const Type item);    bool DeleteMin(Type &first);private:	void Adjust(const int start, const int end);	//adjust the elements from start to endprivate:	const int m_nMaxSize;		Type *m_pheap;	int m_ncurrentsize;};template
        
          void MinHeap
         
          ::Adjust(const int start, const int end){	int i = start,j = i*2+1;	Type temp=m_pheap[i];	while(j <= end){		if(j
          
           m_pheap[j+1]){			j++;		}		if(temp <= m_pheap[j]){			break;		}		else{			m_pheap[i] = m_pheap[j];			i = j;			j = 2*i+1;		}	}	m_pheap[i] = temp;}template
           
             MinHeap
            
             ::MinHeap(Type heap[], int n):m_nMaxSize(n){ m_pheap = new Type[m_nMaxSize]; for(int i=0; i
             
              =0){ Adjust(pos, n-1); pos--; }}template
              
                bool MinHeap
               
                ::DeleteMin(Type &first){ first = m_pheap[0]; m_pheap[0] = m_pheap[m_ncurrentsize-1]; m_ncurrentsize--; Adjust(0, m_ncurrentsize-1); return 1;}template
                
                  bool MinHeap
                 
                  ::Insert(const Type item){ if(m_ncurrentsize == m_nMaxSize){ cerr<<"Heap Full!"<
                  
                    0){ if(m_pheap[i] <= temp){ break; } else{ m_pheap[j] = m_pheap[i]; j = i; i = (j-1)/2; } } m_pheap[j] = temp; m_ncurrentsize++; return 1;}
                  
                 
                
               
              
             
            
           
          
         
        
       

#include "BinaryTree.h"#include "MinHeap.h"template
       
         void Huffman(Type *elements, int n, BinaryTree
        
          &tree){    BinaryTree
         
           first, second;    BinaryTree
          
            node[20];    for (int i=0; i
           
            (elements[i]);    }    MinHeap
            
             
               > heap(node, n); for (int i=0; i
              
               GetData() == second.m_proot->GetData()){ tree = *(new BinaryTree
               
                (second, first)); } else { tree = *(new BinaryTree
                
                 (first, second)); } heap.Insert(tree); }}
                
               
              
             
            
           
          
         
        
       

#include 
       
        using namespace std;#include "Huffman.h"int main(){    BinaryTree
        
          tree;    int init[10]={3,6,0,2,8,4,9,1,5,7};    Huffman(init,10,tree);    cout << tree;    tree.Destroy();    return 0;}