发布时间 : 星期六 文章数据结构Java8二叉树与树更新完毕开始阅读6e4eec883169a4517723a3b0
表示权值
int parent,left,right; //父母结点和左、右孩子结点下标
public TriElement(int data, int parent, int left, int right) { this.data = data; this.parent = parent; this.left = left; this.right = right; }
public TriElement(int data) {
this(data, -1, -1, -1); }
public TriElement() {
this(0, -1, -1, -1); }
public String toString() {
return \+this.data+\\+this.parent+\\+this.left+\
\+this.right+\; } }
（2） N个叶结点的二叉树共有2n-1个结点， 数据表示：
//int[] weight={5,29,7,8,14,23,3,11};
TriElement[] huftree = new TriElement[2*n-1]; 见上表
（3） 构造Huffman树
A 建类，成员变量叶子结点个数，Huffman树的结点数组TriElement[] huftree;
B对huftree初始化。
C找两个最小结点，将两个结点和的权值相加作为新结点的权值。更新相应的左右孩子及父结点的标记忆。 D重复（n-1次）C直到树建成 即：
1)从现有的树中寻找没有父结点且权值最小的两个结点 权值为min1,min2//i1,i2 0,….k huftree[m] 2)用min1+min2作权值由产生一个新的结点Tri[k] Tri[i1] Tri[i2]的双亲为K， Tri[i1].p=Tri[i2].p=k; Tri[K].left=i1; Tri[k].right=i2
public class HuffmanTree //Huffman树 {
private int leafNum; //叶子结点个数
private TriElement[] huftree; //Huffman树的结点数组
public HuffmanTree(int[] weight) //构造指定权值集合的Huffman树 {
int n = weight.length; //n个叶子结点
this.leafNum = n;
this.huftree = new TriElement[2*n-1]; //n个叶子结点的Huffman树共有2n-1个结点
for(int i=0; i this.huftree[i] = new TriElement(weight[i]); for(int i=0; i { int min1=Integer.MAX_VALUE, min2=min1; //最小和次最小权值，初值为整数最大值 int x1=-1, x2=-1; //记录两个无父母的最小权值结点下标 for(int j=0; j if(huftree[j].data min2 = min1; x2 = x1; min1 = huftree[j].data; //min1记下最小权值 x1 = j; //x1记下最小权值结点的下标 }