主要是記錄一道九度的哈夫曼樹的題目 題目 [html] 題目描述： 哈夫曼樹，第一行輸入一個數n，表示葉結點的個數。需要用這些葉結點生成哈夫曼樹，根據哈夫曼樹的概念，這些結點有權值，即weight，題目需要輸出所有結點的值與權值的乘積之和。 輸入： 輸入有多組數據。 每組第一行輸入一個數n，接著輸入n個葉節點（葉節點權值不超過100，2<=n<=1000）。 輸出： 輸出權值。 樣例輸入： 5 1 2 2 5 9 樣例輸出： 37 ac代碼 [cpp] #include <stdio.h> #include <stdlib.h> #define max 1001 struct htree { int weight; struct htree *lchild; struct htree *rchild; struct htree *next; }; void addNode(struct htree *, struct htree *); struct htree* createHfmtree(int *, int); int getWpl(struct htree *, int); int main() { int w[max]; int i, n, wpl; struct htree *ht; while(scanf("%d", &n) != EOF) { for(i = 0; i < n; i ++) { scanf("%d", &w[i]); } ht = createHfmtree(w, n); wpl = getWpl(ht, 0); printf("%d\n", wpl); } return 0; } struct htree* createHfmtree(int *w, int n) { int i; struct htree *head, *pl, *pr, *proot; head = (struct htree *)malloc(sizeof(struct htree)); head->next = NULL; for(i = 0; i < n; i ++) { struct htree *pnode = malloc(sizeof(struct htree)); pnode->weight = *(w + i); pnode->lchild = pnode->rchild = pnode->next = NULL; addNode(head, pnode); } while(head->next) { if(head->next->next == NULL) break; pl = head->next; pr = pl->next; head->next = pr->next; proot = (struct htree *)malloc(sizeof(struct htree)); proot->weight = pl->weight + pr->weight; proot->lchild = pl; proot->rchild = pr; addNode(head, proot); } return head->next; } void addNode(struct htree *head, struct htree *pnode) { struct htree *t = head; while(t->next && t->next->weight < pnode->weight) t = t->next; pnode->next = t->next; t->next = pnode; } www.2cto.com int getWpl(struct htree *ht, int level) { if(ht == NULL) return 0; if(!ht->lchild && !ht->rchild) { return ht->weight * level; } return getWpl(ht->lchild, level + 1) + getWpl(ht->rchild, level + 1); }
