二叉树（五）——哈夫曼树

我会带着你远行 2022-05-25 09:52 136阅读 0赞

今天我来说一说霍夫曼树的构造。什么是霍夫曼树，之前我们发现，二叉树的每个结点的重要程度（以下称为权值）都是相同的。但是如果每个结点的重要程度不相同，即他们的权值不同。我们就需要构造一个新的二叉树，按照权值不同，权值高的放在二叉树的顶端，权值低的放在二叉树的底端。从二叉树的构造原理来看，这样做可以有效地减少一组数据索引时间。

首先我来说一下我的哈夫曼树的结点的数据结构

class TreeNode{
    		private TreeNode leftchild;//左孩子
    		private TreeNode rightchild;//右孩子
    		private String content;//节点对应的内容
    		private int data;//权值
    		private int status;//判断是我们原本数组中的数据还是后来添加的根节点
    		
    		private int level = 0;//根节点的层次
    }

在展示我的代码之前，我想先用一幅图来解释一下霍夫曼树的形成。首先我来说一下霍夫曼树的组成原则，在一组从小到大排列的数组中查找最小的两个数，将其作为左子树和右子树，生成一个父节点，父节点的权值是这两个子节点的权值之和.然后将这个父节点按照权值的大小在原来的数组中进行重新排序。以此类推，直到整个数组为空。

下面来看一下这幅图

接下来我将用java代码实现这个霍夫曼树

首先我想从构造方法讲起。

public TreeNode(String content,int data){
    			this.content =content;
    			this.data =data;
    			this.status = 1;
    		}
    		/**
    		 * 构造的是原本的数组中应该存在的权值结点
    		 * @param data
    		 */
    		public TreeNode(TreeNode node){
    			this.content = node.content;
    			this.leftchild = node.leftchild;
    			this.rightchild = node.rightchild;
    			this.data = node.data;
    			this.status = node.status;//表示这是原本的数组存在的值，其权值是有意义的
    		}
    		/**
    		 * 为了实现将权值低的值放在底端而设置的根节点
    		 * @param leftchild
    		 * @param rightchild
    		 */
    		public TreeNode(TreeNode leftchild,TreeNode rightchild){
    			this.leftchild = leftchild;
    			this.rightchild = rightchild;
    			this.data= leftchild.data+rightchild.data;
    			this.status = 0;
    		}

首先我来讲述一下status这个属性的意义。我们知道霍夫曼树里面有的结点的content是实际存在的，而有些则是null。原因就是这个节点是为了二叉树形成而生成的辅助结点（在遍历的时候并不会被输出），那么我们就讲这些辅助结点的status的值设置为0，而将原本存在的结点的status的值设置为1。

接下来就是我的具体的霍夫曼树的生成代码

/**
    	 * 霍夫曼排序
    	 * @param list
    	 */
    	public void huffOrder(List<TreeNode> list){
    		while(list.size()>1){
    			TreeNode min = list.remove(0);
    			TreeNode max =list.remove(0);
    			TreeNode leftchild = new TreeNode(min);
    			TreeNode rightchild = new TreeNode(max);
    			TreeNode parent = new TreeNode(leftchild,rightchild);
    			//System.out.println(parent);
    			root = parent;
    			if(list.size()>0){
    				List<TreeNode> temp =list;
    				if(parent.data>=(list.get(list.size()-1)).data){
    					temp.add(list.size(),parent);
    					list = temp;
    				}else{
    					for(int i =0;i<list.size()-1;i++){
    						if(parent.data>=list.get(i).data&&parent.data<=list.get(i+1).data){
    							temp.add(i+1, parent);
    							list=temp;
    							break;
    						}
    					}
    				}
    				
    			}
    			huffOrder(list);
    		}
    		return;
    	}

形参是一个结点链表，这个链表的生成方法如下

public List<TreeNode> getList(String[] strs,int[] weights){
    		List<TreeNode> list = new LinkedList<TreeNode>();
    		for(int i=0;i<weights.length;i++){
    			list.add(new TreeNode(strs[i],weights[i]));
    		}
    		return  list;
    	}

将对应结点的内容和其权值生成一个新的TreeNode对象。

下面我来简述一下代码的实现原理。

首先，将list的前两个元素取出，一个作为左子树，一个作为右子树。同时生成他们的根节点。

然后将这个根节点按照其权值大小顺序插入到原链表中的位置。递归遍历新的链表，直到链表的长度为0。

思路并不复杂，但是需要根据代码一行一行地对应起来。

接下来就是求这个霍夫曼树的总权值了。代码如下

/**
    	 * 获取一个霍夫曼树的最小权值
    	 * @param node
    	 * @return
    	 */
    	public int getMinWeight(TreeNode node){
    		int weight = 0;
    		if(node==null){
    			return 0;
    		}
    		Queue<TreeNode> queue = new LinkedList<TreeNode>();
    		if(node.leftchild!=null){
    			queue.add(node.leftchild);
    			node.leftchild.level = node.level+1;
    			if(node.leftchild.status!=0){
    				weight+=node.leftchild.data*node.leftchild.level;
    			}
    		}
    		if(node.rightchild!=null){
    			queue.add(node.rightchild);
    			node.rightchild.level = node.level+1;
    			if(node.rightchild.status!=0){
    				weight+=node.rightchild.data*node.rightchild.level;
    			}
    		}
    		while(!queue.isEmpty()){
    			TreeNode n = queue.remove();
    			
    			if(n.leftchild!=null){
    				queue.add(n.leftchild);
    				n.leftchild.level = n.level+1;
    				if(n.leftchild.status!=0){
    					weight+=n.leftchild.data*n.leftchild.level;
    				}
    			}
    			
    			if(n.rightchild!=null){
    				queue.add(n.rightchild);
    				n.rightchild.level = n.level+1;
    				if(n.rightchild.status!=0){
    					weight+=n.rightchild.data*n.rightchild.level;
    				}
    			}
    			
    		}
    		return weight;
    	}

我们可以看到，这个求权值的算法和我之前所说的层次遍历法是很相近的。原因很简单，这和霍夫曼树的组成有关系。这个时候就用到我们的level了。根据层次遍历法的原理，每次入栈的结点都是出栈结点的左孩子或者右孩子。那么其所在层次必定是其根节点层次加一。所以每次添加时都需要对新添加结点的level重新赋值。计算的时候则是 权值\*层次数 然后叠加。

最后一点我来说说怎样遍历霍夫曼树，前面我已经说了，遍历使用的是层次遍历法。只不过只输出status为1的结点的content。代码如下

public void levelOrder(TreeNode node) {
    		if(node==null){
    			try {
    				throw new Exception("该树为空");
    			} catch (Exception e) {
    				e.printStackTrace();
    			}
    		}
    		Queue<TreeNode> queue = new LinkedList<TreeNode>();
    			if(node.leftchild!=null){
    				queue.add(node.leftchild);
    				if(node.leftchild.status!=0){
    					System.out.println(node.leftchild.content+" ");
    				}
    			}
    			if(node.rightchild!=null){
    				queue.add(node.rightchild);
    				if(node.leftchild.status!=0){
    					System.out.println(node.rightchild.content+" ");
    				}
    			}
    		while(!queue.isEmpty()){
    			TreeNode n = queue.remove();
    			if(n.leftchild!=null){
    				queue.add(n.leftchild);
    				if(n.leftchild.status!=0){
    					System.out.println(n.leftchild.content+" ");
    				}
    			}
    			if(n.rightchild!=null){
    				queue.add(n.rightchild);
    				if(n.rightchild.status!=0){
    					System.out.println(n.rightchild.content+" ");
    				}
    			}
    		}
    	}

这个就是霍夫曼树比较完整的代码了。这个代码是我根据霍夫曼树的定义去写出来的。霍夫曼树的应用比较广泛的就是霍夫曼编码，根据一个字母在一个数据域的频率的大小为其分配不同的码值实现内存的最大利用。所以霍夫曼树也叫最优二叉树。