[已解决]此代码创建的哈夫曼树正确吗?

a905448839

#include <stdio.h>
#include <stdlib.h>

int MinData = -1; 
typedef struct TreeNode *HuffmanTree;
typedef struct Heap *MinHeap;
typedef int ElenmentType ;
struct TreeNode
{
    ElenmentType Weight;//权值
    HuffmanTree Left;
    HuffmanTree Right;
};
struct Heap
{
    HuffmanTree *Data;
    ElenmentType Size;
    ElenmentType Capacity;
};

MinHeap CreateHeap(int MaxSize);   // 建堆 
void InsertHeap(MinHeap H,HuffmanTree T);
HuffmanTree DeleteHeap(MinHeap H);
HuffmanTree CreateHuffman(MinHeap H);
void WPL(HuffmanTree HF,int depth);
void P(MinHeap H);

MinHeap CreateHeap(int MaxSize)
{
    MinHeap H = malloc(sizeof(struct Heap));
    H->Data = malloc((MaxSize + 1)* sizeof(struct TreeNode));
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Data[0] = malloc(sizeof(struct TreeNode));
    H->Data[0]->Weight = MinData;
    int i;
    for(i = 1;i <= MaxSize;i++)
            H->Data[i] = NULL;

    return H;
}

void InsertHeap(MinHeap H,HuffmanTree T)
{
        if(H->Size == H->Capacity)
        {
                printf("最小堆满");
                return; 
        }
        int i = ++H->Size;
        for(;H->Data[i/2]->Weight > T->Weight;i/=2)
                H->Data[i] = H->Data[i/2];
        H->Data[i] = T;
}

HuffmanTree DeleteHeap(MinHeap H)
{
        if(H->Size == 0)
        {
                printf("最小堆空");
                return;
        }
        HuffmanTree MinData = H->Data[1];
        HuffmanTree temp = H->Data[H->Size--];
        int i,j;
        for(i = 1;i*2 <= H->Size;i = j)
        {
                j = i*2;
                if((j != H->Size) && (H->Data[j]->Weight > H->Data[j+1]->Weight))
                j++;
                if(temp->Weight <= H->Data[j]->Weight)break;
                else
                        H->Data[i] = H->Data[j];
        }
        H->Data[i] = temp;
        
        P(H);
        return MinData;
}
HuffmanTree CreateHuffman(MinHeap H)
{
        while(H->Size > 1)
        {
                printf("合并前：\n"); 

                HuffmanTree A = DeleteHeap(H);
                HuffmanTree B = DeleteHeap(H);
                HuffmanTree Troot = (HuffmanTree)malloc(sizeof(struct TreeNode));
                Troot->Weight = A->Weight+B->Weight;
                Troot->Left = A;
                Troot->Right = B;
                InsertHeap(H,Troot);
                printf("合并后：\n"); 
                P(H);

        }
        return H->Data[1];
}

void WPL(HuffmanTree HF,int depth)
{
        // 找到二叉树的叶子节点并打印深度
    if (HF == NULL) {
        return;
    }

    if (HF->Left == NULL && HF->Right == NULL) {
        printf("%d\n", HF->Weight * depth);
    }

    WPL(HF->Left, depth + 1);
    WPL(HF->Right, depth + 1);


}

void P(MinHeap H)
{
        int i = 1;
        if(H->Size > 0)
                for(;i <= H->Size;i++)
                        printf("%d ",H->Data[i]->Weight); 
                printf("\n");
}
int main()
{
        
        int i;
        scanf("%d\n",&i);
        MinHeap H = CreateHeap(i);
        while(i--)
        {
                char a;
                ElenmentType Weight;
                scanf("%c %d",&a,&Weight);
                HuffmanTree T  = malloc(sizeof(struct TreeNode));
                T->Left = T->Right = NULL;
                T->Weight = Weight;
                getchar();
                InsertHeap(H,T);
        }
        HuffmanTree HF = CreateHuffman(H);
         WPL(HF,1);

  return 0;
}

此代码创建的哈夫曼树正确吗?好像创造出来的不是正确的,哈夫曼树WPL值也不对。。。求解答哪里错误了。

最佳答案

月排行榜 / 总排行榜

isdkz

2023-7-18 16:22:52

这段代码在创建哈夫曼树时没有任何错误。问题在于  WPL  函数，它打印了每个叶子节点的权值与深度的乘积，而没有实现真正的权值路径长度 (Weighted Path Length, WPL)。WPL 应该是所有叶子节点的权值与深度的乘积之和。

以下是修改后的  WPL  函数：

int WPL(HuffmanTree HF, int depth){    if (HF == NULL) {        return 0;    }    if (HF->Left == NULL && HF->Right == NULL) {        return HF->Weight * depth;    }    return WPL(HF->Left, depth + 1) + WPL(HF->Right, depth + 1);}

然后，在  main  函数中，用下面的语句替换  WPL(HF,1); ，以打印总的 WPL 值：

printf("%d\n", WPL(HF, 1));

此外，对于输入部分，我注意到你用  scanf("%c %d", &a, &Weight);  获取了一个字符，但这个字符并没有在后续的操作中使用。如果这个字符的输入是不必要的，那么你可以直接输入权值，然后跟一个换行符。如果这个字符是重要的，那么你需要在  TreeNode  结构中添加一个字符字段来存储这个字符。

希望以上的建议可以帮助你改善你的代码。

跳转到最佳答案楼层

陶远航

根据你提供的代码，似乎存在一些问题导致创建的哈夫曼树和WPL值不正确。下面是我发现的几个可能的错误：

1. 在函数MinHeap CreateHeap(int MaxSize)中，你为最小堆的数据数组分配内存时，只给每个节点分配了sizeof(struct TreeNode)的内存，但实际上每个节点应该是指向struct TreeNode类型的指针，所以分配内存时应该使用sizeof(struct TreeNode*)。

2. 在函数InsertHeap(MinHeap H, HuffmanTree T)中的循环条件判断部分存在错误。应该是H->Data[i/2]->Weight > T->Weight而不是H->Data[i/2]->Weight < T->Weight。这样才能保证最小堆的性质。

3. 在函数DeleteHeap(MinHeap H)中，在交换节点位置时，应该使用H->Data = H->Data[j][i]而不是H->Data = H->Data[j+1][i]。

4. 在函数CreateHuffman(MinHeap H)中的循环条件判断部分存在错误。应该是j != H->Size && (H->Data[j]->Weight < H->Data[j+1]->Weight)而不是j != H->Size && (H->Data[j]->Weight > H->Data[j+1]->Weight)。

请根据以上建议修改代码，并重新运行以创建正确的哈夫曼树。

isdkz

这段代码在创建哈夫曼树时没有任何错误。问题在于  WPL  函数，它打印了每个叶子节点的权值与深度的乘积，而没有实现真正的权值路径长度 (Weighted Path Length, WPL)。WPL 应该是所有叶子节点的权值与深度的乘积之和。

以下是修改后的  WPL  函数：

int WPL(HuffmanTree HF, int depth){    if (HF == NULL) {        return 0;    }    if (HF->Left == NULL && HF->Right == NULL) {        return HF->Weight * depth;    }    return WPL(HF->Left, depth + 1) + WPL(HF->Right, depth + 1);}

然后，在  main  函数中，用下面的语句替换  WPL(HF,1); ，以打印总的 WPL 值：

printf("%d\n", WPL(HF, 1));

此外，对于输入部分，我注意到你用  scanf("%c %d", &a, &Weight);  获取了一个字符，但这个字符并没有在后续的操作中使用。如果这个字符的输入是不必要的，那么你可以直接输入权值，然后跟一个换行符。如果这个字符是重要的，那么你需要在  TreeNode  结构中添加一个字符字段来存储这个字符。

希望以上的建议可以帮助你改善你的代码。