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
