Java

ハフマンツリーの作成とトラバーサル（Java）



Huffman Tree Creation



ハフマンツリーの基本的な紹介：

n個のリーフノードとしてn個の重みが与えられると、二分木が構築されます。ツリーの加重パス長（wpl）が最小に達すると、バイナリツリーは最適なバイナリツリーと呼ばれ、ハフマンツリーとも呼ばれます。ツリー）、およびいくつかの本はホフマンツリーとして翻訳されています。 ハフマンツリーは、重み付きパスの長さが最も短いツリーであり、重みが大きいノードはルートに近くなります。
下の図の2番目のツリーは、wpl値が最小であるため、ハフマンツリーです。
画像

ハフマンツリーのいくつかの重要な概念：

1）、 パスとパスの長さ ：ツリーでは、ノードから下に到達できる子ノードまたは孫ノード間のパスはパスと呼ばれます。パス内のブランチの数は、パスの長さと呼ばれます。ルートノードの層数が1に指定されている場合、ルートノードからL番目の層のノードまでのパスの長さはL-1です。
二）、 ノードの重みと重み付きパスの長さ ：ツリー内のノードに特定の意味を持つ値が割り当てられている場合、この値はノードの重みと呼ばれます。ノードの加重パス長は、ルートノードからノードまでのパスの長さとノードの重みの積です。
3）、 ツリーの加重パス長 ：ツリーの加重パス長は、すべてのリーフノードの加重パス長の合計として定義され、WPL（加重パス長）として示されます。重みが大きく、ノードがルートノードに近い二分木です。最適な二分木。
4）、 最小のWPLはハフマンツリーです



タイトル説明：

シーケンス{13、7、8、3、29、6、1}を与えて、ハフマンツリーに変換するように依頼します

ハフマンツリーを形成する手順：

  1. 小さいものから大きいものへと並べ替える 、各データ、各データはノードであり、各ノードは最も単純な二分木と見なすことができます
  2. ルートノードを削除します 最小の重みを持つ2つ 二分木
  3. 新しい二分木を形成するために、新しい二分木のルートノードの重みは、前の2つの二分木のルートノードの重みの合計です。
    画像
  4. 次に、ルートノードの重みに従ってこの新しいバイナリツリーを再度並べ替え、シーケンス内のすべてのデータが処理されてハフマンツリーが取得されるまで手順1-2-3-4を繰り返します。
    画像

コード：

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 } }