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

书读的越多而不加思考,你就会觉得你知道得很多;而当你读书而思考得越多的时候,你就会越清楚地看到,你知道得很少。

导读:本篇文章讲解 Java数据结构与算法——树篇,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

Java数据结构与算法: https://blog.csdn.net/weixin_46822367/article/details/115478461?spm=1001.2014.3001.5502.

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://www.bmabk.com/index.php/post/123092.html

(0)

相关推荐

发表回复

登录后才能评论
半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!