huffman二叉树 java_Java－－－Huffman树的实现

偏执的太偏执、 2022-11-04 15:21 122阅读 0赞

packagecom.newer.tree;/\*\*\* 　　　　　　　　　　我的哈弗曼树

\* 什么是哈弗曼树：哈弗曼树是最优二叉树，树的带权路径长度最小的一个二叉树。

\* 带权路径长度为根节点到该节点的路径长度和该节点权重的乘积。

\* 路径长度为当前节点到另一个节点所经过的分支的个数(边的个数)。

\*

\* 应用场景：哈弗曼树可以用来求哈弗曼编码，通过对文件中不同数据出现的频率，

\* 设计出新的编码方式，来对文件进行数据压缩。

\* 建立哈弗曼树:

\* １．将表示不同数据的节点按照出现的频率(权重)进行排序。

\* ２．选取出两个最小频率(权重)的数据，创建新节点，作为新节点的两个子节点。

\* ３．将两个子节点从原有的节点集删除，计算新节点的权重，并将其加入到节点集合中。

\* ４．对新的节点集进行排序，重复２和３步骤，直到节点集中只有一个节点。

\*

\*@authorlixiaochi

\*\*/

public classMyHuffmanTree \{//哈弗曼树的根节点

HuffmaNode root;public static voidmain(String\[\] args) \{

MyHuffmanTree huffmantree= newMyHuffmanTree();//数组中的元素是一个节点，节点中有数据内容和出现的频率。

HuffmaNode\[\] nodeArray = new HuffmaNode\[6\];//哈弗曼树中各个节点的初始化。

nodeArray\[0\]=new HuffmaNode("A",27);

nodeArray\[1\]=new HuffmaNode("B",8);

nodeArray\[2\]=new HuffmaNode("C",15);

nodeArray\[3\]=new HuffmaNode("D",15);

nodeArray\[4\]=new HuffmaNode("E",30);

nodeArray\[5\]=new HuffmaNode("F",5);//创建一颗哈弗曼树

huffmantree.root =huffmantree.create(nodeArray);//对哈弗曼树进行编码，其实可以在生成哈弗曼树的时候，一起生成哈弗曼编码。

encode(huffmantree.root);//按先序的方式输出哈弗曼树的每个节点的信息。

print(huffmantree.root);

\}public staticHuffmaNode create(HuffmaNode\[\] nodeArray) \{//表示当前要排序的起始位置

int num = 0;//不断循环，一直到节点集只有一个节点。

while(num

for(int i=num;i

min=j;

\}

\}

swap(nodeArray,i,min);

\}//创建新节点，记录新节点的权重

int newNodeValue = nodeArray\[num\].value+nodeArray\[num+1\].value;

HuffmaNode newNode= new HuffmaNode("分支节点",newNodeValue,nodeArray\[num\],nodeArray\[num+1\]);//将节点加入到节点集中，这里的num表示的起始位置，已经实现了在节点集数组中删除两个节点。

nodeArray\[++num\] =newNode;

\}returnnodeArray\[num\];

\}private static void swap(HuffmaNode\[\] nodeArray, int i, intmin) \{

HuffmaNode temp=nodeArray\[i\];

nodeArray\[i\]=nodeArray\[min\];

nodeArray\[min\]=temp;

\}public static voidencode(HuffmaNode node) \{

encode(node,"0","1","");

\}//对哈弗曼树中叶子节点进行编码。

public static voidencode(HuffmaNode node,String a,String b,String c) \{if(node.leftChild != null) \{

String temp= c+"0";

encode(node.leftChild,"0","1",temp);

\}if(node.rightChild != null) \{

String temp= c+"1";

encode(node.rightChild,"0","1",temp);

\}if(node.leftChild==null && node.rightChild==null) \{

node.encode=c;

\}

\}//按先序的方式输出哈弗曼树的每个节点的信息。

public static voidprint(HuffmaNode node) \{if(node != null) \{

System.out.println(node);

print(node.leftChild);

print(node.rightChild);

\}

\}

\}

发表评论取消回复

表情：

评论列表（有 0 条评论，122人围观）

还没有评论，来说两句吧...

相关阅读

相关 Huffman树

一颗k叉Huffman树是如下问题的解：构造一颗n个叶子节点的k叉树，叶子节点i有权值\\(w\_i\\)，使得Σ\\(w\_i \ l\_i\\)最小，其中\\(l\_i

淩亂°似流年/ 2023年08月17日 17:47/ 0 赞/ 94 阅读

相关树——二叉树——线索二叉树

一、线索二叉树 (1)什么是线索化将二叉树以某种次序将其遍历，得到线性序列，就是将非线性结构进行线索化。线索化的优点就是可以很快地得到前驱或后继。如

梦里梦外;/ 2023年06月13日 09:35/ 0 赞/ 14 阅读

相关 C语言实现二叉树---＞二叉查找树

声明代码实现都是自己写的，而且没有借鉴别人的代码，也没有看任何教程，只看了下二叉树的具体定义，知道大概是个什么东西说这些只是为了说明下列代码实现肯定不是最优的，甚

柔情只为你懂/ 2023年01月13日 06:19/ 0 赞/ 210 阅读

相关 huffman二叉树 java_Java－－－Huffman树的实现

packagecom.newer.tree;/\\\ 　　　　　　　　　　我的哈弗曼树 \ 什么是哈弗曼树：哈弗曼树是最优二叉树，树的带权路径长度最小的一个二叉树。 \ 带

偏执的太偏执、/ 2022年11月04日 15:21/ 0 赞/ 123 阅读

相关 python实现mysql二叉树_Python 二叉树实现

\二叉树实现 class Node(): def \_\_init\_\_(self,item): self.elem = item self.lchild = Non

一时失言乱红尘/ 2022年10月31日 15:54/ 0 赞/ 165 阅读

相关 Huffman算法实现最优二叉树（C++）

template<class Type> class node{ public: node():left(0),right(0){}

r囧r小猫/ 2022年06月10日 10:09/ 0 赞/ 159 阅读

相关 Huffman树的实现

昨天下午看了Huffman树的算法，写了部分代码，今天试着调试了一下，虽然过程有点坎坷，但是最终还是出来结果了。这个代码写的很粗糙，好多地方需要改进：比如选择最小的两个数的时候

快来打我*/ 2022年04月04日 05:42/ 0 赞/ 154 阅读

相关 Huffman树

实验题目(共6题, 第1题) <table> <tbody> <tr> <td>标题：</td> <td>Huffman树</td> </

╰+攻爆jí腚メ/ 2022年01月07日 16:15/ 0 赞/ 205 阅读

相关二叉树、满二叉树、完全二叉树、平衡二叉树（AVL树）

二叉树： -------------------- 二叉树由节点（node）和边组成。节点分为根节点、父节点、子节点。二叉树是每个结点最多有两个子树的树结构。 ![

柔情只为你懂/ 2021年12月23日 23:37/ 0 赞/ 504 阅读

相关 HUFFMAN 树

在一般的数据结构的书中，树的那章后面，著者一般都会介绍一下哈夫曼(HUFFMAN) 树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如 JPEG中就应用

古城微笑少年丶/ 2021年11月13日 15:00/ 0 赞/ 268 阅读