wpl最小的就是赫夫曼樹(shù)(所有葉子節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和最小)

寫出來(lái)兩個(gè)節(jié)點(diǎn)連接，然后循環(huán)就可以了

package tree.huffmantree;import java.util.ArrayList; import java.util.Collections; import java.util.List;public class huffmanTree {public static void main(String[] args) {int [] arr = {13, 7, 8, 3, 29, 6, 1};Node huffmanTree = createHuffmanTree(arr);//測(cè)試（前序遍歷）preOrder(huffmanTree);}//編寫一個(gè)前序遍歷的方法public static void preOrder(Node root){if (root != null){root.preOrder();}else{System.out.println("空樹(shù)");}}//創(chuàng)建赫夫曼樹(shù)public static Node createHuffmanTree(int arr []){//第一步為了操作方便//1.遍歷arr數(shù)組//2.將arr的每個(gè)元素構(gòu)建成一個(gè)Node//3.將node放入到ArrayList中List<Node> nodes = new ArrayList<>();for(int value : arr){nodes.add(new Node(value));}//排序 從小到大while (nodes.size() > 1) {Collections.sort(nodes);//取出根節(jié)點(diǎn)權(quán)值最小的兩顆二叉樹(shù)//(1)取出權(quán)值最小的節(jié)點(diǎn)（二叉樹(shù)）Node leftNode = nodes.get(0);//(2)取出第二小的節(jié)點(diǎn)Node rightNode = nodes.get(1);//（3）構(gòu)建新的二叉樹(shù)Node parent = new Node(leftNode.value + rightNode.value);parent.left = leftNode;parent.right = rightNode;//（4）刪除掉取出的兩個(gè)nodes.remove(leftNode);nodes.remove(rightNode);//（5）將parent加入到nodesnodes.add(parent);}//最后返回root節(jié)點(diǎn)return nodes.get(0);} } //創(chuàng)建節(jié)點(diǎn)類 //為了讓node對(duì)象，支持排序，需要實(shí)現(xiàn)comparable接口 class Node implements Comparable<Node>{int value; //權(quán)值Node left; //左子節(jié)點(diǎn)Node right; //右子節(jié)點(diǎn)@Overridepublic int compareTo(Node o) {//從小到大排序return this.value - o.value;}public void preOrder(){System.out.println(this);if (this.left != null){this.left.preOrder();}if (this.right != null){this.right.preOrder();}}public Node(int value){this.value = value;}@Overridepublic String toString() {return "Node{" +"value=" + value +'}';} }

結(jié)果：

總結(jié)

以上是生活随笔為你收集整理的数据结构 - 赫夫曼树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。