请选择 进入手机版 | 继续访问电脑版
 找回密码
 立即注册

QQ登录

只需要一步,快速开始

搜索
开启左侧

哈夫曼树(最优二叉树) - Java实现

马上注册,分享更多源码,享用更多功能,让你轻松玩转云大陆。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
简介
哈夫曼树(Huffman)树又称最优二叉树,是指对于一组带有确定权值的叶子结点所构造的具有带权路径长度最短的二叉树。从树中一个结点到另一个结点之间的分支构成了两结点之间的路径,路径上的分支个数称为路径长度。二叉树的路径长度是指由根结点到所有叶子结点的路径长度之和。如果二叉树中的叶子结点都有一定的权值,则可将这一概念拓展:设二叉树具有n个带权值的叶子结点,则从根结点到每一个叶子结点的路径长度与该叶子结点权值的乘积之和称为二叉树路径长度,记做:
WPL = W1L1 + W2L2 + ...... + WnLn;
构建过程
① 对数据中出现过的元素各产生一个树叶节点,并赋予其出现的频率。
② 令N为T1和T2的父节点,其中T1和T2是出现频率最低的两个节点,令N的频率为T1和T2的频率之和
③ 消去两个节点,插入N节点,重复前面的步骤。
145503frrmq99hcraqamp8.jpg


145503m8xq4jb3qkcdx48r.jpg


代码实现
HuffmanTree.java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class HaffmanTree {
private List nodes;
private Node root;
// 实现排序接口,添加结点自动排序,从小到大排序
private static class Node implements Comparable{
private int value;
private Node left;
private Node right;
public Node(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
@Override
public int compareTo(Node o) {
return this.value - o.value;
}
}
public HaffmanTree() {}
public void bulidHaffmanTree(int[] arr) {
nodes = new ArrayList();
for (int i = 0; i < arr.length; i++) {
nodes.add(new Node(arr));
}
root = createHaffmanTree(nodes);
}
private Node createHaffmanTree(List nodes) {
while (nodes.size() > 1) {
// 排序,每次取最小的两个结点
Collections.sort(nodes);
// 获得权值最小的两个结点,左结点大于右结点
Node leftChild = nodes.get(1);
Node rightChild = nodes.get(0);
// 生成新结点
Node newNode = new Node(leftChild.value + rightChild.value);
newNode.left = leftChild;
newNode.right = rightChild;
// 删除权值最小的两个结点
nodes.remove(0);
nodes.remove(0);
// 将新结点加入到集合中
nodes.add(newNode);
}
return nodes.get(0);
}
// 先序遍历
public void preOrder() {
preOrder(root);
}
private void preOrder(Node root) {
ArrayDeque stack = new ArrayDeque();
while (root != null || !stack.isEmpty()) {
System.out.println(root.value);
stack.push(root);
root = root.left;
}
if (!stack.isEmpty()) {
root = stack.pop();
root = root.right;
}
}
// 中序遍历
public void inOrder() {
preOrder(root);
}
private void inOrder(Node root) {
ArrayDeque stack = new ArrayDeque();
while (root != null || !stack.isEmpty()) {
stack.push(root);
root = root.left;
}
if (!stack.isEmpty()) {
root = stack.pop();
System.out.println(root.value);
root = root.right;
}
}
// 非递归后序遍历
public void postOrder() {
postOrder(root);
}
private void postOrder(Node root) {
ArrayDeque stack = new ArrayDeque();
Node cur = root;
Node pre = null;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.peek();
if (cur.right == null || cur.right == pre) {
System.out.print(cur.value + " ");
pre = cur;
stack.pop();
cur = null;
} else {
cur = cur.right;
}
}
}
// 层序遍历
public void levelOrder() {
levelOrder(root);
}
private void levelOrder(Node root) {
ArrayDeque queue = new ArrayDeque();
Node curr = root;
if (curr == null)
return;
queue.add(curr);
while (!queue.isEmpty()) {
curr = queue.remove();
System.out.print(curr.value + " ");
if (curr.left != null)
queue.add(curr.left);
if (curr.right != null)
queue.add(curr.right);
}
}
}
测试代码
HuffmanTreeTest.java
public class HaffmanTreeTest {
public static void main(String[] args) {
int arr[] = {13, 7, 8, 3, 29, 6, 1};
HaffmanTree haffmanTree = new HaffmanTree();
haffmanTree.bulidHaffmanTree(arr);
haffmanTree.postOrder();
System.out.println();
haffmanTree.levelOrder();
}
}
版权声明:本文为CSDN博主「键盘上Dance」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/qq_43327091/article/details/102932360
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

  • 0 关注
  • 0 粉丝
  • 1 帖子
广告招商