数据结构Java8二叉树与树

表示权值

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记下最小权值结点的下标 }

else if(huftree[j].data

min2 = huftree[j].data;

x2 = j;