C语言，哈夫曼编码。采用三重链表创建二叉树，另外又设计了函数实现建立哈夫曼树，编码哈夫曼树。源代码中还包括了递归方法先序，中序，后序遍历二叉树，以及非递归方法按层次遍历二叉树。当然也可对哈夫曼树实现上述遍历。该程序也可计算二叉树节点数量，高度，叶子结点数量，对叶子结点按层次遍历。最后根据叶子结点实现哈夫曼编码。
#include<stdio.h> #include<stdlib.h> typedef struct btnode { int element; struct btnode* Lchild, * Rchild, * Father; }BTNode; typedef struct btree { struct btnode* Root; }BTree; BTNode* NewNode() { BTNode* p = (BTNode*)malloc(sizeof(BTNode)); return p; } void CreateBT(BTree* bt) { bt->Root = NULL; } void MakeBT(BTree* bt, int x, BTree* lt, BTree* rt) { BTNode* p = NewNode(); p->element = x; p->Father = NULL; if (rt->Root != NULL) { rt->Root->Father = p; } p->Rchild = rt->Root; if (lt->Root != NULL) { lt->Root->Father = p; } p->Lchild = lt->Root; lt->Root = rt->Root = NULL; bt->Root = p; } void BreakBT(BTree* bt, BTree* lt, BTree* rt) { BTNode* p = bt->Root; if § { lt->Root = p->Lchild; rt->Root = p->Rchild; bt->Root = NULL; free§; } }
int Size(BTNode* p) { int s, s1, s2; if (!p) { return 0; } else { s1 = Size(p->Lchild); s2 = Size(p->Rchild); s = s1 + s2 + 1; return s; } } int SizeofBT(BTree bt) { return Size(bt.Root); } void LevelOrd(BTree bt) { BTNode* p; BTNode* queue[256]; int front = -1, rear = -1; p = bt.Root; rear++; queue[rear] = p; printf(“按层次遍历树\n”); while (front != rear) { front++; p = queue[front]; printf("%d “, p->element); if (p->Lchild != NULL) { rear++; queue[rear] = p->Lchild; } if (p->Rchild != NULL) { rear++; queue[rear] = p->Rchild; } } printf(”\n"); } void HFMcode(BTree bt) { BTNode* p; BTNode* queue[256]; BTNode* leaf[256]; int i, co, j, m, le = 0; int front = -1, rear = -1; char code[100][100]; p = bt.Root; rear++; queue[rear] = p; while (front != rear) { front++; p = queue[front]; if (p->Lchild == NULL && p->Rchild == NULL) { leaf[le] = p; le++; } if (p->Lchild != NULL) { rear++; queue[rear] = p->Lchild; } if (p->Rchild != NULL) { rear++; queue[rear] = p->Rchild; }
} printf("按层次遍历，叶子节点分别为：\n"); for (i = 0; i < le; i++) { printf(" %d\t", leaf[i]->element); } printf("\n"); printf("对应的哈夫曼编码为： \n"); for (i = 0; i < le; i++) { co = 0; while (leaf[i]->Father != NULL) { if (leaf[i]->Father->Lchild == leaf[i]) { code[i][co] = '0'; co++; } if (leaf[i]->Father->Rchild == leaf[i]) { code[i][co] = '1'; co++; } leaf[i] = leaf[i]->Father; } code[i][co] = '\0'; } for (i = 0; i < le; i++) { m = 0; for (j = 0; code[i][j] != '\0'; j++) { m++; } for (j = m; j >= 0; j--) { printf("%c", code[i][j]); } printf("\t"); } printf("\n");} int Depth(BTNode* p) { if (!p) { return 0; } else { return 1 + max(Depth(p->Lchild), Depth(p->Rchild)); } } int DepthofBT(BTree bt) { return Depth(bt.Root); } int CountLeaf(BTNode* p, int count) { if (p != NULL) { if (p->Lchild == NULL && p->Rchild == NULL) { count++; } count = CountLeaf(p->Lchild, count); count = CountLeaf(p->Rchild, count); } return count; } int NumberofLeaf(BTree bt, int count) { return CountLeaf(bt.Root, count); } void Visit(BTNode* p) { printf("%d “, p->element); } void PreOrd(void (Visit)(BTNode u), BTNode* t) { if (t) { (Visit)(t); PreOrd(Visit, t->Lchild); PreOrd(Visit, t->Rchild); } } void InOrd(void (Visit)(BTNode u), BTNode t) { if (t) { InOrd(Visit, t->Lchild); (Visit)(t); InOrd(Visit, t->Rchild); } } void PostOrd(void (Visit)(BTNode u), BTNode t) { if (t) { PostOrd(Visit, t->Lchild); PostOrd(Visit, t->Rchild); (Visit)(t); } } void PreOrder(BTree bt, void (Visit)(BTNode u)) { PreOrd(Visit, bt->Root); } void InOrder(BTree* bt, void (Visit)(BTNode u)) { InOrd(Visit, bt->Root); } void PostOrder(BTree* bt, void (Visit)(BTNode u)) { PostOrd(Visit, bt->Root); } int Fmin(BTree ht[], int k) { int i, k1; int temp; temp = ht[0].Root->element; k1 = 0; for (i = 0; i <= k; i++) { if (temp > ht[i].Root->element) { temp = ht[i].Root->element; k1 = i; } } return k1; } int Fmin2(BTree ht[], int k) { int i, j, k1, k2; int temp, temp2; temp = ht[0].Root->element; k1 = 0; for (i = 0; i <= k; i++) { if (temp > ht[i].Root->element) { temp = ht[i].Root->element; k1 = i; } } if (k1 != 0) { temp2 = ht[0].Root->element; k2 = 0; for (j = 0; j <= k; j++) { if (k1 == j) { continue; } if (temp2 > ht[j].Root->element) { temp2 = ht[j].Root->element; k2 = j; } } } else { temp2 = ht[1].Root->element; k2 = 1; for (j = 1; j <= k; j++) { if (temp2 > ht[j].Root->element) { temp2 = ht[j].Root->element; k2 = j; } } } return k2; } BTree CreateHFMTree(int n) { BTree ht[256]; int w[100]; int i, k, k1 = 0, k2 = 0; BTree* zero; zero = (BTree*)malloc(sizeof(BTree)); printf(“请输入各个权重指数： \n”); for (i = 0; i < n; i++) { scanf(”%d", &w[i]); getchar(); } CreateBT(zero); for (i = 0; i < n; i++) { MakeBT(&ht[i], w[i], zero, zero); } for (k = n - 1; k > 0; k–) { k1 = Fmin(ht, k); k2 = Fmin2(ht, k);
MakeBT(&ht[k1], ht[k1].Root->element + ht[k2].Root->element, &ht[k1], &ht[k2]); ht[k2] = ht[k]; } return ht[0];}
void main() { BTree bt; bt = CreateHFMTree(6); printf(“先序遍历哈夫曼树：”); PreOrder(&bt, Visit); printf("\n"); printf(“中序遍历哈夫曼树：”); InOrder(&bt, Visit); printf("\n"); printf(“后序遍历哈夫曼树：º”); PostOrder(&bt, Visit); printf("\n"); printf(“the total node number is: %d\n”, SizeofBT(bt)); printf(“the tree depth is: %d\n”, DepthofBT(bt)); printf(“the number of leaves is: %d\n”, NumberofLeaf(bt, 0)); LevelOrd(bt); HFMcode(bt); }
