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

a905448839

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int MinData = -1;
   
5. typedef struct TreeNode *HuffmanTree;
   
6. typedef struct Heap *MinHeap;
   
7. typedef int ElenmentType ;
   
8. struct TreeNode
   
9. {
   
10.     ElenmentType Weight;//权值
    
11.     HuffmanTree Left;
    
12.     HuffmanTree Right;
    
13. };
    
14. struct Heap
    
15. {
    
16.     HuffmanTree *Data;
    
17.     ElenmentType Size;
    
18.     ElenmentType Capacity;
    
19. };
    
20. 
    
21. MinHeap CreateHeap(int MaxSize);   // 建堆
    
22. void InsertHeap(MinHeap H,HuffmanTree T);
    
23. HuffmanTree DeleteHeap(MinHeap H);
    
24. HuffmanTree CreateHuffman(MinHeap H);
    
25. void WPL(HuffmanTree HF,int depth);
    
26. void P(MinHeap H);
    
27. 
    
28. MinHeap CreateHeap(int MaxSize)
    
29. {
    
30.     MinHeap H = malloc(sizeof(struct Heap));
    
31.     H->Data = malloc((MaxSize + 1)* sizeof(struct TreeNode));
    
32.     H->Size = 0;
    
33.     H->Capacity = MaxSize;
    
34.     H->Data[0] = malloc(sizeof(struct TreeNode));
    
35.     H->Data[0]->Weight = MinData;
    
36.     int i;
    
37.     for(i = 1;i <= MaxSize;i++)
    
38.             H->Data[i] = NULL;
    
39. 
    
40.     return H;
    
41. }
    
42. 
    
43. void InsertHeap(MinHeap H,HuffmanTree T)
    
44. {
    
45.         if(H->Size == H->Capacity)
    
46.         {
    
47.                 printf("最小堆满");
    
48.                 return;
    
49.         }
    
50.         int i = ++H->Size;
    
51.         for(;H->Data[i/2]->Weight > T->Weight;i/=2)
    
52.                 H->Data[i] = H->Data[i/2];
    
53.         H->Data[i] = T;
    
54. }
    
55. 
    
56. HuffmanTree DeleteHeap(MinHeap H)
    
57. {
    
58.         if(H->Size == 0)
    
59.         {
    
60.                 printf("最小堆空");
    
61.                 return;
    
62.         }
    
63.         HuffmanTree MinData = H->Data[1];
    
64.         HuffmanTree temp = H->Data[H->Size--];
    
65.         int i,j;
    
66.         for(i = 1;i*2 <= H->Size;i = j)
    
67.         {
    
68.                 j = i*2;
    
69.                 if((j != H->Size) && (H->Data[j]->Weight > H->Data[j+1]->Weight))
    
70.                 j++;
    
71.                 if(temp->Weight <= H->Data[j]->Weight)break;
    
72.                 else
    
73.                         H->Data[i] = H->Data[j];
    
74.         }
    
75.         H->Data[i] = temp;
    
76.        
    
77.         P(H);
    
78.         return MinData;
    
79. }
    
80. HuffmanTree CreateHuffman(MinHeap H)
    
81. {
    
82.         while(H->Size > 1)
    
83.         {
    
84.                 printf("合并前：\n");
    
85. 
    
86.                 HuffmanTree A = DeleteHeap(H);
    
87.                 HuffmanTree B = DeleteHeap(H);
    
88.                 HuffmanTree Troot = (HuffmanTree)malloc(sizeof(struct TreeNode));
    
89.                 Troot->Weight = A->Weight+B->Weight;
    
90.                 Troot->Left = A;
    
91.                 Troot->Right = B;
    
92.                 InsertHeap(H,Troot);
    
93.                 printf("合并后：\n");
    
94.                 P(H);
    
95. 
    
96.         }
    
97.         return H->Data[1];
    
98. }
    
99. 
    
100. void WPL(HuffmanTree HF,int depth)
     
101. {
     
102.         // 找到二叉树的叶子节点并打印深度
     
103.     if (HF == NULL) {
     
104.         return;
     
105.     }
     
106. 
     
107.     if (HF->Left == NULL && HF->Right == NULL) {
     
108.         printf("%d\n", HF->Weight * depth);
     
109.     }
     
110. 
     
111.     WPL(HF->Left, depth + 1);
     
112.     WPL(HF->Right, depth + 1);
     
113. 
     
114. 
     
115. }
     
116. 
     
117. void P(MinHeap H)
     
118. {
     
119.         int i = 1;
     
120.         if(H->Size > 0)
     
121.                 for(;i <= H->Size;i++)
     
122.                         printf("%d ",H->Data[i]->Weight);
     
123.                 printf("\n");
     
124. }
     
125. int main()
     
126. {
     
127.        
     
128.         int i;
     
129.         scanf("%d\n",&i);
     
130.         MinHeap H = CreateHeap(i);
     
131.         while(i--)
     
132.         {
     
133.                 char a;
     
134.                 ElenmentType Weight;
     
135.                 scanf("%c %d",&a,&Weight);
     
136.                 HuffmanTree T  = malloc(sizeof(struct TreeNode));
     
137.                 T->Left = T->Right = NULL;
     
138.                 T->Weight = Weight;
     
139.                 getchar();
     
140.                 InsertHeap(H,T);
     
141.         }
     
142.         HuffmanTree HF = CreateHuffman(H);
     
143.          WPL(HF,1);
     
144. 
     
145.   return 0;
     
146. }

复制代码

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

最佳答案

月排行榜 / 总排行榜

isdkz

2023-7-18 16:22:52

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

以下是修改后的  WPL  函数：

1. int WPL(HuffmanTree HF, int depth)
2. {
3.     if (HF == NULL) {
4.         return 0;
5.     }
7.     if (HF->Left == NULL && HF->Right == NULL) {
8.         return HF->Weight * depth;
9.     }
11.     return WPL(HF->Left, depth + 1) + WPL(HF->Right, depth + 1);
12. }

复制代码

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

1. 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  函数：

1. int WPL(HuffmanTree HF, int depth)
2. {
3.     if (HF == NULL) {
4.         return 0;
5.     }
7.     if (HF->Left == NULL && HF->Right == NULL) {
8.         return HF->Weight * depth;
9.     }
11.     return WPL(HF->Left, depth + 1) + WPL(HF->Right, depth + 1);
12. }

复制代码

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

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

复制代码

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

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