字母 频率003560.0139002790.03780.13040.02890.01990.05280.06270.00130.0420.03900249 字母 频率00070.07970.01994000200670.06070.1050.02490.00210.01490007001990.008
字 母 a b c d e f g h i j k l m 频 率 0.0356 0.0139 0.0279 0.0378 0.1304 0.0289 0.0199 0.0528 0.0627 0.0013 0.042 0.0339 0.0249 字 母 n o p q r s t u V w x y z 频 率 0.0707 0.0797 0.0199 0.0012 0.0677 0.0607 0.1045 0.0249 0.0092 0.0149 0.0017 0.0199 0.0008
Definition 32: Let t be a tree with weigths wi sw2s.<wn at its leaf nodes. The weighted leaf path length w(t)of T is W(t)=>wl, where li is the path length from the root to vertex i. Say that a binary tree t is optimal if w(T) has its minimum value over all possible trees with the same set of leaf nodes
Definition 32: Let T be a tree with weigths w1w2...wn at its leaf nodes. The weighted leaf path length w(T) of T is W(T)= = n i i i w l 1 , where li is the path length from the root to vertex i. Say that a binary tree T is optimal if w(T) has its minimum value over all possible trees with the same set of leaf nodes
Example: Let t be a binary tree with weigths 3, 5, 7, 9 a)∑l=48 b)∑w1=47
Example: Let T be a binary tree with weigths 3, 5, 7, 9 a ) = 48, i i w l b) = 47, i i w l