Java实现构造哈夫曼树 给出以下权重2, 3, 7, 9, 18, 25，构造哈夫曼树。 以先序遍历方式输出节点，换行隔开。 注意：构造哈夫曼树时，节点值小的在左侧。

在Java中，我们可以使用优先队列（通常是一个最小堆）和贪心算法来构建哈夫曼树。以下是步骤：

1. 首先，创建一个Node类，包含一个值weight、一个左子节点left和一个右子节点right，以及一个用于比较大小的方法，通常基于权重。

class Node {
    int weight;
    Node left, right;

    // 其他必要的构造方法和比较方法
}

2. 创建一个优先队列，并将所有给定的权重作为初始元素放入队列。

import java.util.PriorityQueue;

PriorityQueue<Node> queue = new PriorityQueue<>();
queue.add(new Node(2));
queue.add(new Node(3));
queue.add(new Node(7));
queue.add(new Node(9));
queue.add(new Node(18));
queue.add(new Node(25));

3. 循环直到队列只剩下一个元素，这是哈夫曼树的根节点。每次从队列取出两个权值最小的节点，合并成一个新的节点，新节点的权值等于这两个子节点的权值之和，然后将新节点插入队列。

Node newNode = null;
while (queue.size() > 1) {
    Node leftNode = queue.poll();
    Node rightNode = queue.poll();
    newNode = new Node(leftNode.weight + rightNode.weight);
    newNode.left = leftNode;
    newNode.right = rightNode;
    queue.add(newNode);
}

4. 最后队列中的唯一元素就是哈夫曼树的根节点。先序遍历根节点及其左右子节点，得到先序遍历的结果。

List<Node> preOrderTraversal = new ArrayList<>();
preOrderTraversal.add(newNode);

// 先序遍历打印
for (Node node : preOrderTraversal) {
    System.out.print(node.weight + " ");
}