Java数据结构与算法——树篇

冷不防 2023-10-04 07:18 10阅读 0赞

> Java数据结构与算法: [https://blog.csdn.net/weixin\_46822367/article/details/115478461?spm=1001.2014.3001.5502][https_blog.csdn.net_weixin_46822367_article_details_115478461_spm_1001.2014.3001.5502].  
> 
> 
> #### 目录 ####
> 
>  *   *   *  1、二叉树
>          *  2、顺序存储二叉树
>          *  3、线索化二叉树
>          *  4、堆排序
>          *  5、赫夫曼树
>          *  6、赫夫曼编码（数据压缩、数据解压）

#### 1、二叉树 ####

package com.lyp.tree;
    
    public class BinaryTreeDemo {
        
    
    	public static void main(String[] args) {
        
    		//先创建一个二叉树
    		BinaryTree binaryTree = new BinaryTree();
    		//创建需要的节点
    		HeroNode root = new HeroNode(1,"宋江");
    		HeroNode node2 = new HeroNode(2,"吴用");
    		HeroNode node3 = new HeroNode(3,"卢俊义");
    		HeroNode node4 = new HeroNode(4,"林冲");
    		HeroNode node5 = new HeroNode(5,"关胜");
    		
    		//手动创建二叉树
    		root.setLeft(node2);
    		root.setRight(node3);
    		node3.setLeft(node5);
    		node3.setRight(node4);
    		binaryTree.setRoot(root);
    		
    		//System.out.println("前序遍历");//1,2,3,5,4
    		//binaryTree.preOrder();
    		
    		//System.out.println("中序遍历");//2,1,5,3,4
    		//binaryTree.infixOrder();
    		
    		//System.out.println("后序遍历");//2,5,4,3,1
    		//binaryTree.postOrder();
    		
    		/*
    		//前序遍历查找
    		//前序遍历的次数：4
    		System.out.println("前序遍历方式~~~");
    		HeroNode resNode = binaryTree.preOrderSearch(5);
    		if(resNode != null) {
    			System.out.printf("找到了，信息为 no=%d name=%s",resNode.getNo(),resNode.getName());
    		} else {
    			System.out.printf("没有找打 no = %d 的英雄",5);
    		}*/
    		
    		/*
    		//中序遍历查找
    		//中序遍历的次数：3
    		System.out.println("中序遍历方式~~~");
    		HeroNode resNode = binaryTree.infixOrderSearch(5);
    		if(resNode != null) {
    			System.out.printf("找到了，信息为 no=%d name=%s",resNode.getNo(),resNode.getName());
    		} else {
    			System.out.printf("没有找打 no = %d 的英雄",5);
    		}*/
    		
    		//后序遍历查找
    		//后序遍历的次数：2
    		System.out.println("后序遍历方式~~~");
    		HeroNode resNode = binaryTree.postOrderSearch(5);
    		if(resNode != null) {
        
    			System.out.printf("找到了，信息为 no=%d name=%s",resNode.getNo(),resNode.getName());
    		} else {
        
    			System.out.printf("没有找打 no = %d 的英雄",5);
    		}
    		
    		
    		
    		
    		
    		
    		
    		
    		
    		
    		
    		
    		//System.out.println("删除前，前序遍历");
    		//binaryTree.preOrder();//1,2,3,5,4
    		
    		//binaryTree.delNode(5);
    		//binaryTree.delNode(3);
    		
    		//System.out.println("删除后，前序遍历");
    		//binaryTree.preOrder();//1,2,3,4
    		
    		
    	}
    
    }
    
    class BinaryTree {
        
    	private HeroNode root;
    
    	public void setRoot(HeroNode root) {
        
    		this.root = root;
    	}
    
    	public void delNode(int no) {
        
    		if(this.root != null) {
        
    			if(this.root.no == no) {
        
    				root = null;
    			}
    			else {
        
    				this.root.delNode(no);
    			}
    		}else {
        
    			System.out.println("树为空，无法删除");
    		}
    	}
    	
    	public void preOrder() {
        
    		if(this.root != null) {
        
    			this.root.preOrder();
    		} else {
        
    			System.out.println("二叉树为空，无法遍历");
    		}
    	}
    	
    	public void infixOrder() {
        
    		if(this.root != null) {
        
    			this.root.infixOrder();
    		} else {
        
    			System.out.println("二叉树为空，无法遍历");
    		}
    	}
    	
    	public void postOrder() {
        
    		if(this.root != null) {
        
    			this.root.postOrder();
    		} else {
        
    			System.out.println("二叉树为空，无法遍历");
    		}
    	}
    	
    	public HeroNode preOrderSearch(int no) {
        
    		if(this.root != null) {
        
    			return this.root.preOrderSearch(no);
    		} else {
        
    			return null;
    		}
    	}
    	
    	public HeroNode infixOrderSearch(int no) {
        
    		if(this.root != null) {
        
    			return this.root.infixOrderSearch(no);
    		} else {
        
    			return null;
    		}
    	}
    	
    	public HeroNode postOrderSearch(int no) {
        
    		if(this.root != null) {
        
    			return this.root.postOrderSearch(no);
    		} else {
        
    			return null;
    		}
    	}
    }
    
    	
    
    //先创建HeroNode节点
     class HeroNode {
        
    	public int no;
    	public String name;
    	public HeroNode left;
    	public HeroNode right;
    	
    	public HeroNode(int no, String name) {
        
    		this.no = no;
    		this.name = name;
    	}
    
    	public int getNo() {
        
    		return no;
    	}
    
    	public void setNo(int no) {
        
    		this.no = no;
    	}
    
    	public String getName() {
        
    		return name;
    	}
    
    	public void setName(String name) {
        
    		this.name = name;
    	}
    
    	public HeroNode getLeft() {
        
    		return left;
    	}
    
    	public void setLeft(HeroNode left) {
        
    		this.left = left;
    	}
    
    	public HeroNode getRight() {
        
    		return right;
    	}
    
    	public void setRight(HeroNode right) {
        
    		this.right = right;
    	}
    
    	@Override
    	public String toString() {
        
    		return "HeroNode [no=" + no + ", name=" + name + "]";
    	}
    	
    	
    	//删除节点
    	public void delNode(int no) {
        
    		if(this.left != null && this.left.no == no) {
        
    			this.left = null;
    			return ;
    		}
    		if(this.right != null && this.right.no == no) {
        
    			this.right = null;
    			return;
    		}
    		if(this.left != null) {
        
    			this.left.delNode(no);
    		}
    		if(this.right != null) {
        
    			this.right.delNode(no);
    		}
    		
    	}
    	
    	//前序遍历
    	public void preOrder() 	{
        
    		System.out.println(this);
    		if(this.left != null) {
        
    			this.left.preOrder();	
    		}
    		if(this.right != null) {
        
    			this.right.preOrder();
    		}
    	}
    	//中序遍历
    	public void infixOrder() 	{
        
    		if(this.left != null) {
        
    			this.left.infixOrder();	
    		}
    		System.out.println(this);
    		if(this.right != null) {
        
    			this.right.infixOrder();
    		}
    	}
    	//后序遍历
    	public void postOrder() 	{
        
    		if(this.left != null) {
        
    			this.left.postOrder();	
    		}
    		if(this.right != null) {
        
    			this.right.postOrder();
    		}
    		System.out.println(this);
    	}
    	
    	//前序查找
    	public HeroNode preOrderSearch(int no) {
        
    		System.out.println("进入前序遍历查找");
    		if(this.no == no) {
        
    			return this;
    		}
    		HeroNode resNode = null;
    		if(this.left != null) {
        
    			resNode = this.left.preOrderSearch(no);
    		}
    		if(resNode != null) {
        
    			return resNode;
    		}
    		if(this.right != null) {
        
    			resNode = this.right.preOrderSearch(no);
    		}
    		return resNode;
    	}
    	
    	//中序查找
    	public HeroNode infixOrderSearch(int no) {
        
    		HeroNode resNode = null;
    		if(this.left != null) {
        
    			resNode = this.left.infixOrderSearch(no);
    		}
    		if(resNode != null) {
        
    			return resNode;
    		}
    		System.out.println("进入中序遍历查找");
    		if(this.no == no) {
        
    			return this;
    		}
    		if(this.right != null) {
        
    			resNode = this.right.infixOrderSearch(no);
    		}
    		return resNode;
    	}
    	
    	//后序查找
    	public HeroNode postOrderSearch(int no) {
        
    		HeroNode resNode = null;
    		//判断当前的左子节点是否为空，如果不为空，则递归后序查找
    		if(this.left != null) {
        
    			resNode = this.left.postOrderSearch(no);
    		}
    		if(resNode != null) {
        //说明左子树找到了
    			return resNode;
    		}
    		//如果左子树没有找到，则向右子树递归进行后序遍历查找
    		if(this.right != null) {
        
    			resNode = this.right.postOrderSearch(no);
    		}
    		if(resNode != null) {
        
    			return resNode;
    		}
    		System.out.println("进入后序遍历查找");
    		//如果左右子树都没有找到，就比较当前节点是不是
    		if(this.no == no) {
        
    			return this;
    		}
    		return resNode;
    	}
    }

#### 2、顺序存储二叉树 ####

package com.lyp.tree;
    
    public class ArrBinaryTreeDemo {
        
    
    	public static void main(String[] args) {
        
    		int[] arr = {
        1,2,3,4,5,6,7};
    		
    		ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
    		System.out.println("数组按二叉树前序遍历");
    		arrBinaryTree.preOrder();//1,2,4,5,3,6,7
    		
    		System.out.println("数组按二叉树中序遍历");
    		arrBinaryTree.infixOrder();//4,2,5,1,6,3,7
    		
    		System.out.println("数组按二叉树后序遍历");
    		arrBinaryTree.postOrder();//4,5,2,6,7,3,1
    	}
    
    }
    
    class ArrBinaryTree {
        
    	private int[] arr;//存储数据结点的数组
    
    	public ArrBinaryTree(int[] arr) {
        
    		this.arr = arr;
    	}
    	
    	//重载preOrder
    	public void preOrder() {
        
    		this.preOrder(0);
    	}
    	
    	//重载infixOrder
    	public void infixOrder() {
        
    		this.infixOrder(0);
    	}
    		
    	//重载postOrder
    	public void postOrder() {
        
    		this.postOrder(0);
    	}
    	
    	//编写一个方法，完成顺序存储的二叉树的前序遍历
    	/**
    	 * 
    	 * @param index 数组下标
    	 */
    	public void preOrder(int index) {
        
    		if(arr == null || arr.length == 0) {
        
    			System.out.println("当前数组为空，无法按照二叉树前序遍历");
    		}
    		//输出这个元素
    		System.out.println(arr[index]);
    		//向左递归
    		if((2 * index + 1) < arr.length) {
        
    			preOrder(2 * index + 1);
    		}
    		//向右递归
    		if((2 * index + 2) < arr.length) {
        
    			preOrder(2 * index + 2);
    		}
    		
    	}
    	
    	//中序遍历
    	public void infixOrder(int index) {
        
    		if(arr == null || arr.length == 0) {
        
    			System.out.println("当前数组为空，无法按照二叉树中序遍历");
    		}
    		if((2 * index + 1) < arr.length) {
        
    			infixOrder(2 * index + 1);
    		}
    		System.out.println(arr[index]);
    		if((2 * index + 2) < arr.length) {
        
    			infixOrder(2 * index + 2);
    		}
    	}
    	
    	//后序遍历
    		public void postOrder(int index) {
        
    			if(arr == null || arr.length == 0) {
        
    				System.out.println("当前数组为空，无法按照二叉树后序序遍历");
    			}
    			if((2 * index + 1) < arr.length) {
        
    				postOrder(2 * index + 1);
    			}
    			if((2 * index + 2) < arr.length) {
        
    				postOrder(2 * index + 2);
    			}
    			System.out.println(arr[index]);
    		}
    }

#### 3、线索化二叉树 ####

package com.lyp.tree.threadedbinarytree;
    
    
    
    public class threadedBinaryTreeDemo {
        
    
    	public static void main(String[] args) {
        
    
    		//测试一把中序线索二叉树的功能
    		HeroNode root = new HeroNode(1,"tom");
    		HeroNode node2 = new HeroNode(3,"jack");
    		HeroNode node3 = new HeroNode(6,"smith");
    		HeroNode node4 = new HeroNode(8,"mary");
    		HeroNode node5 = new HeroNode(10,"king");
    		HeroNode node6 = new HeroNode(14,"dim");
    		
    		//二叉树，手动创建
    		root.setLeft(node2);
    		root.setRight(node3);
    		node2.setLeft(node4);
    		node2.setRight(node5);
    		node3.setLeft(node6);
    		
    		
    		//测试中序线索化
    		ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
    		threadedBinaryTree.setRoot(root);
    		threadedBinaryTree.threadedNodes();
    		
    		
    		//测试以10号节点测试
    		HeroNode leftNode = node5.getLeft();
    		System.out.println("10号节点的前驱节点是 ="+ leftNode);//3
    		HeroNode rightNode = node5.getRight();
    		System.out.println("10号节点的后继节点是 ="+ rightNode);//1
    		
    		System.out.println("使用线索化的方式遍历  线索化二叉树");
    		threadedBinaryTree.threadedList();//8,3,10,1,14,6
    		
    	}
    
    }
    
    //实现了线索化功能的二叉树
    class ThreadedBinaryTree {
        
    	private HeroNode root;
    	
    	//为了实现线索化，需要创建要给指向节点的前驱节点的指针
    	//在递归进行线索化，pre 总是保留前一个节点
    	private HeroNode pre = null;
    
    	public void setRoot(HeroNode root) {
        
    		this.root = root;
    	}
    	
    	public void threadedNodes() {
        
    		this.threadedNodes(root);
    	}
    	
    	
    	//遍历线索化二叉树的方法
    	public void threadedList() {
        
    		//定义一个变量，存储当前遍历的节点，从root开始
    		HeroNode node = root;
    		while(node != null) {
        
    			//循环的找到leftType == 1的节点，第一个找到的就是8节点
    			//后面随着循环而遍历，因为当leftType==1时，说明节点是按照线索化
    			//处理后的有效节点
    			while(node.leftType == 0) {
        
    				node = node.getLeft();
    			}
    			//打印当前这个节点
    			System.out.println(node);
    			//如果当前节点的右指针指向的是后继节点，就一直输出
    			while(node.rightType == 1) {
        
    				//获取到当前节点的后继节点
    				node = node.getRight();
    				System.out.println(node);
    			}
    			//替换这个遍历的节点
    			node = node.getRight();
    		}
    	}
    	
    	
    	
    	//编写对二叉树的中序线索化方法
    	/**
    	 * 
    	 * @param node 就是当前需要线索化的节点
    	 */
    	public void threadedNodes(HeroNode node) {
        
    		//如果 node==null，不能线索化
    		if(node == null) {
        
    			return;
    		}
    		//(一)先线索化左子树
    		threadedNodes(node.getLeft());
    		//(二)线索化当前节点
    		
    		//处理当前节点的前驱节点 
    		//以8节点来理解
    		//8节点 的.left = null,8 节点的.leftType = 1
    		if(node.left == null) {
        
    			//让当前节点的左指针指向前驱节点
    			node.setLeft(pre);
    			//修改当前节点的左指针的类型，指向前驱节点
    			node.setLeftType(1);
    		}
    		
    		//处理后继节点
    		if(pre != null && pre.right == null) {
        
    			//让前驱节点的右指针指向当前节点
    			pre.setRight(node);
    			//修改前驱节点的右指针类型
    			pre.setRightType(1);
    		}
    		//！！！ 每处理一个节点后，让当前节点是下一个节点的前驱节点
    		pre = node;
    		
    		//(三)再线索化右子树
    		threadedNodes(node.getRight());
    		
    	}
    
    	public void delNode(int no) {
        
    		if(this.root != null) {
        
    			if(this.root.no == no) {
        
    				root = null;
    			}
    			else {
        
    				this.root.delNode(no);
    			}
    		}else {
        
    			System.out.println("树为空，无法删除");
    		}
    	}
    	
    	public void preOrder() {
        
    		if(this.root != null) {
        
    			this.root.preOrder();
    		} else {
        
    			System.out.println("二叉树为空，无法遍历");
    		}
    	}
    	
    	public void infixOrder() {
        
    		if(this.root != null) {
        
    			this.root.infixOrder();
    		} else {
        
    			System.out.println("二叉树为空，无法遍历");
    		}
    	}
    	
    	public void postOrder() {
        
    		if(this.root != null) {
        
    			this.root.postOrder();
    		} else {
        
    			System.out.println("二叉树为空，无法遍历");
    		}
    	}
    	
    	public HeroNode preOrderSearch(int no) {
        
    		if(this.root != null) {
        
    			return this.root.preOrderSearch(no);
    		} else {
        
    			return null;
    		}
    	}
    	
    	public HeroNode infixOrderSearch(int no) {
        
    		if(this.root != null) {
        
    			return this.root.infixOrderSearch(no);
    		} else {
        
    			return null;
    		}
    	}
    	
    	public HeroNode postOrderSearch(int no) {
        
    		if(this.root != null) {
        
    			return this.root.postOrderSearch(no);
    		} else {
        
    			return null;
    		}
    	}
    }
    //先创建HeroNode节点
    class HeroNode {
        
    	public int no;
    	public String name;
    	public HeroNode left;
    	public HeroNode right;
    	public int leftType;
    	public int rightType;
    	
    	
    	public int getLeftType() {
        
    		return leftType;
    	}
    
    	public void setLeftType(int leftType) {
        
    		this.leftType = leftType;
    	}
    
    	public int getRightType() {
        
    		return rightType;
    	}
    
    	public void setRightType(int rightType) {
        
    		this.rightType = rightType;
    	}
    
    	public HeroNode(int no, String name) {
        
    		this.no = no;
    		this.name = name;
    	}
    
    	public int getNo() {
        
    		return no;
    	}
    
    	public void setNo(int no) {
        
    		this.no = no;
    	}
    
    	public String getName() {
        
    		return name;
    	}
    
    	public void setName(String name) {
        
    		this.name = name;
    	}
    
    	public HeroNode getLeft() {
        
    		return left;
    	}
    
    	public void setLeft(HeroNode left) {
        
    		this.left = left;
    	}
    
    	public HeroNode getRight() {
        
    		return right;
    	}
    
    	public void setRight(HeroNode right) {
        
    		this.right = right;
    	}
    
    	@Override
    	public String toString() {
        
    		return "HeroNode [no=" + no + ", name=" + name + "]";
    	}
    	
    	
    	//删除节点
    	public void delNode(int no) {
        
    		if(this.left != null && this.left.no == no) {
        
    			this.left = null;
    			return ;
    		}
    		if(this.right != null && this.right.no == no) {
        
    			this.right = null;
    			return;
    		}
    		if(this.left != null) {
        
    			this.left.delNode(no);
    		}
    		if(this.right != null) {
        
    			this.right.delNode(no);
    		}
    		
    	}
    	
    	//前序遍历
    	public void preOrder() 	{
        
    		System.out.println(this);
    		if(this.left != null) {
        
    			this.left.preOrder();	
    		}
    		if(this.right != null) {
        
    			this.right.preOrder();
    		}
    	}
    	//中序遍历
    	public void infixOrder() 	{
        
    		if(this.left != null) {
        
    			this.left.infixOrder();	
    		}
    		System.out.println(this);
    		if(this.right != null) {
        
    			this.right.infixOrder();
    		}
    	}
    	//后序遍历
    	public void postOrder() 	{
        
    		if(this.left != null) {
        
    			this.left.postOrder();	
    		}
    		if(this.right != null) {
        
    			this.right.postOrder();
    		}
    		System.out.println(this);
    	}
    	
    	//前序查找
    	public HeroNode preOrderSearch(int no) {
        
    		System.out.println("进入前序遍历查找");
    		if(this.no == no) {
        
    			return this;
    		}
    		HeroNode resNode = null;
    		if(this.left != null) {
        
    			resNode = this.left.preOrderSearch(no);
    		}
    		if(resNode != null) {
        
    			return resNode;
    		}
    		if(this.right != null) {
        
    			resNode = this.right.preOrderSearch(no);
    		}
    		return resNode;
    	}
    	
    	//中序查找
    	public HeroNode infixOrderSearch(int no) {
        
    		HeroNode resNode = null;
    		if(this.left != null) {
        
    			resNode = this.left.infixOrderSearch(no);
    		}
    		if(resNode != null) {
        
    			return resNode;
    		}
    		System.out.println("进入中序遍历查找");
    		if(this.no == no) {
        
    			return this;
    		}
    		if(this.right != null) {
        
    			resNode = this.right.infixOrderSearch(no);
    		}
    		return resNode;
    	}
    	
    	//后序查找
    	public HeroNode postOrderSearch(int no) {
        
    		HeroNode resNode = null;
    		//判断当前的左子节点是否为空，如果不为空，则递归后序查找
    		if(this.left != null) {
        
    			resNode = this.left.postOrderSearch(no);
    		}
    		if(resNode != null) {
        //说明左子树找到了
    			return resNode;
    		}
    		//如果左子树没有找到，则向右子树递归进行后序遍历查找
    		if(this.right != null) {
        
    			resNode = this.right.postOrderSearch(no);
    		}
    		if(resNode != null) {
        
    			return resNode;
    		}
    		System.out.println("进入后序遍历查找");
    		//如果左右子树都没有找到，就比较当前节点是不是
    		if(this.no == no) {
        
    			return this;
    		}
    		return resNode;
    	}
    }

#### 4、堆排序 ####

package com.lyp.tree;
    
    import java.text.SimpleDateFormat;
    import java.util.Arrays;
    import java.util.Date;
    
    public class HeapSort {
        
    
    	public static void main(String[] args) {
        
    		//int[] arr = {4,6,8,5,9};
    		//创建80000个的随机数组
    		int[] arr = new int[8000000];
    		for(int i = 0; i < 8000000; i++) {
        
    			arr[i] = (int)(Math.random()*8000000);//生成一个[0,8000000] 数
    		}
    		
    		//System.out.println("排序前：");
    		//System.out.println(Arrays.toString(arr));
    		
    		
    		Date date1 = new Date();
    		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    		String date1Str = simpleDateFormat.format(date1);
    		System.out.println("排序前的时间是="+date1Str);
    		
    		heapSort(arr);
    		
    		Date date2 = new Date();
    		String date2Str = simpleDateFormat.format(date2);
    		System.out.println("排序后的时间是="+date2Str);//1秒 8百万数据
    		
    	}
    
    	public static void heapSort(int arr[]) {
        
    		int temp = 0;
    		System.out.println("堆排序！！！");
    		
    //		//分布完成
    //		adjustHeap(arr,1,arr.length);
    //		System.out.println("第1次"+Arrays.toString(arr));//4,9,8,5,6
    //		
    //		adjustHeap(arr,0,arr.length);
    //		System.out.println("第2次"+Arrays.toString(arr));//9,6,8,5,4
    		
    		//完成最终代码
    		//将无序序列构成一个堆，根据升序降序需求选择大顶堆或小顶堆
    		for(int i = arr.length / 2 - 1; i >= 0; i--) {
        
    			adjustHeap(arr,i,arr.length);
    		}
    		
    		/**
    		 * 将堆顶元素与末尾元素交换，将最大元素“沉底”到数组末端
    		 * 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整 +交换步骤，直到整个有序序列有序
    		 * 
    		 */
    		
    		for(int j = arr.length - 1; j > 0; j--) {
        
    			//交换
    			temp = arr[j];
    			arr[j] = arr[0];
    			arr[0] = temp;
    			adjustHeap(arr,0,j);
    		}
    		
    		//System.out.println("数组="+ Arrays.toString(arr));
    	
    	}
    	
    	public static void adjustHeap(int[] arr, int i, int length) {
        
    		int temp = arr[i];
    		for(int k = (i * 2 + 1); k < length;  k = (k * 2 + 1)) {
        
    			if(k + 1 < length && arr[k] < arr[k+1]) {
        
    				k++;
    			}
    			if(arr[k] > temp) {
        
    				arr[i] = arr[k];
    				i = k;
    			} else {
        
    				break;
    			}
    		}
    		arr[i] = temp;
    	}
    }

#### 5、赫夫曼树 ####

package com.lyp.tree;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    
    public class HuffmanTree {
        
    
    	public static void main(String[] args) {
        
    		int[] arr = {
        13,7,8,3,29,6,1};
    		Node root = createHuffmanTree(arr);
    		
    		
    		//测试
    		preOrder(root);
    	}
    	
    	
    	
    	
    	//前序遍历的方法
    	public static void preOrder(Node root) {
        
    		if(root != null) {
        
    			root.preOrder();
    		}else {
        
    			System.out.println("是空树，无法遍历");
    		}
    	}
    	
    	
    	
    	
    	//创建赫夫曼树的方法
    	/**
    	 * 
    	 * @param arr 需要创建成哈夫曼树的数组
    	 * @return  创建好后的哈夫曼树的root节点
    	 */
    	public static Node createHuffmanTree(int[] arr) {
        
    		//第一步为了操作方便
    		//1.遍历 arr 数组
    		//2.将arr的每一个元素构成一个Node
    		//3.将Node 放入ArrayList中
    		List<Node> nodes = new ArrayList<Node>();
    		for(int value : arr) {
        
    			nodes.add(new Node(value));
    		}
    		
    		
    		//处理过程是一个循环的过程
    		while(nodes.size() > 1) {
        
    			
    			//排序从小到大
    			Collections.sort(nodes);
    			
    			System.out.println("nodes ="+nodes);
    			
    			//取出每根节点权值最小的两个二叉树
    			//（1）取出权值最小的节点（二叉树）
    			Node leftNode = nodes.get(0);
    			//（2）取出权值第二小的节点（二叉树）
    			Node rightNode = nodes.get(1);
    			
    			//（3）构建一个新的二叉树
    			Node parent = new Node(leftNode.value + rightNode.value);
    			parent.left = leftNode;
    			parent.right = rightNode;
    			
    			//（4）从ArrayList 删除处理过的二叉树
    			nodes.remove(leftNode);
    			nodes.remove(rightNode);
    			//（5）将parent加入nodes
    			nodes.add(parent);
    		}
    		
    		
    		//返回哈夫曼树的root节点
    		return nodes.get(0);
    	}
    } 
    
    
    
    //创建节点类
    //为了让Node 对象直接排序Collections 集合排序
    //让Node 实现 Comparable 接口
    class Node implements Comparable<Node>{
        
    	int value; //节点权值
    	Node left;//指向左子节点
    	Node right;//指向右子节点 
    	
    	
    	//前序遍历
    	public void preOrder() {
        
    		System.out.println(this);
    		if(this.left != null) {
        
    			this.left.preOrder();
    		}
    		if(this.right != null) {
        
    			this.right.preOrder();
    		}
    	}
    	
    	
    	public Node(int value) {
        
    		this.value =value;
    	}
    
    	@Override
    	public String toString() {
        
    		return "Node [value=" + value + "]";
    	}
    
    	@Override
    	public int compareTo(Node o) {
        
    		// TODO Auto-generated method stub
    		//表示从小到大排序
    		return this.value - o.value;
    	}
    	
    	
    }

#### 6、赫夫曼编码（数据压缩、数据解压） ####

package com.lyp.huffmancode;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    public class HuffmanCode {
        
    
    	public static void main(String[] args) {
        
    		String content = "i like like like java do you like a java";
    		byte[] contentBytes = content.getBytes();
    		System.out.println(contentBytes.length);//40
    		
    		
    		byte[] huffmanCodesBytes = huffmanZip(contentBytes);
    		System.out.println("压缩后的结果是：" + Arrays.toString(huffmanCodesBytes)+"长度 =" +huffmanCodesBytes.length);
    		
    		
    		//分部过程
    		
    		/*
    		
    		List<Node> nodes = getNodes(contentBytes);
    		System.out.println("nodes="+ nodes);
    		
    		//测试
    		System.out.println("哈夫曼树");
    		Node huffmanTreeRoot = createHuffmanTree(nodes);
    		System.out.println("前序遍历");
    		preOrder(huffmanTreeRoot);
    		
    		//测试是否生成了对应的哈夫曼编码
    		Map<Byte,String> huffmanCodes = getCodes(huffmanTreeRoot);
    		System.out.println("~生成的哈夫曼编码表"+huffmanCodes);
    		
    		//测试
    		byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
    		System.out.println("huffmanCodeBytes" + Arrays.toString(huffmanCodeBytes));//17
    		
    		*/
    	}
    	
    	//使用一个方法，将前面的方法封装起来，便于我们调用
    	
    	private static byte[] huffmanZip(byte[] bytes) {
        
    		List<Node> nodes = getNodes(bytes);
    		//根据 nodes 创建 哈夫曼树
    		Node huffmanTreeRoot = createHuffmanTree(nodes);
    		//对应的哈夫曼编码（根据  哈夫曼树）
    		Map<Byte,String> huffmanCodes = getCodes(huffmanTreeRoot);
    		//根据生成的哈夫曼编码 ，压缩得到压缩后的哈夫曼编码字节数组
    		byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
    		return huffmanCodeBytes;
    	}
    	
    	//编写一个方法，将字符串对应的byte[] 数组，通过生成的哈夫曼编码表，返回一个哈夫曼码 压缩后的 byte[]
    	/**
    	 * 
    	 * @param bytes  这时原始的字符串对应的byte[]
    	 * @param huffmanCodes 生成的赫夫曼编码map
    	 * @return 返回哈夫曼编码处理后 byte[]
    	 */
    	
    	private static byte[] zip(byte[] bytes,Map<Byte ,String> huffmanCodes) {
        
    		//1.利用 huffmanCodes 将 bytes 转成 哈夫曼编码对应的字符串
    		StringBuilder stringBuilder = new StringBuilder();
    		//遍历bytes 数组
    		for(byte b: bytes) {
        
    			stringBuilder.append(huffmanCodes.get(b));
    		}
    		
    		//统计返回 byte[] huffmanCodeBytes 长度
    		//一句话  int len = (stringBuilder.length() + 7) / 8;
     		int len;
    		if(stringBuilder.length() % 8 == 0) {
        
    			len = stringBuilder.length() / 8;
    		} else {
        
    			len  = stringBuilder.length() / 8 + 1;
    		}
    		//创建存储压缩后的byte 数组
    		byte[] huffmanCodeBytes = new byte[len];
    		int index = 0;//记录第几个byte
    		for(int i = 0; i < stringBuilder.length(); i += 8) {
        //因为每8位对应一个byte，所以步长 +8 
    			String strByte;
    			if(i + 8 > stringBuilder.length()) {
        
    				strByte = stringBuilder.substring(i);
    			} else {
        
    				strByte = stringBuilder.substring(i, i + 8);
    			}
    			
    			
    			//将strByte 转成一个 byte ，放入 huffmanCodeBytes
    			huffmanCodeBytes[index] =(byte)Integer.parseInt(strByte,2);
    			index++;
    			
    		}
    		return huffmanCodeBytes;
    	}
    
    	//前序遍历
    	public static void preOrder(Node root) {
        
    		if(root != null) {
        
    			root.preOrder();
    		} else {
        
    			System.out.println("哈夫曼树为空");
    		}
    	}
    	
    	//生成哈夫曼树对应的哈夫曼编码
    	//思路
    	//1.将哈夫曼树存放在 Map<Byte,String> 形式
    	//32 -> 01 97 -> 100 100 -> 11000 等【形式】
    	static Map<Byte,String> huffmanCodes = new HashMap<Byte,String>();
    	//2.在生成的哈夫曼编码表示。需要去拼接路径，定义一个StringBuilder  存储某个叶子节点的路径
    	static StringBuilder stringBuilder = new StringBuilder();
    	
    	//为了调用方便，我们重载 getCodes
    	private static Map<Byte,String> getCodes(Node root){
        
    		if(root == null) {
        
    			return null;
    		}
    		//处理root的左子树
    		getCodes(root.left,"0",stringBuilder);
    		//处理root的右子树
    		getCodes(root.right,"1",stringBuilder);
    		return huffmanCodes;
    	}
    	
    	
    	/**
    	 * 功能：将传入的node节点的所有叶子节点的哈夫曼树得到，并放入huffmanCodes集合
    	 * @param node 传入节点
    	 * @param code 路径： 左节点是 0 ，右节点是 1
    	 * @param stringBuilder
    	 */
    	private static void getCodes(Node node,String code ,StringBuilder stringBuilder) {
        
    		StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
    		//将code 加入到 stringBuilder2
    		stringBuilder2.append(code);
    		if(node != null) {
        //如果node == null不处理
    			//判断当前node 是叶子节点还是非叶子节点
    			if(node.data == null) {
        //非叶子节点
    				//递归处理
    				//向左递归
    				getCodes(node.left,"0",stringBuilder2);
    				//向右递归
    				getCodes(node.right,"1",stringBuilder2);
    			} else {
        
    				//就表示找到了某个叶子节点的最后
    				huffmanCodes.put(node.data, stringBuilder2.toString());
    			}
    		}
    	}
    	
    	/**
    	 * 
    	 * @param bytes 接受字节数组
    	 * @return 返回的就是List 形式 [Node[data=97 ,weight = 5], Node[data = 32,weight = 9]......],
    	 */
    	private static List<Node> getNodes(byte[] bytes){
        
    		//1.先创建一个ArrayList
    		ArrayList<Node> nodes = new ArrayList<Node>();
    		
    		//遍历bytes ,统计 每一个byte出现的次数 -> map[key,value]
    		Map<Byte,Integer> counts = new HashMap<>();
    		for(byte b: bytes) {
        
    			Integer count = counts.get(b);
    			if(count == null) {
        //Map还没有这个字符数据，第一次
    				counts.put(b, 1);
    			} else {
        
    				counts.put(b,count + 1);
    			}
    		}
    		
    		//将每一个键值对转成一个Node 对象，并加入 nodes集合中
    		//遍历map
    		for(Map.Entry<Byte, Integer> entry: counts.entrySet()) {
        
    			nodes.add(new Node(entry.getKey(), entry.getValue()));
    		}
    		return nodes;
    	}
    	
    	//通过List 创建对应的哈夫曼树
    	public static Node createHuffmanTree(List<Node> nodes) {
        
    		while(nodes.size() > 1) {
        
    			//排序
    			Collections.sort(nodes);
    			//取出第一个最小的二叉树
    			Node leftNode = nodes.get(0);
    			//取出第二小的二叉树
    			Node rightNode = nodes.get(1);
    			//创建一个新的二叉树，它的根节点 没有data ，只有权值
    			Node parent = new Node(null,leftNode.weight + rightNode.weight);
    			parent.left = leftNode;
    			parent.right = rightNode;
    			
    			//将已经处理的两个二叉树从nodes 删除
    			nodes.remove(leftNode);
    			nodes.remove(rightNode);
    			//将新的二叉树，加入到nodes
    			nodes.add(parent);
    		}
    		//nodes 最后的节点 ，就是哈夫曼树的根节点
    		return nodes.get(0);
    	}
    }
    
    class Node implements Comparable<Node>{
        
    	Byte data;//存放数据(字符)本身，比如 'a' => 97 ' ' => 32
    	int weight;//权值，表示字符出现的次数
    	Node left;
    	Node right;
    	
    	
    
    	public Node(Byte data, int weight) {
        
    		this.data = data;
    		this.weight = weight;
    	}
    
    	@Override
    	public int compareTo(Node o) {
        
    		// 从小到大排序
    		return this.weight - o.weight;
    	}
    
    	@Override
    	public String toString() {
        
    		return "Node [data=" + data + ", weight=" + weight + "]";
    	}
    	
    	//前序遍历
    	public void preOrder() {
        
    		System.out.println(this);
    		if(this.left != null) {
        
    			this.left.preOrder();
    		}
    		if(this.right != null) {
        
    			this.right.preOrder();
    		}
    	}
    	
    }

[https_blog.csdn.net_weixin_46822367_article_details_115478461_spm_1001.2014.3001.5502]: https://blog.csdn.net/weixin_46822367/article/details/115478461?spm=1001.2014.3001.5502