首页 > 其他分享 >Huffman Tree in C

Huffman Tree in C

时间:2023-10-18 14:57:10浏览次数:30  
标签:struct weight int Tree HuffmanTree Huffman 节点 HTNode

//
//  main.c
//  HuffmanTree
//
//  Created by steve xiaohu zhao on 2023/10/18.
//

#include <stdio.h>
#include <stdlib.h>

// 定义一个 Huffman Tree 的节点
struct HTNode {
    // 表示权值
    int weight;
    // 定义一个左节点和右节点指针
    struct HTNode *left, *right;
};

// 为节点起个别名
typedef struct HTNode *HuffmanTree;


// 创建哈夫曼树(用堆来实现)
HuffmanTree CreateHuffmanTree(MinHeap H) {
    
    // 假设 H->Size 个权值已经保存在 H->Elements[]->Weight 里面
    int i;
    HuffmanTree T;
    
    // 将 H->Elements[] 按权值调整为最小堆
    BuildMinHeap(H);
    
    // 做 H->Size - 1 次合并
    for (int i = 1; i < H->Size; i++) {
        // 建立新节点
        T = malloc(sizeof(struct HTNode));
        
        // 从最小堆中删除一个节点,作为新 T 的左子节点
        T->left = DeleteMin(H);
        
        // 从做小堆中删除一个节点,作为新 T 的右子节点
        T->right = DeleteMin(H);
        
        // 计算新的权值
        T->weight = T->left->weight + T->right->weight;
        
        // 将新 T 插入最小堆
        Insert(H, T);
    }
    
    T = DeleteMin(H);
    
    return T;
    
    // 整体复杂度为:O(N*logN)
    
}


int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    return 0;
}


标签:struct,weight,int,Tree,HuffmanTree,Huffman,节点,HTNode
From: https://www.cnblogs.com/zxhoo/p/17772332.html

相关文章

  • [题解] CF1790E - XOR Tree
    CF1790E-XORTree题意给定一颗无根树,在可以改变任意一个点的点权操作基础上,让树上任意简单路径的异或和不为\(0\),问最少需要多少次操作。思路假设某个点为根,设\(pre_x\)为\(x\)点到根的树上前缀异或和,\(a_x\)为\(x\)的点权,则\(x\)和\(y\)之间简单路径的异或和......
  • WPF控件ItemsControl、ListBox、ListView、DataGrid、TreeView、TabControl用法及区别
    1.ItemsControltemsControl是WPF中最基本的控件之一,用于显示一个数据项集合。它允许按照自定义方式呈现任何类型的对象,可以在其中使用不同的布局和面板来展示数据。ItemsControl非常灵活,可以满足各种需求。以下是一个简单的ItemsControl的XAML示例,它使用StackPanel作为布局容器,......
  • CF1873F Money Trees
    CF1873FMoneyTrees双指针好题,但是我用的队列(考虑先找出所有极长的、满足任意一个数都能被它后面的那个数整除的连续段。显然这个操作可以在\(\mathcal{O}(n)\)的时间复杂度内完成。求出每个极长连续段的答案,取\(\max\)即为最终答案。那么现在的问题就是求一个数列中,满......
  • Binary Tree Postorder Traversal
    SourceGivenabinarytree,returnthepostordertraversalofitsnodes'values.ExampleGivenbinarytree{1,#,2,3},1\2/3return[3,2,1].ChallengeCanyoudoitwithoutrecursion?题解1-递归首先使用递归便于理解。C++-Tra......
  • btree 与 b+tree 的区别
    btree:1.关键字和记录放在一起     2.越靠近根节点的记录查询速度越快b+tree:1.非叶子节点中只有关键字和指向下一个节点的索引,记录只放在叶子节点中      2.查询都需要从根节点走到叶子节点,叶子节点还要进行关键字的比较,每个记录的查询时间基本相同......
  • Oracle索引之(b-tree、bitmap、聚集、非聚集)
    Oracle索引之(b-tree、bitmap、聚集、非聚集)一、B-TREE索引一个B树索引只有一个根节点,它实际就是位于树的最顶端的分支节点。可以用下图一来描述B树索引的结构。其中,B表示分支节点,而L表示叶子节点。对于分支节点块(包括根节点块)来说,其所包含的索引条目都是按照顺序排列的(缺省是......
  • MEX Tree
    MEXTreeMEXTree-洛谷|计算机科学教育新生态(luogu.com.cn)目录MEXTree题目大意基本思路询问修改code题目大意给出一棵\(n\)个点的树,点从\(0\)到\(n-1\)编号。定义一条路径的权值是路径上所有点编号的\(mex\)。对于每个\(0\lei\len\)求出\(mex\)为\(i......
  • CF963B Destruction of a Tree 题解
    CF963BDestructionofaTree题解  洛谷题目链接  这里提供一个较为朴素的DP想法。题意简述  给定一棵树,节点个数不超过\(2\times10^5\),每次可以删掉度数为偶数的点。问最后能不能删完;能删完给出删除方案。思路分析  首先可以随便选一个点作为根。  其次,......
  • 动态树(Link-Cut Tree)
    算法思想动态树算法用于解决一类树上问题,涉及树边的连接和断开,并借助splay实现高效维护树上路径信息。算法细节见YangZhe的论文代码实现P3690【模板】动态树(LCT)#include<bits/stdc++.h>#definelllonglong#defineilinlineusingnamespacestd;intread(){in......
  • [gym103860D]Tree Partition
    D-TreePartition考虑将树转换到一个序列上,钦定\(1\)为根节点,\(1\)的父亲为\(0\),在序列上,孩子向父亲连边然后考虑设\(dp\)状态\(dp[i][j]\)表示前\(i\)个点,分成\(j\)段的方案数,那么\(dp[i][j]\)从\(dp[k][j-1]\)转移过来要满足以下条件之一:点\(i\)的后向边\((a,b)\)满足\(a\l......