Java 最优二叉树的哈夫曼算法的简单实现

最优二叉树也称哈夫曼树,讲的直白点就是每个结点都带权值,我们让大的值离根近、小的值离根远,实现整体权值(带权路径长度)最小化。

哈夫曼算法的思想我认为就是上面讲的,而它的算法实现思路是这样的:
从根结点中抽出权值最小的两个(涉及排序,但是我这个实现代码没做严格的排序,只有比较)合并出新的根结点重新加入排序(被抽出来的两个自然是变成非根结点了啊),就这样循环下去,直到合并完成,我们得到一颗最优二叉树——哈夫曼树。

说明:
(1)哈夫曼树有n个叶子结点,则我们可以推出其有n-1个分支结点。因此我在定义名为huffmanTree的HuffmanNode类型数组时定义长度为2*n-1。
(2)这里排序相关没有做得很好,只是为了实现而实现,以后慢慢完善。
(3)理论上讲哈夫曼树应该是不仅仅局限于数值,能compare就行,但这里只用int表示。

下面是代码:

首先定义哈夫曼树结点

public class HuffmanNode {

  private int weight = -1;

  private int parent = -1;

  private int left = -1;

  private int right = -1;

  public HuffmanNode(int weight) {
    super();
    this.weight = weight;
  }

  public HuffmanNode(int weight, int left, int right) {
    super();
    this.weight = weight;
    this.left = left;
    this.right = right;
  }

  public int getWeight() {
    return weight;
  }

  public void setWeight(int weight) {
    this.weight = weight;
  }

  public int getParent() {
    return parent;
  }

  public void setParent(int parent) {
    this.parent = parent;
  }

  public int getLeft() {
    return left;
  }

  public void setLeft(int left) {
    this.left = left;
  }

  public int getRight() {
    return right;
  }

  public void setRight(int right) {
    this.right = right;
  }

  @Override
  public String toString() {
    return "HuffmanNode [weight=" + weight + ", parent=" + parent + ","
        + " left=" + left + ", right=" + right + "]";
  }

}

定义一下哈夫曼树的异常类

public class TreeException extends RuntimeException {

  private static final long serialVersionUID = 1L;

  public TreeException() {}

  public TreeException(String message) {
    super(message);
  }

}

编码实现(做的处理不是那么高效)

public class HuffmanTree {

  protected HuffmanNode[] huffmanTree;

  public HuffmanTree(int[] leafs) {
    //异常条件判断
    if (leafs.length <= 1) {
      throw new TreeException("叶子结点个数小于2,无法构建哈夫曼树");
    }
    //初始化储存空间
    huffmanTree = new HuffmanNode[leafs.length*2-1];
    //构造n棵只含根结点的二叉树
    for (int i = 0; i < leafs.length; i++) {
      HuffmanNode node = new HuffmanNode(leafs[i]);
      huffmanTree[i] = node;
    }
    //构造哈夫曼树的选取与合并
    for (int i = leafs.length; i < huffmanTree.length; i++) {
      //获取权值最小的结点下标
      int miniNum_1 = selectMiniNum1();
      //获取权值次小的结点下标
      int miniNum_2 = selectMiniNum2();
      if (miniNum_1 == -1 || miniNum_2 == -1) {
        return;
      }
      //两个权值最小的结点合并为新节点
      HuffmanNode node = new HuffmanNode(huffmanTree[miniNum_1].getWeight() +
          huffmanTree[miniNum_2].getWeight(), miniNum_1, miniNum_2);
      huffmanTree[i] = node;
      huffmanTree[miniNum_1].setParent(i);
      huffmanTree[miniNum_2].setParent(i);
    }
  }

  /**
   * 获取权值最小的结点下标
   * @return
   */
  private int selectMiniNum1() {
    //最小值
    int min = -1;
    //最小值下标
    int index = -1;
    //是否完成最小值初始化
    boolean flag = false;
    //遍历一遍
    for (int i = 0; i < huffmanTree.length; i++) {
      //排空、只看根结点,否则跳过
      if (huffmanTree[i] == null || huffmanTree[i].getParent() != -1) {
        continue;
      } else if (!flag) {   //没初始化先初始化然后跳过
        //初始化
        min = huffmanTree[i].getWeight();
        index = i;
        //以后不再初始化min
        flag = true;
        //跳过本次循环
        continue;
      }
      int tempWeight = huffmanTree[i].getWeight();
      //低效比较
      if (tempWeight < min) {
        min = tempWeight;
        index = i;
      }
    }
    return index;
  }

  /**
   * 获取权值次小的结点下标
   * @return
   */
  private int selectMiniNum2() {
    //次小值
    int min = -1;
    //是否完成次小值初始化
    boolean flag = false;
    //最小值下标(调用上面的方法)
    int index = selectMiniNum1();
    //最小值都不存在,则次小值也不存在
    if (index == -1) {
      return -1;
    }
    //次小值下标
    int index2 = -1;
    //遍历一遍
    for (int i = 0; i < huffmanTree.length; i++) {
      //最小值不要、排空、只看根结点,否则跳过
      if (index == i || huffmanTree[i] == null || huffmanTree[i].getParent() != -1) {
        continue;
      } else if (!flag) {   //没初始化先初始化然后跳过
        //初始化
        min = huffmanTree[i].getWeight();
        index2 = i;
        //以后不再初始化min
        flag = true;
        //跳过本次循环
        continue;
      }
      int tempWeight = huffmanTree[i].getWeight();
      //低效比较
      if (tempWeight < min) {
        min = tempWeight;
        index2 = i;
      }
    }
    return index2;
  }

}

测试类1

public class HuffmanTreeTester {

  public static void main(String[] args) {
    int[] leafs = {1, 3, 5, 6, 2, 22, 77, 4, 9};
    HuffmanTree tree = new HuffmanTree(leafs);
    HuffmanNode[] nodeList = tree.huffmanTree;
    for (HuffmanNode node : nodeList) {
      System.out.println(node);
    }
  }

}

测试结果1

HuffmanNode [weight=1, parent=9, left=-1, right=-1]
HuffmanNode [weight=3, parent=10, left=-1, right=-1]
HuffmanNode [weight=5, parent=11, left=-1, right=-1]
HuffmanNode [weight=6, parent=12, left=-1, right=-1]
HuffmanNode [weight=2, parent=9, left=-1, right=-1]
HuffmanNode [weight=22, parent=15, left=-1, right=-1]
HuffmanNode [weight=77, parent=16, left=-1, right=-1]
HuffmanNode [weight=4, parent=11, left=-1, right=-1]
HuffmanNode [weight=9, parent=13, left=-1, right=-1]
HuffmanNode [weight=3, parent=10, left=0, right=4]
HuffmanNode [weight=6, parent=12, left=1, right=9]
HuffmanNode [weight=9, parent=13, left=7, right=2]
HuffmanNode [weight=12, parent=14, left=3, right=10]
HuffmanNode [weight=18, parent=14, left=8, right=11]
HuffmanNode [weight=30, parent=15, left=12, right=13]
HuffmanNode [weight=52, parent=16, left=5, right=14]
HuffmanNode [weight=129, parent=-1, left=15, right=6]

图形表示:

测试类2

public class HuffmanTreeTester {

  public static void main(String[] args) {
    int[] leafs = {2, 4, 5, 3};
    HuffmanTree tree = new HuffmanTree(leafs);
    HuffmanNode[] nodeList = tree.huffmanTree;
    for (HuffmanNode node : nodeList) {
      System.out.println(node);
    }
  }

}

测试结果2

HuffmanNode [weight=2, parent=4, left=-1, right=-1]
HuffmanNode [weight=4, parent=5, left=-1, right=-1]
HuffmanNode [weight=5, parent=5, left=-1, right=-1]
HuffmanNode [weight=3, parent=4, left=-1, right=-1]
HuffmanNode [weight=5, parent=6, left=0, right=3]
HuffmanNode [weight=9, parent=6, left=1, right=2]
HuffmanNode [weight=14, parent=-1, left=4, right=5]

图形表示:

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Java编程求二叉树的镜像两种方法介绍

    给出一棵二叉树,求它的镜像,如下图:右边是二叉树是左边二叉树的镜像. 仔细分析这两棵树的特点,看看能不能总结出求镜像的步骤.这两棵树的根节点相同,但他们的左右两个子节点交换了位置.因此我们不妨先在树中交换根节点的两个子节点,就得到了下面一幅图中的第二颗树 解法1(递归) 思路1:如果当前节点为空,返回,否则交换该节点的左右节点,递归的对其左右节点进行交换处理. /*class TreeNode{ int val; TreeNode left=null; TreeNode right=null;

  • Java实现表达式二叉树

    什么是二叉树,这里不再介绍,可以自行百度:二叉树.在这里利用java实现"表达式二叉树". 表达式二叉树的定义  第一步先要搞懂表达式二叉树是个什么东东?举个栗子,表达式:(a+b×(c-d))-e/f.将数字放在叶子节点,将操作符放在分支节点,就构成了一个二叉树,由于存储的是一个表达式,称之为"表达式二叉树". 童靴们可能好奇这个到底是怎么构建的?就拿45+23*56/2-5来说吧.首先取出第一个数字45放在叶子节点,遇到"+"后将其放到分支节

  • Java实现打印二叉树所有路径的方法

    本文实例讲述了Java实现打印二叉树所有路径的方法.分享给大家供大家参考,具体如下: 问题: 给一个二叉树,把所有的路径都打印出来. 比如,对于下面这个二叉树,它所有的路径为: 8 -> 3 -> 1 8 -> 2 -> 6 -> 4 8 -> 3 -> 6 -> 7 8 -> 10 -> 14 -> 13 思路: 从根节点开始,把自己的值放在一个数组里,然后把这个数组传给它的子节点,子节点同样把自己的值放在这个数组里,又传给自己的子节点,

  • JAVA 实现二叉树(链式存储结构)

    二叉树的分类(按存储结构) 树的分类(按存储结构) 顺序存储(用数组表示(静态二叉树))   链式存储 一些特别的二叉根: 完全二叉树,平衡二叉树(AVL),线索二叉树,三叉的(带父亲的指针)    二叉搜索树或者叫二叉 查找树(BST)  所用二叉树如下图所示: 二叉树的Java实现(链式存储结构) class TreeNode { private int key = 0; private String data = null; private boolean isVisted = false

  • 图解二叉树的三种遍历方式及java实现代码

    二叉树(binary tree)是一颗树,其中每个节点都不能有多于两个的儿子. 1.二叉树节点 作为图的特殊形式,二叉树的基本组成单元是节点与边:作为数据结构,其基本的组成实体是二叉树节点(binary tree node),而边则对应于节点之间的相互引用. 如下,给出了二叉树节点的数据结构图示和相关代码: // 定义节点类: private static class BinNode { private Object element; private BinNode lChild;// 定义指向

  • Java中二叉树的建立和各种遍历实例代码

    这是个常见的面试题,比如说通过二叉树的先序和中序遍历,得到二叉树的层序遍历等问题 先序+中序->建树 假设现在有个二叉树,如下: 此时遍历顺序是: PreOrder: GDAFEMHZ InOrder: ADEFGHMZ PostOrder: AEFDHZMG 现在给出先序(preOrder)和中序(InOrder),建立一颗二叉树 或者给出中序(InOrder)和后序(PostOrder), 建立二叉树,其实是一样的 树节点的定义: class Tree{ char val; Tree lef

  • Java实现求二叉树的深度和宽度

    这个是常见的对二叉树的操作.总结一下: 设节点的数据结构,如下: 复制代码 代码如下: class TreeNode {     char val;     TreeNode left = null;     TreeNode right = null; TreeNode(char _val) {         this.val = _val;     } } 1.二叉树深度 这个可以使用递归,分别求出左子树的深度.右子树的深度,两个深度的较大值+1即可. 复制代码 代码如下: // 获取最大

  • java 数据结构二叉树的实现代码

    1. 二叉树接口 public interface BinaryTreeInterface<T> { public T getRootData(); public int getHeight(); public int getNumberOfRoot(); public void clear(); public void setTree(T rootData); // 用rootData设置树 public void setTree(T rootData,BinaryTreeInterface

  • java编程求二叉树最大路径问题代码分析

    题目: Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree. For example: Given the below binary tree, 1 / \ 2 3 Return 6. 节点可能为负数,寻找一条最路径使得所经过节点和最大.路径可以开始和结束于任何节点但是不能走回头路. 这道题虽然

  • Java中二叉树数据结构的实现示例

    来看一个具体的习题实践: 题目 根据二叉树前序遍历序列例如:7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#,构建二叉树,并且用前序.中序.后序进行遍历 代码 import java.util.Scanner; public class BinaryTree { public static String[] str; public static int count; /** * 静态内部类,定义二叉树节点 */ static class TreeNode { public Str

  • 图解红黑树及Java进行红黑二叉树遍历的方法

    红黑树 红黑树是一种数据结构与算法课堂上常常提到但又不会细讲的树,也是技术面试中经常被问到的树,然而无论是书上还是网上的资料,通常都比较刻板难以理解,能不能一种比较直观的方式来理解红黑树呢?本文将以图形的方式来解释红黑树的插入与删除操作. 对树结构的学习是一个递进的过程,我们通常所接触的树都是二叉树,二叉树简单来说就是每个非叶子节点都有且只有两个孩子,分别叫做左孩子和右孩子.二叉树中有一类特殊的树叫二叉查找树,二叉查找树是一种有序的树,对于每个非叶子节点,其左子树的值都小于它,其右子树的值都大于

随机推荐