PTA习题 HuffmanTree的创建问题
本题要求实现一个创建哈夫曼树的函数,根据输入的n个结点的权值,创建一棵哈夫曼树。例如输入5 2 3 5 7 8,其中第一个数值5,表示5个结点,2 3 5 7 8分别表示这5个结点的权值,中间用空格分开,则该函数应该输出5(2,3),10(5,5),15(7,8),25(10,15),注意:生成的结点之间用“,”分开。
程序代码:
#include <stdio.h> #include <string.h> #include <malloc.h> typedef struct { int weight; // 结点权值 int parent, lc, rc; // 双亲结点和左 右子节点 } HTNode, *HuffmanTree; void Select(HuffmanTree *HT, int n, int *s1, int *s2) { int minum,i; // 定义一个临时变量保存最小值? for(i=1; i<=n; i++) // 以下是找到第一个最小值 { if((*HT)[i].parent == 0) { minum = i; break; } } for(i=1; i<=n; i++) { if((*HT)[i].parent == 0) if((*HT)[i].weight < (*HT)[minum].weight) minum = i; } *s1 = minum; // 以下是找到第二个最小值,且与第一个不同 for( i=1; i<=n; i++) { if((*HT)[i].parent == 0 && i != *s1) { minum = i; break; } } for( i=1; i<=n; i++) { if((*HT)[i].parent == 0 && i != *s1) if((*HT)[i].weight < (*HT)[minum].weight) minum = i; } *s2 = minum; } void CreatHuff(HuffmanTree *HT, int *w, int n); int main() { HuffmanTree HT; int *w, n, wei,i; //printf("input the number of node\n"); scanf("%d", &n); //w = new int[n+1]; w=(int *) malloc ((n+1) * sizeof(int)); //printf("\ninput the %dth node of value\n", n); for(i=1; i<=n; i++) { scanf("%d", &wei); w[i] = wei; } CreatHuff(&HT, w, n); return 0; } /* 请在这里填写答案 */
这是部分代码,所以想请教大佬们下面该怎么做。我在二叉树方面的知识还很欠缺,所以还想请前辈们指教指教,帮助一下