#define DeBUG #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <string> #include <set> #include <sstream> #include <map> #include <bitset> using namespace std ; #define zero {0} #define INF 0x3f3f3f3f #define EPS 1e-6 typedef long long LL; const double PI = acos(-1.0); //#pragma comment(linker,"/STACK:102400000,102400000") inline int sgn(double x) { return fabs(x) < EPS ? 0 : (x < 0 ? -1 : 1); } struct Node { Node *left,*right;//左右孩子 Node *parent;//父节点 bool flag;//是否为插入节点 int value;//节点值 Node() {} Node(int x,Node *l,Node *r,Node *p,bool isnode) { value = x; left = l; right = r; parent = p; flag = isnode; } bool lessthan(const Node *pnode) const//用于优先队列的比较 { return value > pnode->value; } }; struct nodePointerComparer { nodePointerComparer() {} bool operator ()(const Node *a,const Node *b) const { return a->lessthan(b); } }; void layerOrder(Node *p) { if (p != NULL) { queue<Node *>st; st.push(p); while (!st.empty()) { Node *now = st.front(); st.pop(); if ( now->parent != NULL) { if (now->parent->right == now) printf("(%d->%d) ",now->parent->value,now->value); else printf("(%d<-%d) ",now->value); } else printf("(%d-%d) ",now->value); if (now->left != NULL) { st.push(now->left); } if (now->right != NULL) { st.push(now->right); } } } printf("\n"); } char code[100]; void dfs(Node *p,int deep) { if (p->left != NULL) { code[deep] = '0'; dfs(p->left,deep + 1); code[deep] = '\0'; } if (p->right != NULL) { code[deep] = '1'; dfs(p->right,deep + 1); code[deep] = '\0'; } if (p->right == NULL && p->left == NULL) { if (p->flag) printf("%d: %s\n",p->value,code); } } int main() { #ifdef DeBUGs freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin); #endif printf("输入节点:\n"); int v; priority_queue<Node *,vector<Node *>,nodePointerComparer>pQ; while (scanf("%d",&v) + 1) { pQ.push(new Node(v,NULL,true)); } Node *root; Node *l,*r; while (!pQ.empty()) { if (!pQ.empty()) { l = pQ.top(); pQ.pop(); } if (!pQ.empty()) { r = pQ.top(); pQ.pop(); } if (r) { root = new Node(l->value + r->value,l,r,false); l->parent = root; r->parent = root; pQ.push(root); } else { root = l; } l = r = NULL; } printf("生成huffman树层序遍历:\n"); layerOrder(root); printf("生成编码:\n"); memset(code,sizeof(code)); dfs(root,0); return 0; }