主要使用自己上一篇文章中的自定义二叉树类实现了霍夫曼树,霍夫曼编码和讲一个数学算式建成树。
1.霍夫曼树和霍夫曼编码
霍夫曼树即最优二叉树,因为它每个叶子结点到根结点的距离与叶子结点的权值有关,往往此权值越大,它的路径越短,即带权路径长度要保持最小,所以叫它最优二叉树。
引用
(1)设给定的一组权值为{W1,W2,W3,……Wn},据此生成森林F={T1,T2,T3,……Tn},F 中的每棵二叉树只有一个带权为Wi的根节点(i=1,2,……n)。
算法思想为:
(2)在F中选取两棵根节点的权值最小和次小的二叉树作为左右构造一棵新的二叉树,新二叉树根节点的权值为其左、右子树根节点的权值之和。
(3)在F中删除这两棵最小和次小的二叉树,同时将新生成的二叉树并入森林中。
(4)重复(2)(3)过程直到F中只有一棵二叉树为止。
以下为代码:
结点类的补充
private String code = " ";
public String getCode() {
return code;
}
public void setCode(String code) {
this.code = code;
}
核心代码:
/**
* 按照传入的数组创建霍夫曼树的方法 通过优先队列实现
*
* @param arr
* 传入的整型数组
*/
public void creatHuffmanTree(int[] arr) {
if (arr == null) {
throw new RuntimeException("空数组,无法建树");
} else {
// 创建优先队列对象
PriorityQueue<TNode> que = new PriorityQueue<TNode>(arr.length,
new MyComparator());
// 将数组中的元素建立结点对象并加入到优先队列中去
for (int i = 0; i < arr.length; i++) {
TNode node = new TNode(arr[i]);
que.add(node);
}
while (que.size() > 1) {
// 将两个结点连成树
TNode ltree = que.poll();
TNode rtree = que.poll();
TNode node = new TNode((Integer) ltree.getObj()
+ (Integer) rtree.getObj());
node.setLeft(ltree);
node.setRight(rtree);
ltree.setParent(node);
rtree.setParent(node);
// 加入子结点
que.add(node);
}
root = que.poll();
}
}
/**
* 打印此树的霍夫曼编码
*
* @param node
* 由指定位置开始做为根结点
*
*/
public void printHCode(TNode node) {
if (node == null) {
throw new RuntimeException("空树,无法编码!");
} else {
TNode current = node;
if (current.getLeft() != null) {
// 向左编码1
current.getLeft().setCode(current.getCode() + '1');
printHCode(current.getLeft());
// 向右编码0
current.getRight().setCode(current.getCode() + '0');
printHCode(current.getRight());
} else {
System.out.println(current.getObj()+"的霍夫曼编码是: \t"+current.getCode());
}
}
}
2.将算术表达式建成树
在这段代码中主要通过将原本的代码转换为逆波兰表达式,以去除括号,然后转换为波兰表达式(波兰表达式将运算符写在前面,操作数写在后面,便于建树),建成树。计算时只需要后序遍历就可以简单的计算这个数学算式。
代码如下:
/**
* 将一个数学算式转化为一个树
*
* @param s
* 此算式的字符串
*/
public void AFtoTree(String s) {
Stack<Character> sta = new Stack<Character>();
sta.push('#');
char[] ch = new char[s.length() + 1];
int j = 0;
// 将中序表达式转化为逆波兰表达式
for (int i = 0; i < s.length(); i++) {
char cha = s.charAt(i);
if (cha != '+' && cha != '-' && cha != '*' && cha != '/'
&& cha != '(' && cha != ')') {
ch[j++] = cha;
} else if (cha == '(') {
sta.push(cha);
} else if (cha == ')') {
char c = sta.pop();
while (c != '(') {
ch[j++] = c;
c = sta.pop();
}
} else {
char c = sta.peek();
while (c == '*' || c == '/') {
ch[j++] = sta.pop();
c = sta.peek();
}
sta.push(cha);
}
}
char c = sta.pop();
while (c != '#') {
ch[j++] = c;
c = sta.pop();
}
// 将逆波兰转化为波兰表达式
char[] temp = new char[j + 1];
for (int i = 0; i < j; i++) {
temp[j - i - 1] = ch[i];
}
temp[j] = '#';
// 由波兰表达式建树
root = creatAFTree(temp);
}
/**
* 将波兰表达式建成一棵树
*
* @param ch
* @param key
* @return
*/
public TNode creatAFTree(char[] ch) {
TNode current = null;
if (ch[key] != '#') {
if (ch[key] == '+' || ch[key] == '-' || ch[key] == '*'
|| ch[key] == '/') {
current = new TNode(ch[key++]);
TNode temp = creatAFTree(ch);
if (temp == null) {
} else {
current.setLeft(temp);
temp.setParent(current);
}
TNode temp2 = creatAFTree(ch);
if (temp2 == null) {
} else {
current.setRight(temp2);
temp2.setParent(current);
}
return current;
} else {
current = new TNode(ch[key++]);
return current;
}
} else {
return null;
}
}
分享到:
相关推荐
递归先序遍历二叉树: 递归中序遍历二叉树: 递归后序遍历二叉树: 非递归先序遍历二叉树: 非递归中序遍历二叉树: 非递归后序遍历二叉树: 非递归中序遍历二叉树(算法2): 层次遍历二叉树: 递归计算单...
java实现二叉树非递归前序中序后序遍历
霍夫曼树用的是类模板,还包括一些树的基本操作,遍历,结点数,深度等!对初学者还是很有意义的!!
代码实现: 二叉树的查找、插入、删除和输出根节点到当前节点的路径 二叉树的前序遍历,中序遍历和后续遍历 TreeNode.java --定义树节点 Mytree.java----创建树结构和上述功能函数 TestTree.java --测试上述的功能
C++的二叉树和霍夫曼编码的应用文档。有代码和详细注释。主要取自王红梅的C++数据结构。加上自己的整理。
树的基本运算:创建树;输出树(凹入显示);遍历树(先序、中序、后序、层次);求二叉树的深度;求叶子数;求结点数。
二叉树操作:太多详情看书1
详细的树和二叉树的教程,还附有源代码 部分代码如下: 二叉树头文件.h //二叉树的二叉链表存储表示 typedef struct BiTNode {TElemType data; //二叉树结点数据域 struct BiTNode *lchild,*rchild; //左右孩子指针...
这段代码运用Java实现了二叉树算法的核心功能,包括节点的插入和三种基本的遍历方式——中序、前序和后序。通过创建节点类和二叉树类,它构建了一个灵活且可扩展的二叉树结构,为后续的复杂操作提供了坚实的基础。
java实现二叉树数据结构,简单明了,免费下载
Java实现二叉树的基本操作
输入共3行:第一行为满二叉树中结点个数n(n<1024);第二行为n个整数,表示二叉树的先序遍历序列;第三行也有n个整数,表示二叉树的中序遍历序列。整数间以空格分割。
简单的描述了JAVA实现二叉树
B树和二叉树的区别:二叉树最多能有两个子节点;B树最多只能有M个子节点,最少有三个子节点 三、B+树 介绍:B+树是B树的升级版本,就目前情况,绝大部分都已经用B+树代替了B树了,文件管理、索引等等 四、红黑树 ...
题目:从先序和中序遍历结果恢复二叉树。 分析:输入先序序列和中序序列,从而得到一个完整的二叉树。 步骤:1.找到root,前序遍历的第一节点G就是root。 2.继续观察前序遍历GDAFEMHZ,除了知道G是root,剩下的节点...
利用java写了两个案例是关于二叉树和平衡树的分别为数组的和链式的。 功能: 1.三种历遍方式的输出。 2.平衡树的重构。 3.节点的添加以及删除。 4.平均查找长度的计算。
其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树:1.若它的左子树非空,则左子树上所有结点的值均小于根结点的值;2.若它的右子树非空,则右子树上所有结点的值均大于根结点的值;3.左、右子树本身又各...
树和二叉树 树和二叉树 树和二叉树 树和二叉树树和二叉树树和二叉树
java实现二叉树遍历demo,一个简单是实例
树和二叉树的实验报告