题目来源：北航14级6系数据结构作业

【问题描述】
已知输入一串正整数，正整数之间用空格键分开，请建立一个哈夫曼树，以输入的数字为叶节点，求这棵哈夫曼树的带权路径长度。

【输入形式】
首先输入正整数的个数，然后接下来为接下来的正整数，正整数个数不超过10个

【输出形式】
输出相应的权值

【样例输入】
5 4 5 6 7 8

【样例输出】
69

求哈夫曼树的算法用的是递归，然而并不会写非递归的，还要花时间研究一下，这次没有看清楚输入的要求，走了，不少的弯路，下次看题目一定要认真啊

@H_301_31@#include <stdio.h> #include <stdlib.h> #define MAXNUM 20 typedef struct BTNode { int data; struct BTNode *lchild,*rchild; }BTNode,*BTree; typedef struct Node { BTree bt; struct Node *link; } Node,*Forest; void insertForestNode ( BTree t,Forest fr,Forest head); void destoryBTree ( BTree t ); void getWPL( BTree t,int depth,int *WPL); int main() { int num; int n; int i; Forest head,top,fr,p,q; BTree t,root,t1,t2; int WPL = 0; head = (Forest)malloc(sizeof(Node)); head->link = NULL; scanf("%d",&n); //用链式队列存森林 i = 1; while( i <= n ) { scanf("%d",&num); t = (BTree)malloc(sizeof(BTNode)); t->data = num; t->lchild = t->rchild = NULL; fr = (Forest)malloc(sizeof(Node)); fr->bt = t; fr->link = NULL; //将元素从大到小排列 if( head->link == NULL) { head->link= fr; //top = fr; } else insertForestNode(t,head); i++; } //构造哈夫曼树 while( head->link != NULL ) { t = (BTree)malloc(sizeof(BTNode)); q = (Forest)malloc(sizeof(Node)); q->bt = t; q->link = NULL; t1 = head->link->bt; p = head->link; head->link = p->link; t->lchild = t1; free(p); t2 = head->link->bt; p = head->link; head->link = p->link; t->rchild = t2; free(p); t->data = t1->data + t2->data; if(head->link != NULL) insertForestNode(t,q,head); } free(head); getWPL(t,&WPL); printf("%d",WPL); destoryBTree(t); t = NULL; return 0; } void insertForestNode ( BTree t,Forest head ) { Forest p = head->link,q; while ( p != NULL ) { if( fr->bt->data > p->bt->data) { q = p; p = p->link; } else { fr->link = p; if( p == head->link) head->link = fr; else q->link = fr; break; } } if( p == NULL) q->link = fr; } //int getWPL ( BTree t) { // // int depth = 0; // int top = -1; // int WPL = 0; // BTree Stack[MAXNUM]; // BTree p; // // p = t; //// do{ //// //// while( p != NULL ) { //// Stack[++top] = p; //// p = p->lchild; //// depth++; //// } //// //// p = Stack[top--]; //// WPL = WPL + p->data*(--depth); //// p = //// //// } while ( p != NULL || top != -1 ); // do{ // // if( p->lchild != NULL && p->rchild != NULL ) { // Stack[++top] = p; // depth++; // p = p->lchild; // // } // // else { // WPL = WPL + p->data*(depth); // p = Stack[top]->rchild; // top--; // // } // } while( top != -1); // // return WPL; //} void getWPL( BTree t,int *WPL) { if( t->lchild == NULL && t->rchild == NULL) { (*WPL) += depth*t->data; } else{ getWPL(t->lchild,depth+1,WPL); getWPL(t->rchild,WPL); } } //二叉树的销毁 void destoryBTree ( BTree t ) { if( t != NULL ) { destoryBTree(t->lchild); destoryBTree(t->rchild); free(t); } }

经过某同学指点，利用了队列和按层次遍历，这下就可以有非递归算法了

先定义一个结构存有节点地址和其高度

@H_301_31@struct depthBuffmanTree { BTree bt; int depth; };
接着是 @H_301_31@//非递归算法 int getWPL2(BTree t) { struct depthBuffmanTree queue[MAXNUM]; struct depthBuffmanTree p; int front = -1; int rear = 0; int WPL = 0; queue[0].bt = t; queue[0].depth = 0; while( front < rear ) { p = queue[++front]; if(p.bt->lchild == NULL && p.bt->rchild == NULL) { WPL += p.bt->data*p.depth; } if( p.bt->lchild != NULL ) { queue[++rear].bt = p.bt->lchild; queue[rear].depth = p.depth + 1; } if( p.bt->rchild != NULL ) { queue[++rear].bt = p.bt->rchild; queue[rear].depth = p.depth + 1; } } return WPL; }

本文为我本人原创

我的邮箱：tao20dage@qq.com,欢迎交流