不只有叶子结点，是所有结点，输入一个有n个叶子结点权值构造的哈夫曼树，输出每一个结点的权值。
参考一下：https://blog.csdn.net/wardseptember/article/details/80717653
如果对你有帮助，可以点击我这个回答右上方的【采纳】按钮，给我个采纳吗，谢谢
public class Node implements Comparable<Node> {
int weight;
Node lChild;
Node rChild;
Object value;
Object key;
public Node(int weight) {
this.weight = weight;
}
public Node(int weight, Node lChild, Node rChild) {
this.weight = weight;
this.lChild = lChild;
this.rChild = rChild;
}
@Override
public int compareTo(Node o) {
return new Integer(this.weight).compareTo(new Integer(o.weight));
}
@Override
public String toString() {
return "Node [weight=" + weight + ", lChild=" + lChild + ", rChild=" + rChild + ", value=" + value + ", key="
+ key + "]";
}
}
public class HuffmanTreeUtil {
//构建哈夫曼树
public static Node createHuffman(int[] weights) {
//优先队列，用于辅助构建哈夫曼树
Queue<Node> nodeQueue = new PriorityQueue<>();
Node[] nodes = new Node[weights.length];
//构建森林，初始化nodes数组
for(int i=0; i<weights.length; i++){
nodes[i] = new Node(weights[i]);
nodeQueue.add(nodes[i]);
}
//主循环，当结点队列只剩一个结点时结束
while (nodeQueue.size() > 1) {
//从结点队列选择权值最小的两个结点
Node left = nodeQueue.poll();
Node right = nodeQueue.poll();
//创建新结点作为两结点的父节点
Node parent = new Node(left.weight + right.weight, left, right);
nodeQueue.add(parent);
}
return nodeQueue.poll();
}
}
public static void main(String[] args) {
int[] weights = {2,3,7,9,18,25};
Node tree = HuffmanTreeUtil.createHuffman(weights);
System.err.println(tree);
}