WHCSRL 技术网

哈夫曼树(C语言实现)——最优二叉树_Mr

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<stdbool.h>
  4. #define MaxSize 100
  5. // 哈夫曼树的结点元素类型
  6. typedef struct HTNode
  7. {
  8. int weight; // 权值
  9. int parent, lchild, rchild; // 双亲结点、左、右孩子结点在数组中的下标
  10. }ElemType;
  11. typedef struct
  12. {
  13. ElemType * data; // 数组存储哈夫曼树结点
  14. int n; // 记录树结点的个数
  15. }HuffmanTree;
  16. void Init_HuffmanTree(HuffmanTree * T, int w[], int n); // 初始化哈夫曼树
  17. void Creat_HuffmanTree(HuffmanTree * T); // 建立哈夫曼树
  18. int* Select_MinIndex(HuffmanTree * T); // 挑选权值最小的两个根结点下标
  19. void Print_HuffmanTree(HuffmanTree * T); // 打印哈夫曼树
  20. void PreOrder_Traverse(HuffmanTree * T, int index); // 前序遍历哈夫曼树
  21. void InOrder_Traverse(HuffmanTree * T, int index); // 中序遍历哈夫曼树
  22. void PostOrder_Traverse(HuffmanTree * T, int index); // 后序遍历哈夫曼树
  23. void Level_Traverse(HuffmanTree * T, int index); // 层序遍历哈夫曼树
  24. int main()
  25. {
  26. int n;
  27. HuffmanTree T;
  28. int w[250] = {2,3,4,5};
  29. printf("请输入哈夫曼树叶子结点的个数:");
  30. scanf("%%d",&n);
  31. Init_HuffmanTree(&T, w, n);
  32. Creat_HuffmanTree(&T);
  33. printf("打印哈夫曼树:");
  34. Print_HuffmanTree(&T);
  35. printf("前序遍历:");
  36. PreOrder_Traverse(&T, T.n-1); // 数组下标越大,权值越大,越靠近根结点
  37. printf(" ");
  38. printf("中序遍历:");
  39. InOrder_Traverse(&T, T.n-1);
  40. printf(" ");
  41. printf("后序遍历:");
  42. PostOrder_Traverse(&T, T.n-1);
  43. printf(" ");
  44. return 0;
  45. }
  46. void Init_HuffmanTree(HuffmanTree * T, int w[], int n)
  47. {
  48. int i;
  49. T->data = (ElemType*)malloc(sizeof(ElemType)*(2*n-1)); // 动态分配数组存储空间
  50. T->n = n;
  51. // 构造n棵只有根结点的树
  52. for(i=0; i<n; i++)
  53. T->data[i].weight = w[i];
  54. for(i=0; i<2*n-1; ++i)
  55. {
  56. // 初始化,所有结点都没有双亲和左、右孩子
  57. T->data[i].parent = -1;
  58. T->data[i].lchild = -1;
  59. T->data[i].rchild = -1;
  60. }
  61. }
  62. void Creat_HuffmanTree(HuffmanTree * T)
  63. {
  64. int k;
  65. int n = T->n;
  66. int m = 2*n-1;
  67. for(k=n; k<m; ++k) // n-1次合并
  68. {
  69. int * res = Select_MinIndex(T); // 求出权值最小的两个下标
  70. int index1 = res[0];
  71. int index2 = res[1];
  72. T->data[k].weight = T->data[index1].weight + T->data[index2].weight;
  73. T->data[k].lchild = index1;
  74. T->data[k].rchild = index2;
  75. T->data[index1].parent = k;
  76. T->data[index2].parent = k;
  77. T->n++;
  78. }
  79. return ;
  80. }
  81. int* Select_MinIndex(HuffmanTree * T)
  82. {
  83. int i;
  84. int firstindex,secondindex;
  85. int firstmin = 1000;
  86. int secondmin = 1000;
  87. for(i=0; i<T->n; ++i)
  88. {
  89. if(T->data[i].parent == -1)
  90. {
  91. if(T->data[i].weight<firstmin)
  92. {
  93. firstmin = T->data[i].weight;
  94. firstindex = i;
  95. }
  96. }
  97. }
  98. for(i=0; i<T->n; ++i)
  99. {
  100. if(T->data[i].parent == -1)
  101. {
  102. if(T->data[i].weight<secondmin && T->data[i].weight!=firstmin)
  103. {
  104. secondmin = T->data[i].weight;
  105. secondindex = i;
  106. }
  107. }
  108. }
  109. int * res = (int*)malloc(sizeof(int)*2);
  110. res[0] = firstindex;
  111. res[1] = secondindex;
  112. return res;
  113. }
  114. void Print_HuffmanTree(HuffmanTree * T)
  115. {
  116. int i;
  117. printf(" 哈夫曼树各项数据如下表所示: ");
  118. printf("———————————————————————— ");
  119. printf("数组下标 weight parent lchild rchild ");
  120. for(i=0; i<T->n-1; ++i)
  121. {
  122. printf(" %%d %%d %%d %%d %%d ",i,T->data[i].weight,T->data[i].parent,T->data[i].lchild,T->data[i].rchild);
  123. }
  124. printf(" %%d %%d %%d %%d %%d ",i,T->data[i].weight,T->data[i].parent,T->data[i].lchild,T->data[i].rchild);
  125. printf("———————————————————————— ");
  126. }
  127. void PreOrder_Traverse(HuffmanTree * T, int index)
  128. {
  129. if(index != -1)
  130. {
  131. printf("%%3d", T->data[index].weight);
  132. PreOrder_Traverse(T, T->data[index].lchild);
  133. PreOrder_Traverse(T, T->data[index].rchild);
  134. }
  135. }
  136. void InOrder_Traverse(HuffmanTree * T, int index)
  137. {
  138. if(index != -1)
  139. {
  140. InOrder_Traverse(T, T->data[index].lchild);
  141. printf("%%3d", T->data[index].weight);
  142. InOrder_Traverse(T, T->data[index].rchild);
  143. }
  144. }
  145. void PostOrder_Traverse(HuffmanTree * T, int index)
  146. {
  147. if(index != -1)
  148. {
  149. PostOrder_Traverse(T, T->data[index].lchild);
  150. PostOrder_Traverse(T, T->data[index].rchild);
  151. printf("%%3d", T->data[index].weight);
  152. }
  153. }

 

 

推荐阅读