二叉树及哈夫曼编码树总结

                                                java中的二叉树及哈夫曼编码树

        现在我们正在学的一门课数据结构中，也有关二叉树和哈夫曼编码树的学习。虽然不完全一样，但是同样作为编程语言，它们的相同点也挺多的，实现原理和大概实现思想也基本相同。

       树是一种重要的非线性数据结构，直观地看，它是结点按分支关系组织起来的结构，很象自然界中的树那样。

 既然叫做二叉树，自然就会有两个分叉，在根结点的左边的树称为左子树，在右边的则称为右子树。

 遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。

 树的遍历有三种方法：先序遍历、中序遍历、后序遍历。

 先序遍历：访问顺序为根结点、左子树、右子树。

 中序遍历：访问顺序为左子树、根结点、右子树。

 后序遍历：访问顺序为左子树、右子树、根结点。

 哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有叶结点的权值乘上其到根结点的路径长度。它的优势在数据重复度越高的时候越能体现出来。对数据压缩很有效果。

 

 哈夫曼树构建方法：每次取最小的两个权值作为左右结点，再将它们的和与除了这两个权值之外的其他权值进行比较。再次重复该步骤，直到剩余一个权值作为结点时才结束。

 作为二叉树的一种，遍历方法自然也与前面提到的三种方法一样，可以进行先序遍历、中序遍历、后序遍历。

 

二叉树代码：

package 二叉树;

/*
 * 定义Node类
 */
public class Node {
	//定义相关属性
	Node left;
	Node right;
	Node parent;
	int data;
	String str;
}

 

package 二叉树;

public class Tree {
	private Node root;//定义根节点

	//添加str-表达式，data-数据，到树的节点上
	public void add(String str, int data){
		if(root == null){
			//第一个添加的节点为根
			Node node = new Node();
			node.data=data;
			node.str = str;			
			root = node;
		} else {
			if(root.parent == null){
				//如果当前根节点的父节点是空，则把新节点作为root的父节点
				Node node = new Node();
				node.data = data;
				node.str = str;			
				//root的父节点指向新节点
				root.parent = node;
				//新节点的左节点指向root
				node.left = root;
			} else {
				Node node = new Node();
				node.data = data;
				node.str = str;
				//把新节点添加到最上层节点的右节点
				root.parent.right = node;
				//root节点向上移动一层
				root = root.parent;
			}
		}
	}
	
	//计算树的和值
	public int calc(Node node){
		if(node != null && node.right != null){
			//递归左节点的结果加上右节点的值
			if(node.str.equals("-")){
				return calc(node.left) - node.right.data;
			}
			if(node.str.equals("+")){
				return calc(node.left) + node.right.data;
			}
		} else {
			//如果是最底层节点，则返回节点上的值
			if(node.left == null)
				return node.data;
		}
		return 0;
	}
	//打印树结构
	public void printTree(){
		Node temp = root;
		while(temp != null){
			//打印当前节点和父节点的右节点
			System.out.print("str="+temp.str+",data="+temp.data);
			if(temp.parent != null){
				if(temp.parent.right != null){
					System.out.println(" right:str="+temp.parent.right.str+",data="+temp.parent.right.data);
				}
			}
			temp = temp.left;
		}
	}
	
	/*
	 * 程序主函数
	 */
	public static void main(String[] args) {
		String str = "1+2+3-4+5+6";
		//实例化一个Tree类对象
		Tree tree = new Tree();
		for(int i=0;i<str.length(); i++){
			char c = str.charAt(i);
			if(c == '+' || c=='-'){
				tree.add(""+c, 0);
			} else {
				tree.add("", Integer.parseInt(""+c));
			}
		}
		//调用打印节点方法
		tree.printTree();
		
		System.out.println(tree.calc(tree.root));
	}


}

 

 

 

哈夫曼手动建树代码：

package 哈佛曼;

public class HFM {
    class Node{
		Node left;//定义左节点属性
		Node right;//定义右节点属性
		String code;//定义编码属性
		int data;//定义数据属性
	}

   	/*
   	 * 手动建树方法
   	 */
	public Node creatTree(){
		Node n1 = new Node();
		n1.data=1;
		
		Node n2 = new Node();
		n2.data=2;
		
		Node n3 = new Node();
		n3.data=3;
		
		Node n4 = new Node();
		n4.data=4;
		
		Node n5 = new Node();
		n5.data=5;	
	        
		Node nn1 = new Node();
		nn1.data = n1.data+n2.data;
	    nn1.left=n1;
	    nn1.right=n2;
	    
	    Node nn2 = new Node();
		nn2.data = nn1.data+n3.data;
	    nn2.left=nn1;
	    nn2.right=n3;
	    
	    Node nn3 = new Node();
		nn3.data = n4.data+n5.data;
	    nn3.left=n4;
	    nn3.right=n5;
	    
	    Node nn4 = new Node();
		nn4.data = nn2.data+nn3.data;
	    nn4.left=nn2;
	    nn4.right=nn3;
	   
	    Node root = null;
	    root=nn4;
	    return root;
		//return root;
	}
	
	//打印哈夫曼编码
	public void printCode(){
		Node root = creatTree();
		printCode(root,"");
	}
	
	//定义一个打印当前节点的方法
	public void printCode(Node node,String code){
		if(node!=null){
			//先序遍历
			if(node.left==null)//有了条件只打印叶结点
			System.out.println(node.data+"的编码是："+code);
			printCode(node.left,code+"0");
			printCode(node.right,code+"1");
		}
	}
	
	/*
	 * 程序主函数
	 */
	public static void main(String[] args){
		//实例化一个HFM对象
		HFM hfm = new HFM();
		//用该对象调用相应方法
		hfm.creatTree();
		hfm.printCode();	
	}
}

 

哈夫曼自动建树代码：

/*
 * 定义一个哈夫曼类
 */
public class HFM {
	/*
	 * 定义一个Node类
	 */
	class Node{
		Node left;//定义左节点属性
		Node right;//定义右节点属性
		String code;//定义编码属性
		int data;//定义数据属性
	} 
	/*
	 * 打印编码方法
	 */
	public void printCode (int [] datas){
		//转化成Node数组
		Node [] nodes = new Node[datas.length];
		for(int i = 0;i<nodes.length;i++){
			nodes[i]=new Node();
			nodes[i].data = datas[i];
		}
		/*
		 * 自动建树
		 */
		while(nodes.length>1){
			sort(nodes);
		
			Node n1 = nodes[0];
			Node n2 = nodes[1];
		
			Node node = new Node();
			node.left = n1;
			node.right = n2;
			node.data = n1.data +n2.data;
		
			//把n1和n2删除，把node加进去
			Node[] nodes2 = new Node[nodes.length-1];
			for(int i = 2; i<nodes.length;i++){
				nodes2[i-2]=nodes[i];
			}
			nodes2[nodes2.length-1]=node;		
			nodes = nodes2;		
			}
		
		Node root = nodes[0];
		printCode(root,"");
	}
	
	//冒泡排序法对Node[]数组进行排序
	public void sort(Node[] nodes){
		for(int i = 0;i<nodes.length;i++){
			for(int j = i+1;j<nodes.length;j++){
				if(nodes[i].data>nodes[j].data){
					//如果nodes[i].data>nodes[j].data则交换两个节点位置
					Node temp = new Node();
					temp=nodes[i];
					nodes[i]=nodes[j];
					nodes[j]=temp;
				}				
			}
		}
	}
	
	//定义一个打印当前节点的方法
	public void printCode(Node node,String code){
		if(node!=null){
			//先序遍历
			if(node.left==null&&node.right==null)//有了条件只打印叶结点
			System.out.println(node.data+"的编码是："+code);
			//打印左节点编码
			printCode(node.left,code+"0");
			//打印右节点编码
			printCode(node.right,code+"1");
		}
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		HFM hfm = new HFM();
		
		int[] datas = {1,2,3,4,5};
		
		hfm.printCode(datas);
	}

}