您的位置: 首页  >  文章  >  数据结构树之霍夫曼树

数据结构树之霍夫曼树

分类: 文章 • 2024-01-06 14:55:22

霍夫曼树
1、为什么需要霍夫曼树
打个比喻，一篇文章里面每个字母出现的次数不同，有点差距很大。如果在编码的时候把每个字母的编码长度都设为一样，这样当然可行，但是会浪费存储空间。如果存在这样的一种编码，出现次数多的字母编码较少，这样就可以一定长度的节省内存空间。对于这样的编码，我们可以用霍夫曼树来实现
数据结构树之霍夫曼树
A—>00
B—>100
C—>101
D—>01
E—>11
这样就会发现这样的编码没有公共的前缀（如果存在公共前缀，那么这个编码是不正确的，以为这样在解码的时候会出现无法判断的情况）

2、霍夫曼树构建过程
（1）从序列里取出两个权值最小的节点
（2）创建一个新的节点，这个新的节点的权值是这两个节点的和
（3）把这个新的节点加入序列
（4）判断这个序列的长度是否大于1，如果是，则回到（1），否则结束构建过程

为了每一次都取出最小，插入的时候都是根据从小到大插入正确的位置，我们创建一个新链表，这个链表是单向的，保存了链表头和元素个数。
（1）插入：判断插入的节点中数据项的大小，然后插入正确位置（这样形成的序列是有序的）
（2）删除：删除表头（表头是最小的元素）

数的节点：

class HuffmanNode<T>
{
	//保存的数据
	T data;
	//数据对应的权值
	int weight;
	//左子树
	HuffmanNode<T> left;
	//右子树
	HuffmanNode<T> right;
	//链表中指向的下个节点
	HuffmanNode<T> next;
	
	
	//构造函数
	public HuffmanNode(T data,int weight)
	{
		this.data=data;
		this.weight=weight;
	}
	
	//
	public HuffmanNode(int weight)
	{
		this.weight=weight;
	}
}

链表：

/**
 * 在插入的时候判断节点的数据大小，然后插入特定的位置，所以这个链表是已经排好序的(ASC)
 * @author faceless
 *
 */
class Link<T extends Comparable<T>>
{
	//链表头
	HuffmanNode<T> frist;
	//节点数
	int length;
	
	/**
	 * 插入新节点
	 * @param node
	 */
	public void insert(HuffmanNode<T> node)
	{
		//如果头节点为空，那么先插入头结点
		if(this.frist==null)
		{
			frist=node;
			length++;
		}
		else//头结点不为空，则根据大小插入
		{
			HuffmanNode<T> current=frist;
			//current节点之前的节点
			HuffmanNode<T> preCurrent=null;
			while(current!=null)
			{
				if(node.weight>=current.weight)
				{
					preCurrent=current;
					current=current.next;
				}
				else
				{
					//插入头结点之前
					if(preCurrent==null)
					{
						node.next=current;
						frist=node;
					}
					else {
						node.next=current;
						preCurrent.next=node;
					}
					//插入结束
					break;
				}	

			}
			//插入到最后
			if(current==null)
				preCurrent.next=node;
			length++;
		}
	}
	
	/**
	 * 删除头结点
	 * @return
	 */
	public HuffmanNode<T> delete()
	{
		HuffmanNode<T> frist=this.frist;
		this.frist=this.frist.next;
		length--;
		return frist;
	}
	
	
	
	/**
	 * 以这个链表构建霍夫曼树，实际上就是把队列转换为数，最后队列只有一个元素，也就是根
	 */
	public HuffmanTree<T> createHuffmanTree()
	{
		while(this.length>1)
		{
			HuffmanNode<T> nowLeft=this.delete();
			HuffmanNode<T> nowRight=this.delete();
			HuffmanNode<T> nowRoot=new HuffmanNode<T>(nowLeft.weight+nowRight.weight);
			nowRoot.left=nowLeft;
			nowRoot.right=nowRight;
			//插入新的节点
			this.insert(nowRoot);
		}
		return new HuffmanTree<T>(this.frist);
	}
	
}

createHuffmanTree()方法的目的是把这个链表构成一棵霍夫曼树

3、构建霍夫曼树表示的序列，使用递归来实现

	private void createHuffmanCode()
	{
		this.stringCode(this.root,"");
	}
	
	private void stringCode(HuffmanNode<T> node,String string)
	{	
		if(node.data!=null)
		{
			map.put(node.data, string);
		}
		else
		{
			stringCode(node.left,string+"0");
			stringCode(node.right,string+"1");
		}
			
	}

4、编码和解码：这个就是霍夫曼树的应用，这里就不做介绍

相关推荐