`
suhuanzheng7784877
  • 浏览: 702760 次
  • 性别: Icon_minigender_1
  • 来自: 北京
博客专栏
Ff8d036b-05a9-33b5-828a-2633bb68b7e6
读金庸故事,品程序人生
浏览量:47714
社区版块
存档分类
最新评论

Java基础复习笔记09数据结构-哈夫曼树

阅读更多

1.       哈夫曼树

哈夫曼树也称作最优二叉树,当树中的节点带了权重信息了,带权路径长度最小的二叉树叫做最优二叉树。带权路径长度=sum(权重*度)。sum代表每个节点的之和。加入有如下带权重的节点。

 权重分别是1584。那么关于这些零散的节点,最优二叉树该如何构建呢?

首先先将离散节点从小到大升序排序

第二从离散节点中在挑选排序前两个节点当做一个新的父节点的两个子节点

第三从离散的节点中去除刚刚使用的两个节点

第四重复第二和第三步骤,直到所有离散节点剔除完毕。哈夫曼树就构建完成

用图形演示过程如下

 可以看出所有的叶子节点就是之前的离散节点,如果在采用广度遍历法遍历此树。那么遍历的过程实际上就是最短遍历路径的遍历过程

2.       哈夫曼树的使用场景

其实哈夫曼树使用场景还真不少,例如apache负载均衡的按权重请求策略的底层算法、咱们生活中的路由器的路由算法、利用哈夫曼树实现汉字点阵字形的压缩存储(http://www.cnki.com.cn/Article/CJFDTotal-LYGY200504016.htm)、快速检索信息等等底层优化算法,其实核心就是因为目标带有权重、长度远近这类信息才能构建哈夫曼树模型。

3.       实现哈夫曼树

要想实现哈夫曼树其实就是将一堆零散的节点信息构建成一颗最优二叉树,之后再按广度优先遍历它。

实现哈夫曼树其实就是构建哈夫曼树的过程,原理其实上面已经说了,这里再重复一下。

首先先将离散节点从小到大升序排序

第二从离散节点中在挑选排序前两个节点当做一个新的父节点的两个子节点

第三从离散的节点中去除刚刚使用的两个节点

第四重复第二和第三步骤,直到所有离散节点剔除完毕。哈夫曼树就构建完成

代码以及测试程序如下

package dateStructer.tree.huffmanTree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * 哈夫曼树
 * 
 * @author liuyan
 */
public class HuffmanTree {

	/**
	 * 节点实体
	 */
	public static class Node<T> {

		// 数据
		T data;

		// 权重
		int power;

		Node<T> leftNode;

		Node<T> rightNode;

		public Node(T data, int power) {
			this.data = data;
			this.power = power;
		}

		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return "[data:" + data + "   power:" + power + "]";
		}

		@SuppressWarnings("unchecked")
		public boolean compareTo(Node node) {

			if (this.power < node.power) {
				return true;
			}

			return false;
		}

	}

	/**
	 * 将集合将序排序
	 * 
	 * @param <T>
	 * @param <E>
	 * 
	 * @param list
	 */
	@SuppressWarnings("unchecked")
	public static void sort(List<Node> list) {

		for (int i = 0; i < list.size() - 1; i++) {

			for (int j = i + 1; j < list.size(); j++) {

				if (list.get(i).compareTo(list.get(j))) {
					// 交换数组中的元素位置
					Node node = list.get(i);

					list.set(i, list.get(j));

					list.set(j, node);
				}

			}

		}

	}

	/**
	 * 创建哈夫曼树
	 * 
	 * @param list
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public static Node createHuffmanTree(List<Node> list) {

		while (list.size() > 1) {
			sort(list);

			Node left = list.get(list.size() - 1);

			Node right = list.get(list.size() - 2);

			Node parent = new Node("父节点", left.power + right.power);

			parent.leftNode = left;
			parent.rightNode = right;

			list.remove(list.size() - 1);
			list.remove(list.size() - 1);

			list.add(parent);
		}
		return list.get(0);
	}

	@SuppressWarnings("unchecked")
	public static List<Node> deepFirst(Node root) {

		List<Node> list = new ArrayList<Node>();
		Queue<Node> queue = new ArrayDeque<Node>();
		queue.add(root);

		while (!queue.isEmpty()) {

			list.add(queue.peek());

			Node twoLinkNode = queue.poll();

			if (twoLinkNode.leftNode != null) {
				queue.add(twoLinkNode.leftNode);
			}

			if (twoLinkNode.rightNode != null) {
				queue.add(twoLinkNode.rightNode);
			}
		}

		return list;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		List<Node> list = new ArrayList<Node>();
		Node<String> node1 = new Node<String>("东方不败", 8);
		Node<String> node2 = new Node<String>("风清扬", 5);
		Node<String> node3 = new Node<String>("岳不群", 4);
		Node<String> node4 = new Node<String>("左冷禅", 1);
		list.add(node1);
		list.add(node2);
		list.add(node3);
		list.add(node4);

		Node root = createHuffmanTree(list);
		System.out.println(deepFirst(root));
	}
}

 测试结果是

[[data:父节点   power:18], [data:东方不败   power:8], [data:父节点   power:10], [data:父节点   power:5], [data:风清扬   power:5], [data:左冷禅   power:1], [data:岳不群   power:4]]

 

  • 大小: 9.1 KB
  • 大小: 42.8 KB
分享到:
评论

相关推荐

    Java基础复习笔记07数据结构-树的概述

    在Java编程中,数据结构是解决问题的关键工具之一,其中树是一种非常重要的非线性数据结构。本篇复习笔记主要关注树的概述,包括树的概念、基本操作、使用场景以及一种特殊的树实现——记父节点实现。 1. **树的...

    数据结构--哈夫曼树的基本代码

    数据结构--哈夫曼树的基本代码 数据结构的重点算法之一

      数据结构-C语言-哈夫曼树

    C语言实现的哈夫曼树

    java数据结构-哈夫曼树

    ### Java数据结构—哈夫曼树 #### 一、哈夫曼树原理 哈夫曼树,也称为最优二叉树,是一种特殊的二叉树,它的特点是在所有可能的二叉树中,对于某一特定的权重集合,哈夫曼树具有最小的带权路径长度。在哈夫曼树中...

    数据结构-哈夫曼树编码译码-课程设计-实验报告_免费下载.doc.doc

    数据结构-哈夫曼树编码译码-课程设计-实验报告_免费下载.doc.doc

    数据结构-哈夫曼树的实现

    哈夫曼树(Huffman Tree),也称为最优二叉树,是数据结构中一种特殊的二叉树,主要用于数据的编码和解码,特别是在文本压缩领域有着广泛应用。它通过构造一个带权路径长度最短的二叉树来实现对数据的高效存储和检索...

    数据结构-哈夫曼树-实验-C语言实现

    数据结构——哈夫曼树——实验

    数据结构-哈夫曼树和哈夫曼编码.ppt

    "数据结构-哈夫曼树和哈夫曼编码" 哈夫曼树(Huffman Tree)是一种特殊的二叉树,它的特点是:有 n 个叶子结点,不存在度为 1 的结点,总的结点数为 2n-1,深度≤ n-1,形态不唯一。哈夫曼树的定义是:带权路径长度...

    数据结构---哈夫曼树

    学习数据结构中的哈夫曼树,需要编写头文件。我们

    漫话数据结构-哈夫曼树和哈夫曼编码.pptx

    哈夫曼树,又称最优二叉树或最小带权路径长度树,是一种特殊的二叉树,主要用于数据压缩和编码...理解哈夫曼树和哈夫曼编码的原理和构造过程,对于学习数据结构和算法,以及深入理解计算机科学中的编码技术至关重要。

    数据结构实验-哈夫曼树与哈夫曼编码

    一、问题描述 运用哈夫曼算法构造哈夫曼树,并得到哈夫曼编码。 输入格式:10,5,21,18,8,13 ...1、构造哈夫曼树和哈夫曼编码的存储结构。 2、实现哈夫曼算法,实现哈夫曼树的存储并求出哈夫曼编码。

    数据结构课程设计----哈夫曼树(c语言)

    它利用哈夫曼树对数据进行编码,形成前缀编码,实现数据的有效压缩存放。然后又通过某种遍历实现译码,从而达到快速远距离通信的目的。 关键词: 哈夫曼树;前缀编码;译码 前 言 利用哈夫曼编码进行通信可以大大...

    数据结构-哈夫曼树实验报告(包含文件压缩).pdf

    【哈夫曼树】是一种特殊的二叉树,用于在数据编码和压缩中创建最优化的编码方案。在哈夫曼树中,频率较低的字符会被赋予较短的编码,而频率较高的字符则会有较长的编码,以此达到高效压缩数据的目的。在给定的文件中...

    数据结构-哈夫曼树实验报告(包含文件压缩).docx

    数据结构中的哈夫曼树(Huffman Tree)是一种特殊的二叉树,用于数据编码和压缩。在本实验中,学生需要实现哈夫曼编码器,包括初始化、建立编码表、编码、译码以及打印哈夫曼树的功能。实验旨在通过实际操作理解...

    C语言数据结构--哈夫曼编/译码器

    - **数据结构**:通常使用`struct`定义哈夫曼树节点,包括字符、频率、左右子节点等字段。 - **动态构建**:可以使用队列(如链表实现)辅助构建哈夫曼树,每次弹出频率最小的两个节点进行合并,新节点入队。 - *...

    数据结构-哈夫曼编码器

    在IT行业中,理解并掌握哈夫曼编码是数据结构与算法学习的重要部分,对于提升程序效率和优化存储空间具有重要意义。 哈夫曼编码的基本原理是基于字符出现频率进行编码。它通过构建一种特殊的二叉树——哈夫曼树(也...

    数据结构-哈夫曼编码实验报告.doc

    《数据结构-哈夫曼编码实验报告》 在信息技术领域,数据压缩是至关重要的,而哈夫曼编码作为一种高效的数据压缩技术,被广泛应用。本实验报告主要关注如何利用哈夫曼编码对文本文件进行压缩与解压缩,以提高信道...

    数据结构-哈夫曼编码译码系统

    哈夫曼编码是一种高效的数据压缩方法,广泛应用于数据结构和计算机科学领域。在这个“数据结构-哈夫曼编码译码系统”中,我们主要探讨如何实现哈夫曼编码的生成和解码,以及如何对文件进行操作。 哈夫曼编码的基本...

Global site tag (gtag.js) - Google Analytics