哈夫曼树(C语言实现)——最优二叉树_Mr
- #include<stdio.h>
- #include<stdlib.h>
- #include<stdbool.h>
- #define MaxSize 100
- // 哈夫曼树的结点元素类型
- typedef struct HTNode
- {
- int weight; // 权值
- int parent, lchild, rchild; // 双亲结点、左、右孩子结点在数组中的下标
-
- }ElemType;
-
- typedef struct
- {
- ElemType * data; // 数组存储哈夫曼树结点
- int n; // 记录树结点的个数
-
- }HuffmanTree;
-
- void Init_HuffmanTree(HuffmanTree * T, int w[], int n); // 初始化哈夫曼树
- void Creat_HuffmanTree(HuffmanTree * T); // 建立哈夫曼树
- int* Select_MinIndex(HuffmanTree * T); // 挑选权值最小的两个根结点下标
- void Print_HuffmanTree(HuffmanTree * T); // 打印哈夫曼树
- void PreOrder_Traverse(HuffmanTree * T, int index); // 前序遍历哈夫曼树
- void InOrder_Traverse(HuffmanTree * T, int index); // 中序遍历哈夫曼树
- void PostOrder_Traverse(HuffmanTree * T, int index); // 后序遍历哈夫曼树
- void Level_Traverse(HuffmanTree * T, int index); // 层序遍历哈夫曼树
-
- int main()
- {
- int n;
- HuffmanTree T;
- int w[250] = {2,3,4,5};
- printf("请输入哈夫曼树叶子结点的个数:");
- scanf("%%d",&n);
- Init_HuffmanTree(&T, w, n);
- Creat_HuffmanTree(&T);
- printf("打印哈夫曼树:");
- Print_HuffmanTree(&T);
-
- printf("前序遍历:");
- PreOrder_Traverse(&T, T.n-1); // 数组下标越大,权值越大,越靠近根结点
- printf("
");
-
- printf("中序遍历:");
- InOrder_Traverse(&T, T.n-1);
- printf("
");
-
- printf("后序遍历:");
- PostOrder_Traverse(&T, T.n-1);
- printf("
");
-
- return 0;
- }
-
- void Init_HuffmanTree(HuffmanTree * T, int w[], int n)
- {
- int i;
- T->data = (ElemType*)malloc(sizeof(ElemType)*(2*n-1)); // 动态分配数组存储空间
- T->n = n;
-
- // 构造n棵只有根结点的树
- for(i=0; i<n; i++)
- T->data[i].weight = w[i];
-
- for(i=0; i<2*n-1; ++i)
- {
- // 初始化,所有结点都没有双亲和左、右孩子
- T->data[i].parent = -1;
- T->data[i].lchild = -1;
- T->data[i].rchild = -1;
- }
- }
-
- void Creat_HuffmanTree(HuffmanTree * T)
- {
- int k;
- int n = T->n;
- int m = 2*n-1;
-
- for(k=n; k<m; ++k) // n-1次合并
- {
- int * res = Select_MinIndex(T); // 求出权值最小的两个下标
- int index1 = res[0];
- int index2 = res[1];
- T->data[k].weight = T->data[index1].weight + T->data[index2].weight;
- T->data[k].lchild = index1;
- T->data[k].rchild = index2;
- T->data[index1].parent = k;
- T->data[index2].parent = k;
- T->n++;
- }
-
- return ;
- }
-
- int* Select_MinIndex(HuffmanTree * T)
- {
- int i;
- int firstindex,secondindex;
- int firstmin = 1000;
- int secondmin = 1000;
-
- for(i=0; i<T->n; ++i)
- {
- if(T->data[i].parent == -1)
- {
- if(T->data[i].weight<firstmin)
- {
- firstmin = T->data[i].weight;
- firstindex = i;
- }
- }
- }
-
- for(i=0; i<T->n; ++i)
- {
- if(T->data[i].parent == -1)
- {
- if(T->data[i].weight<secondmin && T->data[i].weight!=firstmin)
- {
- secondmin = T->data[i].weight;
- secondindex = i;
- }
- }
- }
-
- int * res = (int*)malloc(sizeof(int)*2);
- res[0] = firstindex;
- res[1] = secondindex;
- return res;
- }
-
- void Print_HuffmanTree(HuffmanTree * T)
- {
- int i;
-
- printf("
哈夫曼树各项数据如下表所示:
");
- printf("————————————————————————
");
- printf("数组下标 weight parent lchild rchild
");
- for(i=0; i<T->n-1; ++i)
- {
- printf(" %%d %%d %%d %%d %%d
",i,T->data[i].weight,T->data[i].parent,T->data[i].lchild,T->data[i].rchild);
- }
- printf(" %%d %%d %%d %%d %%d
",i,T->data[i].weight,T->data[i].parent,T->data[i].lchild,T->data[i].rchild);
- printf("————————————————————————
");
- }
-
- void PreOrder_Traverse(HuffmanTree * T, int index)
- {
- if(index != -1)
- {
- printf("%%3d", T->data[index].weight);
- PreOrder_Traverse(T, T->data[index].lchild);
- PreOrder_Traverse(T, T->data[index].rchild);
- }
- }
-
- void InOrder_Traverse(HuffmanTree * T, int index)
- {
- if(index != -1)
- {
- InOrder_Traverse(T, T->data[index].lchild);
- printf("%%3d", T->data[index].weight);
- InOrder_Traverse(T, T->data[index].rchild);
- }
- }
-
- void PostOrder_Traverse(HuffmanTree * T, int index)
- {
- if(index != -1)
- {
- PostOrder_Traverse(T, T->data[index].lchild);
- PostOrder_Traverse(T, T->data[index].rchild);
- printf("%%3d", T->data[index].weight);
- }
- }
推荐阅读