?? binarytree.java
字號:
package graph;
/*
* 求哈夫曼樹
* @author 周建勇
*/
public class BinaryTree {
TreeNode[] node;
public BinaryTree(int[] w) {
int n = w.length;
node = new TreeNode[n];
node = initTree(node,n,w);
display(node,n);
node = createTree(node,n,w);
display2(node,n);
}
private void display2(TreeNode[] node2, int n) {
System.out.println("====================================================");
System.out.println("index\tweight\tleft\tright\tparent");
for(int i=0;i<n;i++)
{
System.out.println(i+"\t"+node2[i].getWeight()+"\t"+node2[i].left+"\t"+node2[i].right+"\t"+node2[i].parent.getWeight());
}
for(int i=n;i<2*n-2;i++)
{
System.out.println(i+"\t"+node2[i].getWeight()+"\t"+node2[i].left.getWeight()+"\t"+node2[i].right.getWeight()+"\t"+node2[i].parent.getWeight());
}
System.out.println(2*n-2+"\t"+node2[2*n-2].getWeight()+"\t"+node2[2*n-2].left.getWeight()+"\t"+node2[2*n-2].right.getWeight()+"\t"+node2[2*n-2].parent);
}
private void display(TreeNode[] node2, int n) {
System.out.println("====================================================");
System.out.println("index\tweight\tleft\tright\tparent");
for(int i=0;i<2*n-1;i++)
{
System.out.println(i+"\t"+node2[i].getWeight()+"\t"+node2[i].left+"\t"+node2[i].right+"\t"+node2[i].parent);
}
}
private TreeNode[] initTree(TreeNode[] a,int n,int[] weight) {
a=new TreeNode[2*n-1];
for(int i=0;i<2*n-1;i++)
{
if(i<n)
a[i]=new TreeNode(weight[i]);
else
a[i]=new TreeNode(0);
}
return a;
}
private TreeNode[] createTree(TreeNode[] a, int n, int[] w) {
for(int i=n;i<2*n-1;i++)
{
int min=65566,cmin=65566;
int x=0,cx=0;
for(int j=0;j<i;j++)
{
if(a[j].parent==null&&a[j].getWeight()<min)
{
cmin=min;
cx=x;
min=a[j].getWeight();
x=j;
}
else if(a[j].parent==null&&a[j].getWeight()<cmin)
{
cmin=a[j].getWeight();
cx=j;
}
}
a[i].setWeight(min+cmin);
a[i].left=new TreeNode(x);
a[i].right=new TreeNode(cx);
a[x].parent=new TreeNode(i);
a[cx].parent=a[x].parent;
}
return a;
}
public static void main(String[] args) {
int[] w = new int[]{1,2,3,4,5,6,7,8,9};
new BinaryTree(w);
}
}
class TreeNode {
private int weight;
TreeNode left;
TreeNode right;
TreeNode parent;
public TreeNode(int weight) {
this.weight = weight;
this.left = null;
this.right = null;
this.parent = null;
}
public int getWeight() {
return this.weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -