个人中心
gpt4 book ai didi

C语言实现哈夫曼树的构建

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 27 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C语言实现哈夫曼树的构建由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

哈夫曼树（霍夫曼树）又称为最优树. 。

1、路径和路径长度 。

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1.

2、结点的权及带权路径长度 。

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积.

3、树的带权路径长度 。

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
/* 哈夫曼树的结构体 */
typedef struct stHuNode
{
   int data; //权值
   struct stHuNode* lchild, *rchild;
}HUNODE;
 
 
/*
* 找出权值数组里面,最小的两个权值下标
* 函数请参：HUNODE *pArray[] 存放节点的指针数组
       int n 数组里面的元素个数
       int* p1 存放最小权值的下标
       int* p2 存放第二小权值的下标
*/
int findSmallData(HUNODE *pArray[] , int n, int * p1, int * p2)
{
   int index = 0;
   int fir_small = 0xffff, sec_small = 0xffff;
 
   if (pArray == NULL)
   {
     return 1;
   }
 
   for (index = 0; index < n; index++)
   {
     /* 当前的下标下面是有节点的*/
     if (pArray[index] != NULL)
     {
       if (pArray[index]->data < fir_small)
       {
         sec_small = fir_small;
         fir_small = pArray[index]->data;
 
         *p2 = *p1;
         *p1 = index;       
       }
       else if (pArray[index]->data < sec_small)
       {
         sec_small = pArray[index]->data;
         *p2 = index;
       }
     }   
   }
 
   return 0;
}
/*
* 函数功能：构建哈夫曼树
* 函数请参：int* a 权值数组
       int n 这个数组里面有多少个数据
*/
 
HUNODE* createHuTree( int * a, int n)
{
   int index = 0;
 
   int fir_small = 0, sec_small = 0;
 
   /* 定义一个指针数组,最大是100 */
   HUNODE *pArray[100];
   HUNODE *pNewNode = NULL;
 
 
   /* 先创建n个root节点*/
   memset (pArray,0, sizeof (HUNODE)*n);
   for (index = 0; index < n; index++)
   {
     pNewNode = (HUNODE*) malloc ( sizeof (HUNODE));
     memset (pNewNode,0, sizeof (HUNODE));
 
     pNewNode->data = a[index];
     pNewNode->lchild = NULL;
     pNewNode->rchild = NULL;
 
     /* 把这个节点存放在指针数组中去 */
     pArray[index] = pNewNode;
   }
 
   /* 构建哈夫曼树 */
   for (index = 0; index < n-1; index++)
   {
     /* fir_small 存放最小权值的下标 sec_small存放第二个小的权值下标*/
     findSmallData(pArray,n,&fir_small,&sec_small);
 
     /* 分配节点内存 */
     pNewNode = (HUNODE*) malloc ( sizeof (HUNODE));
     memset (pNewNode,0, sizeof (HUNODE));
 
     pNewNode->data = pArray[fir_small]->data + pArray[sec_small]->data;
 
     /* 最小的是左孩子，第二小的是右孩子 */
     pNewNode->lchild = pArray[fir_small];
     pNewNode->rchild = pArray[sec_small];
 
     /* 把新的节点放入到指针数组里面去 */
     pArray[fir_small] = NULL;
     pArray[sec_small] = pNewNode;
 
   }
   return pNewNode;
}
 
/* 前序遍历该二叉树 */
void preOrderHuffMan(HUNODE* root)
{
   if (root)
   {
     printf ( "%d " ,root->data);
     preOrderHuffMan(root->lchild);
     preOrderHuffMan(root->rchild);
   }
}
 
int main()
{
   int a[4] = {7,5,2,4};
   HUNODE* root = NULL;
 
   /* 构建哈夫曼树 */
   root = createHuTree(a,4);
 
   /* 前序遍历 */
   preOrderHuffMan(root);
   printf ( "\n" );
 
   return 0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我.

原文链接：https://blog.csdn.net/u010889616/article/details/48052567 。

最后此篇关于C语言实现哈夫曼树的构建的文章就讲到这里了,如果你想了解更多关于C语言实现哈夫曼树的构建的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

27 4 0
文章推荐： 关于C++中strcpy函数例题讲解
文章推荐： C++实现哈夫曼树的方法
文章推荐： 一篇带你创建 Tekton 流水线
文章推荐： C语言实现哈夫曼树
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com