`
大_圣
  • 浏览: 17649 次
  • 性别: Icon_minigender_1
  • 来自: 湖南
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

哈夫曼树(最优二叉树)

 
阅读更多

....差点忘记写博客了...

 

 

哈夫曼树 .. 其实就是只利用叶子结点来存储要用信息的树,只不过它在构造的时候就拥有了一个迷人的特性... 就是WPL(带权路径长度)是最小的.. 而且还能用这个树的来为叶子结点中的信息进行编码, 得出来的各个编码一定不会相同,并且不会产生混淆的情况..

 

通过哈夫曼树的特点.实现了根据一个队列来创建一棵哈夫曼树的方法.

/**
	 * 得到随机产生的队列
	 */
	public void setQueue() {
		Random rd = new Random();
		System.out.println("随机产生的队列为:");
		for (int i = 0; i < 10; i++) {
			int k = rd.nextInt(20);
			TreeNode tn = new TreeNode(k);
			queue.add(tn);
			System.out.print(k + " ");
		}
		System.out.println();
	}

	// 得到队列
	public PriorityQueue<TreeNode> getQueue() {
		return queue;
	}

	// 建树,while (queue.size()>=2)
	public TreeNode CreatTree(PriorityQueue<TreeNode> queue) {
		TreeNode lc = queue.poll();
		TreeNode rc = queue.poll();
		// 两个最小的结点通过这个结点连接起来
		TreeNode tr = new TreeNode((Integer) lc.getData()
				+ (Integer) rc.getData());
		tr.setLchild(lc);
		tr.setRchild(rc);
		lc.setParent(tr);
		rc.setParent(tr);
		// 将其父结点放入队列.
		queue.add(tr);
		return tr;// 将根结点返回.当返回到最后一个根结点时就构成了一棵树
	}

 到此.. 哈夫曼树就建成了. 接下来就是哈夫曼编码了.这个的实现我用到了递归,并且是每个叶结点往回找

 

/**
	 * 为每个叶结点编码,返回字符串
	 * 
	 * @param leaf每次传入一个叶结点
	 * @return以字符串形式返回每个叶结点的哈夫曼编码
	 */
	public String ToCode(TreeNode leaf) {
		String s = "";
		// 叶结点存在双亲结点.
		if (leaf.getParent() != null) {
			if (leaf.getParent().getLchild() == leaf) {
				// 向父结点递归
				s = ToCode(leaf.getParent()) + 0;
				return s;// 叶结点为左孩子时,在递归得到的编码后面加个0;
			} else if (leaf.getParent().getRchild() == leaf) {
				// 向父结点递归
				s = ToCode(leaf.getParent()) + 1;
				return s;// 叶结点为右孩子时,在递归得到的编码后面加个1;
			}
		}
		return s;
	}

 

 通过这个方法.. 实现对哈夫曼树中叶子结点进行哈夫曼编码的

 

 

 

补充个.. 今天读取文件中的字节时..发现0出现的次数是最多的 ... 读了个162M的文件.. 0的个数比其他的数出现的次数多了10万次 ....
 

  • 大小: 12.2 KB
分享到:
评论

相关推荐

    哈夫曼(最优二叉树)C语言版

    哈夫曼编码是一种数据压缩方法,它利用了字符出现频率的不同来构建一棵特殊的二叉树——哈夫曼树。在哈夫曼树中,频率较高的字符对应的路径较短,而频率较低的字符路径较长,这样可以使得频繁出现的字符在编码时使用...

    最优二叉树的哈夫曼算法(成功).rar

    哈夫曼编码的基本思想是通过构建一棵特殊的二叉树——哈夫曼树(也称为最优二叉树),对具有不同频率的字符进行编码。这种编码方式使得最频繁出现的字符拥有最短的编码,从而达到数据压缩的目的。在哈夫曼树中,叶子...

    最优二叉树 c++ 数据结构

    最优二叉树,又称为哈夫曼树或最小带权路径长度树,是一种特殊的二叉树,主要用于数据编码,特别是数据压缩。在最优二叉树中,每个叶子节点都代表一个待编码的字符,而其权重是该字符在数据源中的出现频率。非叶子...

    Huffman编码树最优二叉树

    它的核心思想是通过构建一种特殊的二叉树——最优二叉树(也称为最小带权路径长度树),来实现对数据的编码。这种树的特点是:频率高的字符对应的路径较短,而频率低的字符对应的路径较长,从而使得编码后的平均码长...

    最优二叉树应用-编码与译码

    最优二叉树,也称为哈夫曼树或最小带权路径长度树,是数据结构和算法领域中的一个重要概念。在信息编码中,特别是在数据压缩中,哈夫曼编码是一种非常有效的无损数据压缩方法。本课程设计作业主要探讨了如何构建和...

    哈夫曼算法最优二叉树.cpp

    定义:给定n个权值作为n个叶子结点,构造一棵二叉树,若树的带权路径长度达到最小,则这棵树被称为哈夫曼树。

    HuffmanTree(最优二叉树)

    《哈夫曼树(最优二叉树)详解》 在计算机科学中,哈夫曼树(Huffman Tree),又称最优二叉树,是一种特殊的二叉树结构,它在数据编码,特别是数据压缩领域中有着广泛的应用。哈夫曼树通过构建最小带权路径长度...

    构造二叉树 最优二叉树 树 输出二叉树到屏幕 C# .net

    2. **最优二叉树(哈夫曼树)** 最优二叉树,也称为哈夫曼树,是一种带权重的二叉树,用于数据编码以提高空间效率。它的构建目标是最小化所有路径的长度总和。哈夫曼树的构建通常采用贪心策略,通过合并权重最小的...

    Java 最优二叉树的哈夫曼算法的简单实现

    Java 最优二叉树的哈夫曼算法的简单实现 ...Java 最优二叉树的哈夫曼算法的简单实现演示了哈夫曼树的构建和实现过程,展示了哈夫曼树的基本结构和算法思想,对于学习哈夫曼树和Java编程都具有很高的参考价值。

    图形化生成树(二叉树 哈夫曼树 和 最小树)

    本主题将探讨三种特定类型的树:二叉树、哈夫曼树(又称最优二叉树)以及最小生成树。这三种树都有各自的特性和用途,让我们逐一深入了解一下。 首先,我们来看二叉树。二叉树是最简单的树结构之一,每个节点最多有...

    哈夫曼树压缩算法实现

    哈夫曼树(Huffman Tree),也称为最优二叉树,是数据压缩领域中的一个重要概念。它是基于贪心策略的一种数据结构,用于构建一种特殊的二叉树,使得带权路径长度最短,从而达到编码效率最高。哈夫曼树的核心思想是...

    哈夫曼树二叉树带权值计算C代码

    哈夫曼树,又称最优二叉树或最小带权路径长度树,是一种特殊的二叉树结构,主要用于数据编码,特别是数据压缩。它通过构建一种树形结构,使得树中所有叶子节点到根节点的路径上权值之和(即路径长度)达到最小,从而...

    根据给定的n个权值构造哈夫曼树。通过遍历此二叉树完成哈夫曼编码。

    **哈夫曼树(Huffman Tree)**是一种带权路径长度最短的二叉树,也称为最优二叉树。在数据压缩、编码等领域有广泛的应用。构建哈夫曼树的基本思想是利用给定的权值集合构造一棵二叉树,使得树中叶子节点的权值代表...

    哈夫曼树 课程设计 实验报告

    哈夫曼树,也称为最优二叉树,是一种特殊的二叉树,它的特点是所有叶子节点到根节点的路径上,权值之和(路径长度)最小。这里的权值通常代表字符出现的频率或概率。在数据压缩中,哈夫曼编码是基于哈夫曼树的一种...

    数据结构哈夫曼树教程

    数据结构中的哈夫曼树,又称为最优二叉树,是一种特殊的二叉树,它的设计目标是为了达到最小的带权路径长度。哈夫曼树在数据压缩、编码等领域有着广泛的应用,因为它能有效地减少数据传输或存储时的位数。 1. 树的...

    最优二叉树——哈夫曼树.doc

    树结构的特点是:它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前趋。

    数据结构 哈夫曼树

    数据结构中的哈夫曼树(Huffman Tree),也称为最优二叉树,是一种特殊的二叉树,主要用于数据的编码压缩。哈夫曼树是通过哈夫曼编码(Huffman Coding)来实现的,这是一种用于无损数据压缩的算法。在这个算法中,...

    哈夫曼树与哈夫曼编码

    哈夫曼树,又称为最优二叉树,是一种带权路径长度最短的二叉树。它的构建过程基于贪心策略,通过不断地合并权重最小的两个节点来构造树形结构。具体步骤如下: 1. **创建初始节点**:将每个字符视为一个节点,赋予...

    c语言 哈夫曼树

    哈夫曼树,又称最优二叉树或最小带权路径长度树,是数据结构领域中一种特殊的二叉树。在C语言中实现哈夫曼树主要用于数据的编码和解码,特别是压缩数据时,能够有效地提高编码效率。下面将详细介绍哈夫曼树的概念、...

Global site tag (gtag.js) - Google Analytics