服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

香港云服务器
服务器之家 - 编程语言 - C/C++ - C语言实现哈夫曼树的构建

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

2021-09-03 14:58dmfrm C/C++

这篇文章主要为大家详细介绍了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++深入理解goto语句的替代实现方式分析

    深入理解goto语句的替代实现方式分析

    本篇文章是对goto语句的替代实现方式进行了详细的分析介绍,需要的朋友参考下...

    C语言教程网7342020-12-03
  • C/C++C/C++经典实例之模拟计算器示例代码

    C/C++经典实例之模拟计算器示例代码

    最近在看到的一个需求,本以为比较简单,但花了不少时间,所以下面这篇文章主要给大家介绍了关于C/C++经典实例之模拟计算器的相关资料,文中通过示...

    jia150610152021-06-07
  • C/C++c++ 单线程实现同时监听多个端口

    c++ 单线程实现同时监听多个端口

    这篇文章主要介绍了c++ 单线程实现同时监听多个端口的方法,帮助大家更好的理解和学习使用c++,感兴趣的朋友可以了解下...

    源之缘11542021-10-27
  • C/C++C语言实现电脑关机程序

    C语言实现电脑关机程序

    这篇文章主要为大家详细介绍了C语言实现电脑关机程序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...

    xiaocaidayong8482021-08-20
  • C/C++学习C++编程的必备软件

    学习C++编程的必备软件

    本文给大家分享的是作者在学习使用C++进行编程的时候所用到的一些常用的软件,这里推荐给大家...

    谢恩铭10102021-05-08
  • C/C++C++之重载 重定义与重写用法详解

    C++之重载 重定义与重写用法详解

    这篇文章主要介绍了C++之重载 重定义与重写用法详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...

    青山的青6062022-01-04
  • C/C++详解c语言中的 strcpy和strncpy字符串函数使用

    详解c语言中的 strcpy和strncpy字符串函数使用

    strcpy 和strcnpy函数是字符串复制函数。接下来通过本文给大家介绍c语言中的strcpy和strncpy字符串函数使用,感兴趣的朋友跟随小编要求看看吧...

    spring-go5642021-07-02
  • C/C++C语言中炫酷的文件操作实例详解

    C语言中炫酷的文件操作实例详解

    内存中的数据都是暂时的,当程序结束时,它们都将丢失,为了永久性的保存大量的数据,C语言提供了对文件的操作,这篇文章主要给大家介绍了关于C语言中文件...

    针眼_6702022-01-24
571