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;
	}
}