liuzeyu12a 发表于 2019-3-9 18:02:52

哈夫曼树的建树

请大佬根据我的代码把树建立以下,我根据自己代码建立的树,
![图片说明](https://img-ask.csdn.net/upload/201903/09/1552125113_251175.png)

然而解码的时候发现对应不上
附上代码,代码可以运行。。就是树的解码对应不上?
我这边代码运行的结果是:

![图片说明](https://img-ask.csdn.net/upload/201903/09/1552125268_67438.png)

无能为了了发现自己好菜,没C币了,如果可以帮忙解释清楚的,也是可以有偿的

```
#include "stdafx.h"
#include<string.h>
#include<malloc.h>//malloc()等
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<limits.h>
#include<iostream>

#define TRUE 1
#define FALSE 1
#define OK 1
#define ERROR 1
#define INFEASIBLE -1

typedef int Status;
typedef int Boolean;


/************************************************************************/
/* 最优二叉树简称:哈夫曼树                                                                     */
/************************************************************************/
//哈夫曼树结构
; typedef struct{
        unsigned int weight;          //权重
        unsigned int parent, lchild, rchild;//树的双亲节点,和左右孩子

}HTNode, *HuffmanTree;

typedef char**HuffmanCode;

//返回i个节点中权值最小的树的根节点的序号,供select()调用
int Min(HuffmanTree T, int i){
        int j, flag;
        unsigned int k = UINT_MAX;//%d-->UINT_MAX = -1,%u--->非常大的数
        for (j = 1; j <= i; j++)
                if (T.weight <k && T.parent == 0)
                        k = T.weight, flag = j;                  //
        T.parent = 1;    //将parent标志为1避免二次查找

        return flag;   //返回
}

void Select(HuffmanTree T, int i, int& s1, int& s2){
        //在i个节点中选取2个权值最小的树的根节点序号,s1为序号较小的那个
        int j;
        s1 = Min(T, i);
        s2 = Min(T, i);
        if (s1 > s2){
                j = s1;
                s1 = s2;
                s2 = j;
        }
}

//HuffmanCode代表的树解码二进制值
void HuffmanCoding(HuffmanTree &HT, HuffmanCode&HC, int* w, int n){
        //w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
        int m, i, s1, s2, start;
        unsigned c, f;
        char* cd;
        //分配存储空间
        HuffmanTree p;
        if (n <= 1)
                return;
        //n个字符(叶子节点)有2n-1个树节点,所以树节点m
        m = 2 * n - 1;
        HT = (HuffmanTree)malloc((m + 1)*sizeof(HTNode));//0号元素未用
        //这一步是给哈夫曼树的叶子节点初始化
        for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++w)
        {
                (*p).weight = *w;
                (*p).lchild = 0;
                (*p).rchild = 0;
                (*p).parent = 0;
        }
        //这一步是给哈夫曼树的非叶子节点初始化
        for (; i <= m; ++i, ++p){
                (*p).parent = 0;
        }
        /************************************************************************/
        /* 做完准备工作后 ,开始建立哈夫曼树
        /************************************************************************/
        for (i = n + 1; i <= m; i++)
        {
                //在HT中选择parent=0且weigh最小的节点,其序号分别为s1,s2
                Select(HT, i - 1, s1, s2);//传引用
                HT.parent = HT.parent = i;
                HT.lchild = s1;
                HT.rchild = s2;
                HT.weight = HT.weight + HT.weight;
        }
        /************************************************************************/
        /* 从叶子到根逆求每个叶子节点的哈夫曼编码                                          */
        /************************************************************************/
        //分配n个字符编码的头指针向量,(不用)
        HC = (HuffmanCode)malloc((n + 1)*sizeof(char*));
        cd = (char*)malloc(n*sizeof(char));   //分配求编码的工作空间
        cd = '\0'; //结束符
        for (i = 1; i <= n; i++)//每个节点的遍历
        {
                start = n - 1;
                for (c = i, f = HT.parent; f != 0; c = f, f = HT.parent){ //每个节点到根节点的遍历
                        //从叶子节点到根节点的逆序编码
                        if (HT.lchild == c)
                                cd[--start] = '0';
                        else
                                cd[--start] = '1';
                }
                HC = (char*)malloc((n - start)*sizeof(char));//生成一个块内存存储字符
                //为第i个字符编码分配空间
                strcpy(HC, &cd);//从cd赋值字符串到cd
        }
        free(cd);//释放资源
}

//函数声明
int Min(HuffmanTree T, int i); //求i个节点中的最小权重的序列号,并返回
void Select(HuffmanTree T, int i, int& s1, int& s2); //从两个最小权重中选取最小的(左边)给s1,右边的给s2
void HuffmanCoding(HuffmanTree &HT, HuffmanCode&HC, int* w, int n);//哈夫曼编码与解码

int main(){

        HuffmanTree HT;
        HuffmanCode HC;

        int *w, n, i;
        printf("请输入权值的个数(>1):");
        scanf_s("%d", &n);

        w = (int*)malloc(n*sizeof(int));
        printf("请依次输入%d个权值(整形):\n", n);

        for (i = 0; i <= n - 1; i++)
        {
                scanf_s("%d", w + i);
        }
        HuffmanCoding(HT, HC, w, n);

        for (i = 1; i <= n; i++)
        {
                puts(HC);
        }
        return 0;
}

```

伊亡 发表于 2019-3-17 20:11:32

检查一下你的min函数,两个min函数选出值的是不是一样的
页: [1]
查看完整版本: 哈夫曼树的建树