如何构造哈夫曼树

 

树：

1.概念

   树其实只是含有多个指针域的链表，一个结点可以指向多个子结点，其形状如树一样开支散叶，所以称之为树。其结构与链表基本一样，操作也相似。

 

2.哈夫曼树：

  哈夫曼树是一种带全路径最短的树，因此在信息检索中很有用。

  1.建造哈夫曼树；

哈夫曼树是带权值组成结点组成的，所以结点属性应当有属性

public class Node {

		//要存储的数据
		private String data;
		//在文件中出现的次数
		private int count =0;
		//用来做生在父类的左子树，或者右子树的标识，如果是做左子树为0；右子树为1。
		private String symbol ="" ;
		//节点的父节点
		private Node leftchild;
		//节点的孩子节点
		private Node rightchild;
	}

 

哈夫曼树是由一个结点数据出现次数来建造树的，所以所有的结点应当事先准备好，储存于队列之中，排好序。这个可以用优先队列来实现功能，也可以自己写一个自定义队列来实现。

public void creatTree(Queue q){

		//当队列的的长度大于一时，始终前两个结点相连起来，构建树
		while(q.size()>1){
			Node node1 = q.getNode();//取出第一个结点
			Node node2 = q.getNode();//取出第二个结点
			//构建父节点
			Node node = new Node(" ",node1.getCount()+node2.getCount());
			//建立结点树
			node.setLeftchild(node1);
			node1.setSymbol("0");
			node.setRightchild(node2);
			node2.setSymbol("1");
			//将新生成的父结点加入队列中
			q.add(node);
		}
		this.root = q.getNode();
	}

 

这个队列是我自己写的一个队列，当你取出这个元素时，元素就被移除，添加元素时，自动根据count大小，找到位置排列。

  这样一颗哈夫曼树就被建造起来，再遍历获得哈夫曼编码，就ok了，

public Queue ergodic(Node node,String str) {
		
		// 设计指针 并指向头结点
		Node temp = new Node("指针",0);
		temp = node;
		// 设置出口
		if (null==temp.getLeftchild() && null==temp.getRightchild() ) {
			temp.setSymbol(str);
			q.add(temp);
		}
		else{
			ergodic(node.getLeftchild(),str+"0");
			ergodic(node.getRightchild(), str+"1");
		}
		return q;
	}

 

这样就获取了，就给每一个结点设置了哈夫曼编码，并已将所有有用的结点储存到了队列中。这其实就实现了将文件头压缩时文件编码

的信息存入了队列。哈夫曼就算完成了。