哈夫曼树的练习
程序员文章站
2022-06-09 23:15:46
...
一、实验目的及要求
1：找出一棵二叉树中相距路径最远的两个节点。
2：构造一棵哈夫曼树。
二、实验内容及步骤
1、
（1）
public class DistanceOfBinaryTree {
public static void main(String[] args) {
TreeNode p0 = new TreeNode(0);
TreeNode p1 = new TreeNode(1);
TreeNode p2 = new TreeNode(2);
TreeNode p3 = new TreeNode(3);
TreeNode p4 = new TreeNode(4);
TreeNode p5 = new TreeNode(5);
TreeNode p6 = new TreeNode(6);
TreeNode p7 = new TreeNode(7);
TreeNode p8 = new TreeNode(8);
TreeNode p9 = new TreeNode(9);
p0.lchild = p1;
p0.rchild = p2;
p1.lchild = p3;
p1.rchild = p4;
p2.lchild = p5;
p2.rchild = p6;
p3.lchild = p7;
p5.rchild = p8;
p8.lchild = p9;
Result res = new Result();
maxDistance(p0, res);
System.out.println(res.maxDistance);
}
public static void maxDistance(TreeNode root, Result res){
if(root == null)
return;
Result lhs = new Result();
Result rhs = new Result();
maxDistance(root.lchild, lhs); //左子树的最大高度及最远距离
maxDistance(root.rchild, rhs); //右子树的最大高度及最远距离
res.maxHeight = Math.max(lhs.maxHeight, rhs.maxHeight) + 1;
res.maxDistance = Math.max(Math.max(lhs.maxDistance, rhs.maxDistance), lhs.maxHeight + rhs.maxHeight + 2);
private static class Result{
private int maxDistance = 0; //初始化最远距离(根的左右孩子结点处为0)
private int maxHeight = -1; //初始化最大高度(根节点处为-1)
}
private static class TreeNode{
private int rootl;
private TreeNode lchild;
private TreeNode rchild;
TreeNode(int rootl){
this.rootl = rootl;
}
（2）
public class HuffmanTree01 {
int[] weight;
HuffmanNode node;
int flag;
public HuffmanTree01() {
}
public HuffmanTree01(int[] weight) {
this.weight=weight;
flag=0;
node=null;
}
//构造哈夫曼树
public HuffmanNode[] setHuffmanTree() {
int n=weight.length;
int m=2*n-1;
HuffmanNode[] HN=new HuffmanNode[m];
int i;
for(i=0;i<n;i++)
HN[i]=new HuffmanNode(weight[i]);
for(i=n;i<m;i++) {
HuffmanNode min1=selectMin(HN,i-1);
min1.flag=1;
HuffmanNode min2=selectMin(HN,i-1);
min2.flag=1;
//构造和的父结点，并修改其父结点的权值
HN[i]=new HuffmanNode();
min1.parent=HN[i];
min2.parent=HN[i];
HN[i].lchild=min1;
HN[i].rchild=min2;
HN[i].weight=min1.weight+min2.weight;
}
node=HN[HN.length - 1];
return HN;
}
//在HN[0..i-1]选择不在哈夫曼树中且weight最小的结点
private HuffmanNode selectMin(HuffmanNode[] HN,int end) {
HuffmanNode min=HN[end];
for(int i=0;i<=end;i++) {
HuffmanNode h=HN[i];
if(h.flag==0&&h.weight<min.weight) //不在哈夫曼树中且weight最小的结点
min=h;
}
return min;
}
//求距离最远的两个结点
public HuffmanNode[] MaxDistance(HuffmanNode[] HN){
if(HN.length>2) {
HuffmanNode[] farthestnode=new HuffmanNode[2]; //存放距离最远的两个结点
int max=0;
for(int i=0;i<weight.length-1;i++) {
skip: //循环跳转
for(int j=i+1;j<weight.length;j++)
{
int min1=1, min2=1;
for(HuffmanNode A = HN[i].parent; A != null; A = A.parent, min1++, min2 = 1) {
for(HuffmanNode B = HN[j].parent; B != null; B = B.parent, min2++) {
if(A==B) {
if(min1+min2>max) {
max=min1+min2;
farthestnode[0]=HN[i];
farthestnode[1]=HN[j+1];
}
continue skip;
}
}
}
}
}
System.out.println("最远的距离是:" + max);
return farthestnode;
}
else
return null;
}
public static void main(String[] args) {
int[] W= {6,30,8,9,15,24,4,12}; //初始化权值
HuffmanTree01 T=new HuffmanTree01(W); //构造哈夫曼树
int[][] HN=T.huffmanCoding(W);
System.out.println("");
System.out.print("输出哈夫曼树的权值：");
for(int i=0;i<HN.length;i++) {
System.out.print(W[i]+" ");
}
HuffmanNode[] nodes = T.setHuffmanTree();
HuffmanNode[] max = T.MaxDistance(nodes);
System.out.println("输出距离最远的两个结点：");
for (int i = 0; i < max.length; i++) //输出距离最远的两个结点
System.out.println("结点"+i+":"+max[i].weight);
}
private int[][] huffmanCoding(int[] W) {
int n=W.length;
int m=2*n-1;
HuffmanNode[] HN=new HuffmanNode[m];
int i;
for(i=0;i<n;i++)
HN[i]=new HuffmanNode(W[i]);
for(i=n;i<m;i++) {
HuffmanNode min1=selectMin(HN,i-1);
min1.flag=1;
HuffmanNode min2=selectMin(HN,i-1);
min2.flag=1;
HN[i]=new HuffmanNode();
min1.parent=HN[i];
min2.parent=HN[i];
HN[i].lchild=min1;
HN[i].rchild=min2;
HN[i].weight=min1.weight+min2.weight;
}
int[][] HuffCode=new int[n][n];
for(int j=0;j<n;j++) {
int start=n-1;
for(HuffmanNode c=HN[j],p=c.parent;p!=null;c=p,p=p.parent) {
if(p.lchild.equals(c))
HuffCode[j][start--]=0;
else
HuffCode[j][start--]=1;
}
HuffCode[j][start]=-1;
}
return HuffCode;
}
}
2、
（1）
public class HuffmanNode {
public int weight;
public int flag;
public HuffmanNode parent;
public HuffmanNode lchild;
public HuffmanNode rchild;
public HuffmanNode() {
this(0);
}
public HuffmanNode(int weight) {
this.weight=weight;
flag=0;
parent=lchild=rchild=null;
}
（2）
public class HuffmanTree {
public int [][] huffmanCoding(int[]W){
int n=W.length;
int m=2*n-1;
HuffmanNode[]HN=new HuffmanNode[m];
int i;
for(i=0;i<n;i++)
HN[i]=new HuffmanNode(W[i]);
for(i=n;i<m;i++) {
HuffmanNode min1=selectMin(HN,i-1);
min1.flag=1;
HuffmanNode min2=selectMin(HN,i-1);
min2.flag=1;
HN[i]=new HuffmanNode();
min1.parent=HN[i];
min2.parent=HN[i];
HN[i].lchild=min1;
HN[i].rchild=min2;
HN[i].weight=min1.weight+min2.weight;
}
int [][] HuffCode=new int[n][n];
for(int j=0;j<n;j++) {
int start=n-1;
for(HuffmanNode c=HN[j],p=c.parent;p!=null;c=p,p=p.parent)
if(p.lchild.equals(c))
HuffCode[j][start--]=0;
else
HuffCode[j][start--]=1;
HuffCode[j][start]=-1;
}
return HuffCode;
}
private HuffmanNode selectMin(HuffmanNode[]HN,int end) {
HuffmanNode min=HN[end];
for(int i=0;i<=end;i++) {
HuffmanNode h=HN[i];
if(h.flag==0&&h.weight<min.weight)
min=h;
}
return min;
}
public static void main(String[] args) {
int[] W= {6,30,8,9,15,24,4,12};
HuffmanTree T=new HuffmanTree();
int [][] HN=T.huffmanCoding(W);
System.out.println("哈夫曼编码为:");
for(int i=0;i<HN.length;i++) {
System.out.print(W[i]+" ");
for(int j=0;j<HN[i].length;j++) {
if(HN[i][j]==-1) {
for(int k=j+1;k<HN[i].length;k++)
System.out.print(HN[i][k]);
break;
}
}
System.out.println();
}
}
}