2.5.3哈夫曼树及其应用 1、哈夫曼树 树的路径长度的概念: 从一个结点到另一个结点之间的分支数 目称为这对结点之间的路径长度。 树的路径长度是从树的根到每一结点的 路径长度之和。 2/22 202l/2/
2021/2/22 2 2.5.3哈夫曼树及其应用 1、哈夫曼树 树的路径长度的概念： 从一个结点到另一个结点之间的分支数 目称为这对结点之间的路径长度。 树的路径长度是从树的根到每一结点的 路径长度之和
树的路径长度用PL表示。 4 PL=0+1+1+2+2+2+2=10 2/22 202l/2/
2021/2/22 3 1 2 4 5 3 6 7 PL=0+1+1+2+2+2+2=10 树的路径长度用PL表示
树的路径长度用PL表示。 C 4 PL=0+1+1+2+2+2+2=10 PL=0+1+1+2+2+3+3=12 2/22 202l/2/
2021/2/22 4 1 2 4 5 3 6 7 PL=0+1+1+2+2+2+2=10 1 2 4 5 C 6 7 PL=0+1+1+2+2+3+3=12 树的路径长度用PL表示
结点带权的路径长度: 从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度: 树中叶子结点带权路径长度之和。 ⑤ 7 52 4 WPL=7*2+5*2+2*2+4*2=36 2/22 202l/2/
2021/2/22 5 结点带权的路径长度： 从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度： 树中叶子结点带权路径长度之和。 a b c d 7 5 2 4 WPL=7*2+5*2+2*2+4*2=36
树的带权路径长度记作: WPL= ∑ KLK k=1 其中:W为树中每个叶子结点的权; L为每个叶子结点到根的路径长度。 7 52 wPL=7*2+5*2+2*2+4*2=36 wPL最小的二叉树就称作最优二叉树或哈夫曼树。 2021/2/22
2021/2/22 6 树的带权路径长度记作： 其中：Wk为树中每个叶子结点的权； Lk为每个叶子结点到根的路径长度。 = = n k WPL WKLK 1 a b c d 7 5 2 4 WPL=7*2+5*2+2*2+4*2=36 WPL最小的二叉树就称作最优二叉树或哈夫曼树