Java

Tvorba a prechod stromu Huffmana (Java)

Huffman Tree Creation



Základné predstavenie Huffmanovho stromu:

Keď dáme n váh ako n listových uzlov, zostrojí sa binárny strom. Ak vážená dĺžka cesty (wpl) stromu dosiahne minimum, binárny strom sa nazýva optimálny binárny strom, tiež známy ako Huffmanov strom. Tree) a niektoré knihy sú preložené ako Hoffmanove stromy. Huffmanov strom je strom s najkratšou váženou dĺžkou cesty a uzol s väčšou hmotnosťou je bližšie ku koreňu.
Druhý strom na obrázku nižšie je Huffmanov strom, pretože má najmenšiu hodnotu wpl
obrázok

Niekoľko dôležitých konceptov Huffmanovho stromu:

1), Cesta a dĺžka cesty : Na strome sa cesta medzi uzlami detí alebo vnukov, na ktorú sa dá dostať z uzla nadol, nazýva cesta. Počet vetiev v ceste sa nazýva dĺžka cesty. Ak je počet vrstiev koreňového uzla určený ako 1, dĺžka cesty od koreňového uzla k uzlu L-tej vrstvy je L-1.
dva), Hmotnosť uzla a vážená dĺžka dráhy : Ak je uzlu v strome priradená hodnota s určitým významom, potom sa táto hodnota nazýva váha uzla. Vážená dĺžka cesty uzla je: súčin dĺžky cesty od koreňového uzla k uzlu a hmotnosti uzla.
3), Vážená dĺžka cesty stromu : Vážená dĺžka cesty stromu je definovaná ako súčet dĺžok váženej cesty všetkých uzlov listov, označených ako WPL (vážená dĺžka cesty), binárny strom s vyššou váhou a bližším uzlom ku koreňovému uzlu. optimálny binárny strom.
4), Najmenšou WPL je Huffmanov strom



Popis názvu:

Dajte vám sekvenciu {13, 7, 8, 3, 29, 6, 1} a požiadajte o prevod na strom Huffman



Kroky na vytvorenie Huffmanovho stromu:

  1. Triediť od najmenších po najväčšie , Každé dáta, každé dáta sú uzlom, každý uzol možno považovať za najjednoduchší binárny strom
  2. Odstráňte koreňový uzol Dve s najmenšou hmotnosťou Binárny strom
  3. Na vytvorenie nového binárneho stromu je váha koreňového uzla nového binárneho stromu súčtom váh koreňových uzlov predchádzajúcich dvoch binárnych stromov.
    obrázok
  4. Potom tento nový binárny strom znova roztriedte podľa váhy koreňového uzla a opakujte kroky 1-2-3-4, kým nebudú spracované všetky údaje v sekvencii a kým sa nezíska Huffmanov strom.
    obrázok

Kód:

package Tree import java.util.ArrayList import java.util.Collection import java.util.Collections /** * @ClassName: HuffmanTree * @Description: Create a Huffman tree and its preorder traversal * @author Golven * @date October 27, 2019 * */ public class HuffmanTree { public static void main(String[] args) { int[] arr = { 13, 7, 8, 3, 29, 6, 1 } preOrder(createHuffmanTree(arr)) } public static void preOrder(Node root) { if (root != null) { root.preOrder() } else { System.out.println('It's an empty tree') return } } /** * * @Title: createHuffmanTree * @Description: Create a Huffman tree * @param @param arr needs to be created as an array of Huffman numbers * @return Node returns the root node of the tree */ public static Node createHuffmanTree(int[] arr) { // Traverse the arr array and put each element in the arr array into the ArrayList ArrayList<Node> nodes = new ArrayList<Node>() for (int value : arr) {// Perform this for each element in arr, and assign the value of each element to value nodes.add(new Node(value)) } // The processing process is a cyclic process while (nodes.size() > 1) { Collections.sort(nodes)// Sort from smallest to largest // Take out the node with the smallest weight Node leftNode = nodes.get(0) // Take out the second smallest node Node rightNode = nodes.get(1) // Create the root node of the left and right nodes, the value is equal to the sum of the values ​​of the two child nodes Node parent = new Node(leftNode.value + rightNode.value) // Build a binary tree parent.left = leftNode parent.right = rightNode // Delete the processed node from the ArrayList nodes.remove(leftNode) nodes.remove(rightNode) // Add the new node created to the array nodes.add(parent) } return nodes.get(0) } } //Create a Node node class //Because the initialized array needs to be sorted in ascending order, Collections are used, so a comparable interface must be implemented in the Node class class Node implements Comparable<Node> { public int value public Node left public Node right // preorder traversal 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 } @Override public String toString() { return 'Node [value=' + value + ']' } @Override // this.value-o.value means ascending order public int compareTo(Node o) { // indicates ascending order return this.value - o.value } }