一、构建最优二叉树
①、节点类:五个属性:结点的数据、父结点、左子结点、右子结点、赫夫曼编码
/**
* 树的结点类
*
* @author lenovo
*
*/
public class TreeNode {
private Object obj; // 数据
private TreeNode parent; // 父结点
private TreeNode leftchild; // 左子结点
private TreeNode rightchild; // 右子结点
private String code; //赫夫曼编码
/**
* 重写构造方法
* @param obj
*/
public TreeNode(Object obj){
this.obj=obj;
}
public Object getObj() {
return obj;
}
public void setObj(Object obj) {
this.obj = obj;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public TreeNode getLeftchild() {
return leftchild;
}
public void setLeftchild(TreeNode leftchild) {
this.leftchild = leftchild;
}
public TreeNode getRightchild() {
return rightchild;
}
public void setRightchild(TreeNode rightchild) {
this.rightchild = rightchild;
}
public String getCode() {
return code;
}
public void setCode(String code) {
this.code = code;
}
}
②、构建最有二叉树的思路:最优二叉树即整棵树的总权值最小,只有每个叶结点才存放数据。先建立一个队列(优先队列,已经排好序),根据数组中的数据建立结点存放到队列中。然后对队列进行构树操作,每次从优先队列中取出结点(用poll方法),分别设为左子结点、右子结点,再将左子结点和右子结点的数据相加并为父结点,再把父结点放到优先队列中去,再取出两个结点,分别设为左子结点、右子结点,再将左子结点和右子结点的数据相加并为父结点,如此循环,去两个放一个,直到优先队列中的只剩下一个结点,再将最后一个结点取出,设为最终的根结点。
/**
* 实现比较器的类
* @author lenovo
*
*/
public class MyComparator implements Comparator<TreeNode>{
/**
* 比较TreeNode中两个obj的大小,o1.getObj()>o2.getObj()返回1(从大到小排序),小于返回-1(从小到大排序)
*/
@Override
public int compare(TreeNode o1, TreeNode o2) {
return (Integer)o1.getObj()-(Integer)o2.getObj();
}
}
/**
* 将数组转化为最优二叉树的方法
*
* @param array
* @return:最优二叉树的根节点
*/
public TreeNode arraytoTree(int[] array) {
if (array == null) {
throw new RuntimeException("数组为空");
}
// 定义优先队列一个队列,指定初始长度和排序方式
java.util.PriorityQueue<TreeNode> pqueue = new java.util.PriorityQueue<TreeNode>(
array.length, new MyComparator());
// 遍历数组,得到数组中的元素,创建TreeNode对象,加入到优先队列中去
for (int i = 0; i < array.length; i++) {
TreeNode tree = new TreeNode(array[i]);
pqueue.add(tree);
}
// 如果优先队列中还有元素,构建赫夫曼树
while (pqueue.size() > 1) {
TreeNode ltree = pqueue.poll(); // 得到左子结点,poll()方法,取出列表头并移除
TreeNode rtree = pqueue.poll(); // 得到右子结点
// 创建根节点
TreeNode root = new TreeNode((Integer) ltree.getObj()
+ (Integer) rtree.getObj());
// 设置关系
root.setLeftchild(ltree);
root.setRightchild(rtree);
ltree.setParent(root);
rtree.setParent(root);
// 加入子结点
pqueue.add(root);
}
//得到根结点
TreeNode root = pqueue.peek();
return root;
}
二、对叶节点进行赫夫曼编码
从根结点开始,在父结点左边的编码为0,在父结点右边的编码为1,直到叶节点,即可以的得到每个叶节点的赫夫曼编码。
/**
* 设置并打印叶结点的赫夫曼编码 左:0; 右:1
*
* @param root
* :根结点
*/
public void printCode(TreeNode root) {
// 如果为叶节点
if (root.getLeftchild() == null && root.getRightchild() == null) {
System.out.println("结点:" + root.getObj());
System.out.println("\t\t赫夫曼编码:"+ root.getCode());
}
// 左子结点为0
if (root.getLeftchild() != null) {
String s = root.getCode();
if(s==null){ //如果是根结点的子左结点
root.getLeftchild().setCode("0");
}else{
root.getLeftchild().setCode(s+'0');
}
printCode(root.getLeftchild()); // 递归
}
// 右子结点为1
if (root.getRightchild() != null) {
String s = root.getCode();
if (s ==null) { //如果是根结点的子右结点
root.getRightchild().setCode( "1");
}else{
root.getRightchild().setCode( s+'1');
}
printCode(root.getRightchild()); // 递归
}
}
分享到:
相关推荐
最优二叉树 c++ 数据结构 最优二叉树 c++ 数据结构 最优二叉树 c++ 数据结构
利用最优二叉树,实现编码与解码功能。这是自己大一的课程设计作业。内容包括程序源码与pdf文档。
最优二叉树 最优二叉树算法
哈夫曼编码,最优二叉树的生成及各种算法遍历,非常有用哦,C语言版的哦
构造二叉树 最优二叉树 树 输出二叉树到屏幕 C# .net
二叉树 最优二叉树 树 算法实现 源码 高度 结点 叶子 输出 源码 源代码 建立二叉树算法 求二叉树高度算法的递归模型 求二叉树结点个数算法的递归模型 求二叉树叶子结点个数算法的递归模型 以括号表示法输出二叉树...
构建最优二叉树最优二叉树测试样例较难找,因此使用书本样例作为测试样例:输入如下图所示:结果如下:
用C++实现的最优二叉查找树,简单,明了,是数据结构里经典必学算法,初学者适用
哈夫曼二叉树编码译码器 里面有课程设计报告 课程是数据结构
适合非专业的学生使用。 本人是非计算机的学生,所以写的时候,可能不是很规矩 请您原谅! 平台:vc++6.0 操作系统 32位
二叉树、赫夫曼树,自己用C++实现,包括树的创建、遍历等常用操作。
最优二叉查找树,为算法导论上的算法,时间复杂度O(nlgn),思考题15.5-
构造一颗有n个叶子节点的二叉树,每个叶子节点带权为wi, 其中带权路径长度WPL最小的二叉树称作最优二叉树或者赫夫曼树。
要求:可以建立函数输入二叉树,并输出其赫夫曼树 在上交资料中请写明:存储结构、 基本算法(可以使用程序流程图) 、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法;
最优二叉树的设计,及其实现过程,比较有实际价值。
哈夫曼算法建立最优二叉树.doc
算法对最优二叉树的实现(课本上对最优二叉树的基本实现)
数据结构实验报告 《五、最优二叉树应用之哈夫曼编译码》
最优二叉搜索树详细的分析了最优二叉树的伪代码以及给出了算法设计,还包含一个例子用来更好的理解最优二叉搜索树的流程
可执行的赫夫曼树,也就是最优二叉树。是Word文档的。