2021-10-06

typedef struct HTreeNode
{
    DataType data;  //结点的关键字
    HTreeNode *lchild,*rchild;  //左右孩子
    int level;  //结点在树中的层次
    
}HTreeNode,*HTree;

 
HTree HuffmanTree(priority_queue,cmp> &q){
    
    while (q.size()>1)//仅剩一个结点（即Huffman树的根节点时跳出循环）
    {
        HTree h1=q.top();
        q.pop();
        HTree h2=q.top();
        q.pop();
        HTree h=(HTreeNode*)malloc(sizeof(HTreeNode));  //将取出的两个节点合成新的结点
        h->lchild=h1;
        h->rchild=h2;
        h->data=h1->data+h2->data;
        q.push(h);
    }

    return q.top();
    
}

//计算在Huffman树中指定p结点的层次
int getLevel(HTree tree,HTreeNode* p){
    if(!tree)
        return 0;
    if(tree==p){//发现了p结点，则当前层为第一层，向上累加可得p结点的层次
        return 1;
    }
    int lLevel=getLevel(tree->lchild,p);
    int rLevel=getLevel(tree->rchild,p);
    
    if (lLevel || rLevel) //左右孩子不全为NULL时，则当前结点可能是根结点到P结点路径上的点，需要继续递归探查
    {
         return lLevel>rLevel? lLevel+1:rLevel+1;
    }
    //当tree结点不为NULL，不是p结点，又是叶子结点（即p不会是根节点到P结点路径上的点）
    return 0;
    
}

void setTNodeDepth(HTree &tree){
    HTree t=tree;
    // int treeHeight=getDepth(tree);  //HuffmanTree的树高度
    queue q;
    q.push(tree);
    while(!q.empty()){
        HTree h=q.front();
        q.pop();
        //根结点到该叶子结点的路径长度=叶子结点的层次-1
        h->level=getLevel(tree,h)-1;   //计算结点的带权路径长度=结点的权值*根结点到该叶子结点的路径长度
        // cout<data<<"  "<data<<"  "<level<lchild)
            q.push(h->lchild);
        if(h->rchild)
            q.push(h->rchild);
    }
    
}

int getHuffmanTreeWPL(HTree tree){
    HTree t=tree;
    int HuffmanTreeWPL=0;
    queue q;
    q.push(tree);
    while(!q.empty()){
        HTree h=q.front();
        q.pop();
        if(!h->lchild && !h->rchild){//只计算叶子节点的权值
            HuffmanTreeWPL+=(h->level*h->data);
        }
        if(h->lchild)
            q.push(h->lchild);
        if(h->rchild)
            q.push(h->rchild);
    }

    return HuffmanTreeWPL;
}

完整代码如下所示：

#include 
#include
#include
#define N 100
#define DataType int
using namespace std;

typedef struct HTreeNode
{
    DataType data;  //结点的关键字
    HTreeNode *lchild,*rchild;  //左右孩子
    int level;  //结点在树中的层次
    
}HTreeNode,*HTree;

 
struct cmp
{
	bool operator () (const HTree &a, const HTree &b)		  
	{
		return a->data>b->data;			
	}
};

 
void init(priority_queue,cmp> &q,int arr[],int len){

    
    for(int i=0;ilchild=NULL;
        h->rchild=NULL;
        h->data=arr[i];
        q.push(h);
    }

}

//输出整个优先队列
void print(priority_queue,cmp> &q){
    while (!q.empty())
    {
        HTree h=q.top();
        q.pop();
        cout<data<,cmp> &q){
    
    while (q.size()>1)//仅剩一个结点（即Huffman树的根节点时跳出循环）
    {
        HTree h1=q.top();
        q.pop();
        HTree h2=q.top();
        q.pop();
        HTree h=(HTreeNode*)malloc(sizeof(HTreeNode));  //将取出的两个节点合成新的结点
        h->lchild=h1;
        h->rchild=h2;
        h->data=h1->data+h2->data;
        q.push(h);
    }

    return q.top();
    
}
//递归计算指定节点的高度（与本题无关）
int getDepth(HTree tree){
    if (tree==NULL)
    {
        return 0;
    }else{
        
        int lDepth=getDepth(tree->lchild);
        int rDepth=getDepth(tree->rchild);
        return lDepth>rDepth? lDepth+1:rDepth+1;
    }
    
}

//计算在Huffman树中指定p结点的层次
int getLevel(HTree tree,HTreeNode* p){
    if(!tree)
        return 0;
    if(tree==p){//发现了p结点，则当前层为第一层，向上累加可得p结点的层次
        return 1;
    }
    int lLevel=getLevel(tree->lchild,p);
    int rLevel=getLevel(tree->rchild,p);
    
    if (lLevel || rLevel) //左右孩子不全为NULL时，则当前结点可能是根结点到P结点路径上的点，需要继续递归探查
    {
         return lLevel>rLevel? lLevel+1:rLevel+1;
    }
    //当tree结点不为NULL，不是p结点，又是叶子结点（即p不会是根节点到P结点路径上的点）
    return 0;
    
}


void setTNodeDepth(HTree &tree){
    HTree t=tree;
    // int treeHeight=getDepth(tree);  //HuffmanTree的树高度
    queue q;
    q.push(tree);
    while(!q.empty()){
        HTree h=q.front();
        q.pop();
        //根结点到该叶子结点的路径长度=叶子结点的层次-1
        h->level=getLevel(tree,h)-1;   //计算结点的带权路径长度=结点的权值*根结点到该叶子结点的路径长度
        // cout<data<<"  "<data<<"  "<level<lchild)
            q.push(h->lchild);
        if(h->rchild)
            q.push(h->rchild);
    }
    
}


int getHuffmanTreeWPL(HTree tree){
    HTree t=tree;
    int HuffmanTreeWPL=0;
    queue q;
    q.push(tree);
    while(!q.empty()){
        HTree h=q.front();
        q.pop();
        if(!h->lchild && !h->rchild){//只计算叶子节点的权值
            // cout<level<<"*"<data<<"="<level*h->data<level*h->data);
        }
        if(h->lchild)
            q.push(h->lchild);
        if(h->rchild)
            q.push(h->rchild);
    }

    return HuffmanTreeWPL;
}

int main(){
    
    DataType arr[N] = {1, 8, 15, 19, 32, 17, 65, 3, 9};
    int len = 9;
    priority_queue,cmp> q;
    init(q,arr,len);
    HTree tree=HuffmanTree(q);

    setTNodeDepth(tree);
    cout< 
小白也是在学习数据结构，哪里学的不通透欢迎各位指正！
 觉得写得不错的话，点个赞吧！