Huffmanツリーの構造と符号化

#include 
#include 
using namespace std;

//       
struct Node
{
    double weight;                        //  
    char ch;                              //    
    string code;                          //  
    Node* lchild,*rchild,*parent;
    Node(double _weight=0,char _ch='*',string _code="")                          //    
    :weight(_weight),ch(_ch),code(_code),lchild(NULL),rchild(NULL),parent(NULL){}

    //     
    bool operator(Node &N){return weight>N.weight;}
    bool operator>=(Node &N){return weight>=N.weight;}
};

#include 
#include "Node.h"
using namespace std;

class HuffmanTree
{
private:
    Node *root;                               //   
    void destroy(Node *subtree);              //   
    void PreOrder(Node *subtree);             //    
    void InOrder(Node *subtree);              //    
    void LevelOrder(Node *subtree);           //    
    void PostOrder(Node *subtree);            //    
    void HuffmanCode(Node *&subtree);         //      Huffman     
public:
    HuffmanTree(int A[],char B[],int n);      //    
    ~HuffmanTree(){destroy(root);}            //    
    void PreOrder(){cout<

//   ，    
#include "Node.h"
#define DefaultSize 50
template 
class MinHeap
{
private:
    T *heap;
    int currentSize;
    void SiftUp(int start);
    void SiftDown(int start,int over);
public:
    MinHeap():currentSize(0){ heap=new T[DefaultSize];}
    ~MinHeap(){currentSize=0;}
    bool Insert(const T &x);
    bool RemoveMin(T &x);
    bool IsEmpty(){return (currentSize==0)?true:false;}
};
template 
bool MinHeap::Insert(const T &x)
{

     heap[currentSize]=x;
     SiftUp(currentSize);
     currentSize++;
     return true;
}
template 
void MinHeap::SiftUp(int start)
{
    int j=start,i=(j-1)/2;
    T t;
    while(i>=0)
    {
        if(heap[j]>=heap[i])  break;
        else
        {
            t=heap[j];
            heap[j]=heap[i];
            heap[i]=t;
            j=i;i=(j-1)/2;
        }

    }
}
template 
void MinHeap::SiftDown(int start,int over)
{
    T t;
    int i=start,j=2*i+1;
    while(j<=over)
    {
        if(j=heap[i]) break;
        else
        {
            t=heap[j];
            heap[j]=heap[i];
            heap[i]=t;
            i=j;j=2*i+1;
        }

    }
}
template 
bool MinHeap::RemoveMin(T &x)
{
    if(!IsEmpty())
    {
        x=heap[0];
        heap[0]=heap[currentSize-1];
        currentSize--;
        SiftDown(0,currentSize-1);
        return true;
    }
    else return false;
}

template 
struct QNode
{
    T data;
    QNode *next;
    QNode():next(NULL){}
    QNode(T _data):data(_data),next(NULL){}
};
template 
class Queue
{
private:
    QNode *front_,*rear;
public:
    Queue():front_(NULL),rear(NULL){}
    bool EnQueue(const T &x);
    bool DeQueue(T &x);
    T getFront();
    T getRear();
    int getSize();
    bool IsEmpty();

};

template 
bool Queue::EnQueue(const T &x)
{
   if(front_==NULL)
   {
       rear=front_=new QNode(x);
       return true;

   }
   else{
    rear->next=new QNode(x);
    if(rear->next==NULL) return false;
    rear=rear->next;

   }
   return true;
}

template 
bool Queue::DeQueue(T &x)
{
    if(IsEmpty()) return false;
    else
    {
       QNode *p=front_;
       x=front_->data;
       front_=front_->next;
       delete p;
       return true;
    }
}

template 
T Queue::getFront()
{
   return front_->data;
}
template 
T Queue::getRear()
{
    return rear->data;
}
template 
int Queue::getSize()
{
    if(front_==NULL) return 0;
    if(front_==rear&&front_!=NULL) return 1;
    int n=2;
    QNode *current=front_;
    while(current->next!=rear)
    {
        n++;
        current=current->next;
    }
    return n;
}
template 
bool Queue::IsEmpty()
{
    if(front_==NULL)
        return true;
    return false;
}

#include 
#include 
#include 
#include "Queue.h"
#include "MinHeap.h"
#include "Huffman.h"
using namespace std;

//    
HuffmanTree::HuffmanTree(int A[],char B[],int n) //A      ，B       
{
    int i;
    MinHeap mh;                           //         
    Node *parent,*first,*second,*temp;
    for(i=0;iweight=t1->weight+t2->weight;
    parent->lchild=t1;
    parent->rchild=t2;
    t1->parent=t2->parent=parent;
}

//   subtree       
void HuffmanTree::destroy(Node *subtree)
{
    if(subtree!=NULL)
    {
        destroy(subtree->lchild);
        destroy(subtree->rchild);
        delete subtree;
    }
}

//    
void HuffmanTree::PreOrder(Node *subtree)
{
    if(subtree!=NULL)
    {
        cout<weight;
        PreOrder(subtree->lchild);
        PreOrder(subtree->rchild);

    }
}
//    
void HuffmanTree::InOrder(Node *subtree)
{
    if(subtree!=NULL)
    {
         InOrder(subtree->lchild);
         cout<weight;
         InOrder(subtree->rchild);
    }
}
//    
void HuffmanTree::PostOrder(Node *subtree)
{
    if(subtree!=NULL)
    {
         PostOrder(subtree->lchild);
         PostOrder(subtree->rchild);
         cout<weight;
    }
}
//    
void HuffmanTree::LevelOrder(Node *subtree)
{
    Queue q;
    Node *temp;
    q.EnQueue(subtree);
    while(!q.IsEmpty())
    {
        q.DeQueue(temp);
        cout<weight;
        if(temp->lchild!=NULL) q.EnQueue(temp->lchild);
        if(temp->rchild!=NULL) q.EnQueue(temp->rchild);
    }

}
// Huffman     
void HuffmanTree::HuffmanCode(Node *&subtree)
{
     Queue q;
     Node *temp;
     q.EnQueue(subtree);
     while(!q.IsEmpty())
     {
         q.DeQueue(temp);
         Node *l=temp->lchild,*r=temp->rchild;
         if(l==NULL&&r==NULL)                                //       ，     ，       
            {
                cout<ch<code<code=temp->code+"0";q.EnQueue(l);}    //      ，        +0
         if(r!=NULL){r->code=temp->code+"1";q.EnQueue(r);}    //      ，        +1

     }
}

#include 
#include "Huffman.h"
#define Max 100
using namespace std;

int main()
{
    int A[Max],n,i;
    char B[Max];
    cout<>n;
    cout<>B[i];
    cout<>A[i];
    HuffmanTree h(A,B,n);
    h.HuffmanCode();
    cout<