(6.6.1)--ch6-12HuffmanTree0821.pdf

Data Structures and Algorithms Huffman Tree 26.6 Huffman Tree The Huffman tree is also called the optimal binary tree.It is the binary tree with the smallest weighted path length value.It can be used to construct the optimal coding and has a wide range of applications in information transmission and data compression.Data Structures and AlgorithmsData Structures and AlgorithmsChapter 6 Trees and Binary Trees6.6 Huffman Tree31.Related concepts1.Related conceptsPath：The sequence of branches from one node to another in the tree.Path length：The number of branches on the path.Node power：The value assigned to the node.Weighted path length：The product of the weight of a node and the length of the path from the node to the root of the tree.Weighted path length of the tree：The sum of the weighted path lengths of all leaf nodes in the tree，marked as：WPL=Wi Lii=1nData Structures and AlgorithmsData Structures and AlgorithmsChapter 6 Trees and Binary Treesn is the number of leaf nodesWi is the weight of the i-th leafLi is the path length from the i-th leaf node to the root4 WPL=Wi Lii=1nABCD7524WPLa=+52+22+42=3672Data Structures and AlgorithmsData Structures and AlgorithmsChapter 6 Trees and Binary Trees6.6 Huffman TreeExample a：ABCD982635CDExample b：=(7+5+4+2)2WPLb=82(9+8)2+(3+5+2+6)35Data Structures and AlgorithmsData Structures and AlgorithmsChapter 6 Trees and Binary Trees6.6 Huffman Tree2 6497a27649b(7+9)4+63+42+21=92WPLa=(7+6+9)2+(2+4)3=62WPLb=72496c(2+4+6)2+(7+9)3=72WPLc=6Data Structures and AlgorithmsData Structures and AlgorithmsChapter 6 Trees and Binary Trees6.6 Huffman TreeThe optimal binary tree：Under the condition that the number of leaves n and the weight of each leaf Wi are determined,the binary tree with the smallest weighted path length WPL value of the tree is called the optimal binary tree.7Data Structures and AlgorithmsData Structures and AlgorithmsChapter 6 Trees and Binary Trees6.6 Huffman Tree8Data Structures and AlgorithmsData Structures and AlgorithmsChapter 6 Trees and Binary Trees6.6 Huffman Tree Huffman based on the characteristics of the optimal binary tree：The larger the weight,the closer to the root！The method of construction is given,so the optimal binary tree is also called Huffman tree.6.6 Huffman Tree9Initialization：Construct a set F=T1,T2,Tn of n binary trees according to the given n weights w1,w2,wn.Each binary tree contains only one root node with weight wi,and the left and right subtrees are empty trees；Select the two binary trees with the smallest root node weight in F,and construct a new binary tree as the left and right subtrees respectively,and set the weight of the root node of the new binary tree as the root node of its left and right subtrees.Sum of weights；Delete the selected two trees from F and insert the new tree just generated；Repeat steps and until there is only one tree in F.Data Structures and AlgorithmsData Structures and AlgorithmsChapter 6 Trees and Binary Trees2.Huffman tree establishment2.Huffman tree establishment9410Example 1：Given the weight W=5,8,4,9,3,4,construct the Huffman tree.Initialization：Construct a set of n binary treesF=T1,T2,Tn；58493 Select the two trees with the smallest root node weights as subtrees to construct a new binary tree；F:549 Delete these two trees from F and add the new tree just generated；7 Select the two trees with the smallest root node weights as subtrees to construct a new binary tree；815 Delete these two trees from F and add the new tree just generated；Select the two trees with the smallest root node weights as subtrees to construct a new binary tree；918 Delete these two trees from F and add the new tree just generated；183333Data Structures and AlgorithmsData Structures and AlgorithmsChapter 6 Trees and Binary Trees6.6 Huffman Tree437 Select the two trees with the smallest root node weights as subtrees to construct a new binary tree；Delete these two trees from F,and add the newly generated tree at the same time；15Until F contains only one tree,the end.113.Implementation of 3.Implementation of Huffman Algorithm Huffman Algorithm A static linked list can be used as a storage structure.That is,an array containing 2N-1 elements is used to store the Huffman tree,and the parent-child relationship between nodes is indicated by subscripts.Data Structures and AlgorithmsData Structures and AlgorithmsChapter 6 Trees and Binary Trees6.6 Huffman Tree For a given N leaf nodes,construct a Huffman tree,the final total number of nodes must be：2N-1.When using the Huffman tree for encoding and decoding,both the parent information of the node and the child information of the node are used,so a static three-pronged linked list is used to store the Huffman tree.6.6 Huffman Tree12Node structureweight parent LChild RChild157853weight parentLChildRChild12345357815400400500512034Data Structures and AlgorithmsData Structures and AlgorithmsChapter 6 Trees and Binary Trees6.6 Huffman Tree13Node structureweight parent LChild RChildData Structures and AlgorithmsData Structures and AlgorithmsChapter 6 Trees and Binary Trees#define N 20#define M 2*N-1typedef struct int weight;int parent;int LChild;int RChild;HTNode,HuffmanTreeM+1;14Huffman tree construction process1.Initialization：The leaf weights and parent-child cursors are all set to 0(nodes corresponding to subscripts 1 n),and all fields of other nodes are set to 0(nodes corresponding to subscripts n+1 2n-1).Choose the smallest tree：Construct a new tree：Data Structures and AlgorithmsData Structures and AlgorithmsChapter 6 Trees and Binary Trees6.6 Huffman TreeSelect the two binary trees with the smallest weight of the root node(the node whose parent domain is 0).The selection range is the node with the subscript 1i-1.Calculate the weight of the new node i,set the left and right child domains of the new node,and assign the parent domains of the two subtrees(implied the deletion of the two trees from F).2.Execute in a loop(i=n+12n-1)to construct a Huffman tree.1557328F:32557815105101525251 2 3 4 5 6 7 8 9987654321RChildLChildparentweight00000000000000000008000200030007000587255291561910437586687Lea f nodeBranch node初始化完毕初始化完毕选择小树、构造新树选择小树、构造新树n-1次次Until it contains only one treeData Structures and AlgorithmsData Structures and AlgorithmsChapter 6 Trees and Binary Trees6.6 Huffman Tree6.6 Huffman Tree16Huffman algorithm:Huffman algorithm:void CrtHuffmanTree(HuffmanTree ht,int w,int n)for(i=1;i=n;i+)hti=wi,0,0,0;m=2*n-1;for(i=n+1;i=m;i+)hti=0,0,0,0；for(i=n+1;im;i+)select(ht,i-1,&s1,&s2);hti.weight=hts1.weight+hts2.weight;hts1.parent=i;hts2.parent=i;hti.LChild=s1;hti.RChild=s2;Data Structures and AlgorithmsData Structures and AlgorithmsChapter 6 Trees and Binary Trees Thanks