---
title: "最优二叉树（哈夫曼树）知识点"
author: "mywebcode"
date: "2013-11-17T22:07:00Z"
tags: []
slug: "untitled"
draft: false
lastmod: "2014-04-30T09:36:28Z"
id: 2058729
url: "https://mywebcode.iteye.com/blog/2058729"
---

**路径**：在一棵树中从一个结点往下到孩子或孙子结点之间的通路

**结点的路径长度**：从根节点到该节点的路径上分支的数目

**树的路径长度**：树中每个结点的路径长度之和

**结点的权**：给树中的结点赋予一个某种含义的值，则该值为该节点的权

**结点的带权路径长度**：结点的路径长度乘以结点的权

**树的带权路径长度（WPL）**：树中所有叶子结点的带权路径长度 (Weight Path Length)

**最优二叉树（哈夫曼树）**：带权路径长度最小的二叉树

**构造哈夫曼树：**

给定n个权值{w1,w2,…wn}，则构造出的哈夫曼树有n个叶子结点,构造过程如下：

1\. 将w1,w2…wn按从小到大排序，并将他们看做n棵只有一个结点的树组成的森林；

2\. 选出两个根节点权值最小的树合并，作为新树的左右子树，新树的根节点权值是左右子树根节点权值之和

3\. 从森林中删除选取的两棵树，将新树加入森林

4\. 重复2,3，直到只剩一棵树，所得即为最优二叉树

实例如下：给定权值{5,6,2,7,9}构造哈夫曼树

解：(1)排序后为w={2,5,6,7,9}

取出2,5![](http://img.blog.csdn.net/20131118212917421?watermark%2F2%2Ftext%2FaHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMjExNjQ1Nw=%3D%2Ffont%2F5a6L5L2T%2Ffontsize%2F400%2Ffill%2FI0JBQkFCMA%3D%3D%2Fdissolve%2F70%2Fgravity%2FSouthEast)w={6,7,7,9}

取出6,7![](http://img.blog.csdn.net/20131118213010062?watermark%2F2%2Ftext%2FaHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMjExNjQ1Nw=%3D%2Ffont%2F5a6L5L2T%2Ffontsize%2F400%2Ffill%2FI0JBQkFCMA%3D%3D%2Fdissolve%2F70%2Fgravity%2FSouthEast)![](http://img.blog.csdn.net/20131118213106140?watermark%2F2%2Ftext%2FaHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMjExNjQ1Nw=%3D%2Ffont%2F5a6L5L2T%2Ffontsize%2F400%2Ffill%2FI0JBQkFCMA%3D%3D%2Fdissolve%2F70%2Fgravity%2FSouthEast)w={7,9,13}

取出7,9![](http://img.blog.csdn.net/20131118213206234?watermark%2F2%2Ftext%2FaHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMjExNjQ1Nw=%3D%2Ffont%2F5a6L5L2T%2Ffontsize%2F400%2Ffill%2FI0JBQkFCMA%3D%3D%2Fdissolve%2F70%2Fgravity%2FSouthEast)![](http://img.blog.csdn.net/20131118213220359?watermark%2F2%2Ftext%2FaHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMjExNjQ1Nw=%3D%2Ffont%2F5a6L5L2T%2Ffontsize%2F400%2Ffill%2FI0JBQkFCMA%3D%3D%2Fdissolve%2F70%2Fgravity%2FSouthEast) w={13,16}

取出13,16![](http://img.blog.csdn.net/20131118213304953?watermark%2F2%2Ftext%2FaHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMjExNjQ1Nw=%3D%2Ffont%2F5a6L5L2T%2Ffontsize%2F400%2Ffill%2FI0JBQkFCMA%3D%3D%2Fdissolve%2F70%2Fgravity%2FSouthEast)

上面的哈夫曼树的wpl=6X2+7X2+2X3+5X3+9X2=65

**哈夫曼树在编码中的应用：**

在通讯中，经常需要将文本转换成二进制串，即编码。为了使电文代码尽可能的短，需要另经常使用的字符采用短的编码，使用频率小的字符采用长的编码。同时，一个字符的编码不能包含另一个字符的编码，例如A是00，B就不能是001，使用哈夫曼树就可以很好的实现 ,

例如A,B,C,D,E的频率分别是6,7,2,5,9对应的哈夫曼树为：

![](http://img.blog.csdn.net/20131118213340265?watermark%2F2%2Ftext%2FaHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMjExNjQ1Nw=%3D%2Ffont%2F5a6L5L2T%2Ffontsize%2F400%2Ffill%2FI0JBQkFCMA%3D%3D%2Fdissolve%2F70%2Fgravity%2FSouthEast)

另左子树的路径为0，右子树路径为1

![](http://img.blog.csdn.net/20131118213413593?watermark%2F2%2Ftext%2FaHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMjExNjQ1Nw=%3D%2Ffont%2F5a6L5L2T%2Ffontsize%2F400%2Ffill%2FI0JBQkFCMA%3D%3D%2Fdissolve%2F70%2Fgravity%2FSouthEast)

则A:00 B:01 C:100 D:101 E:11