数据结构--哈夫曼树权值相等问题

秒速五厘米 2023-07-03 14:30 45阅读 0赞

# 数据结构–哈夫曼树权值相等问题 #

> 在哈夫曼树排序中，当遇见有两个权值相等的情况下，怎样选择排序，以及先后选择排序后打的区别；
> 
> 1、我们可以统一确定左子节点和右子节点的大小关系，例如所有构造都必须使得左子节点的权值不小于右子节点，免得给出相同的原始节点序列，所构造的哈夫曼树结构不同  
> 2、节点按照权值排序的规则，例如两个原始节点或者一个原始节点和一个新建节点，具有相同的权值时，需要统一序列中的前后顺序(序列中的前后顺序也就是确定哪个是左子节点和右子节点)，目的仍然是满足构造出的哈夫曼树具有相同的结构

附上代码

#include<stdio.h>
    #include<iostream>
    #include<stdlib.h>
    #include<string.h>
    #include<math.h>
    using namespace std ;
    typedef long long ll;
    #define MAXN 100005
    #define INF 0x3f3f3f3f
    #define MALL (Bithrnode *)malloc(sizeof(Bithrnode));
    
    typedef struct
    {
        
        int weight;
        int parent, lchild, rchild;
    }HTNode, *Huffmantree;
    
    void Select(Huffmantree HT, int n, int &x1, int &x2)// 查找前n个结点的最小权值的下标下x1、x2；
    {
        
        int min1 = INF;
        int min2 = INF;
        for(int i=1; i<=n; ++i)
        {
        
            if(HT[i].parent == 0 && min1 > HT[i].weight)
            {
        
                min1 = HT[i].weight;
                x1 = i;
            }
        }
        for(int i=1; i<=n; ++i)
        {
        
            if(HT[i].parent == 0 && min2 > HT[i].weight && i!=x1)
            {
        
                min2 = HT[i].weight;
                x2 = i;
            }
        }
    }
    
    void CreatHuffmantree(Huffmantree &HT, int n)//顺序创建哈夫曼树
    {
        
        if(n<=1)
            return;
        int m = 2*n-1;
        HT = (HTNode *)malloc(2*n*sizeof(HTNode));//创建2*n个空间，因为0没有被用到。。。。
     
        for(int i=1; i<=2*n-1; ++i)
        {
        
            HT[i].parent = 0;
            HT[i].lchild = 0;
            HT[i].rchild = 0;
        }
        for(int i=1; i<=n; ++i)
            scanf("%d", &HT[i].weight); // 初始化完成
    
        int s1, s2;
        for(int i=n+1; i<=2*n-1; ++i)
        {
        
            Select(HT, i-1, s1, s2);
    
            HT[s1].parent = i;
            HT[s2].parent = i;
            HT[i].lchild = s1;
            HT[i].rchild = s2;
            HT[i].weight = HT[s1].weight + HT[s2].weight;
        }
    }
    
    void print(Huffmantree HT, int n)
    {
        
        for(int i=1; i<=2*n-1; ++i)
        {
        
            cout << "结点序号 " << i;
            cout << " 权重 " << HT[i].weight;
            cout << " parent " << HT[i].parent;
            cout << " Lchild " << HT[i].lchild;
            cout << " Rchild " << HT[i].rchild << '\n';
        }
    }
    
    int main()
    {
        
        Huffmantree HT;
    
        cout << "开始构建哈夫曼树" << '\n';
        cout << "请输入哈夫曼树的叶子结点的个数： ";
        int n;
        cin >> n;
        cout << "请输入每个叶子结点的权值: " << '\n';
        CreatHuffmantree(HT, n);
        print(HT, n);
        return 0;
    }