数据结构--哈夫曼树权值相等问题_哈夫曼树两个值相同咋办-程序员宅基地

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

在哈夫曼树排序中，当遇见有两个权值相等的情况下，怎样选择排序，以及先后选择排序后打的区别；

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

本文链接：https://blog.csdn.net/WX_timi/article/details/104208070

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Python 基于 OpenCV 视觉图像处理实战之 OpenCV 简单人脸检测/识别实战案例之七简单进行人脸检测并添加面具特效实现

Python是一种跨平台的计算机程序设计语言。是一种面向对象的动态类型语言，最初被设计用于编写自动化脚本(shell)，随着版本的不断更新和语言新功能的添加，越多被用于独立的、大型项目的开发。Python是一种解释型脚本语言，可以应用于以下领域： Web 和 Internet开发、科学计算和统计、人工智能、教育、桌面界面开发、软件开发、后端开发、网络爬虫。这里使用 Python 基于 OpenCV 进行视觉图像处理，......

使用UmcFramework和unimrcpclient.xml连接多个SIP设置的配置指南及C代码示例

在多媒体通信领域，MRCP（Media Resource Control Protocol）协议被广泛用于控制语音识别和合成等媒体资源。UniMRCP是一个开源的MRCP实现，提供了客户端和服务端的库。UmcFramework是一个基于UniMRCP客户端库的示例应用程序框架，它帮助开发者快速集成和测试MRCP客户端功能。本文将详细介绍如何使用UmcFramework和unimrcpclient.xml配置文件连接到多个SIP设置，以及如何用C代码进行示例说明。

java.net.ProtocolException: Server redirected too many times (20)-程序员宅基地

文章浏览阅读3k次。报错：java.net.ProtocolException: Server redirected too many times (20)1.没有检查到cookie，一直循环重定向。解决：CookieHandler.setDefault(new CookieManager(null, CookiePolicy.ACCEPT_ALL));URL url = new URL(url); ..._java.net.protocolexception: server redirected too many times (20)

springboot启动报错 Failed to scan *****/derbyLocale_ja_JP.jar from classloader hierarchy_failed to scan from classloader hierarchy-程序员宅基地

文章浏览阅读4.1k次。问题这是部分报错信息2019-07-11 14:03:34.283 WARN [restartedMain][DirectJDKLog.java:175] - Failed to scan [file:/D:/repo/org/apache/derby/derby/10.14.2.0/derbyLocale_ja_JP.jar] from classloader hierarchyjava...._failed to scan from classloader hierarchy

MATLAB-ones函数_matlab中ones函数-程序员宅基地

文章浏览阅读2.8k次，点赞3次，收藏7次。在MATLAB中，ones函数用于创建一个指定大小的由1组成的矩阵或数组。_matlab中ones函数

解决PS等软件出现应用程序无法正常启动(0xc000007b)_photoshop应用程序无法正常启动0xc000007b。请单击“确认”关闭应用程序。-程序员宅基地

文章浏览阅读3.9w次，点赞2次，收藏9次。　　在使用电脑办公过程中，安装应用程序时难免遇到无法安装或者无法正常启动的问题，这对我们使用电脑带来了诸多不便。那遇到应用程序无法正常启动的问题要如何解决呢?相信大家肯定都是十分疑问的，每次都是只能忍痛重新安装软件。今天，小编就和大家探讨下应用程序无法正常启动的解决方法，帮助大家排忧解难。0xc000007b电脑图解1　　第一种方案：SFC检查系统完整性来尝试修复丢失文件　　1、打开电脑搜索输入cmd.exe，选择以管理员身份运行，跳出提示框时选择继续。0xc000007b电脑图解2_photoshop应用程序无法正常启动0xc000007b。请单击“确认”关闭应用程序。