二叉树是由n（n>=0）个结点组成的有序集合，集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 二叉树的五种形态：

2、二叉树的存储结构模型

树的另一种表示法：孩子兄弟表示法 A、每个结点都有一个指向其第一个孩子的指针 B、每个结点都有一个指向其第一个右兄弟的指针 孩子兄弟表示法的特性： A、能够表示任意的树形结构 B、每个结点包含一个数据成员和两个指针成员 C、孩子结点指针和兄弟结点指针构成树杈

如果二叉树中所有分支结点的度数都为2，并且叶子结点都在统一层次上，则二叉树为满二叉树。

如果一棵具有n个结点的高度为k的二叉树，树的每个结点都与高度为k的满二叉树中编号为1——n的结点一一对应，则二叉树为完全二叉树。 完全二叉树的特性： A、同样结点数的二叉树，完全二叉树的高度最小 B、完全二叉树的叶子结点仅出现在最下边两层，并且最底层的叶子结点一定出现在左边，倒数第二层的叶子结点一定出现在右边。 C、完全二叉树中度为1的结点只有左孩子。

A、在二叉树的第i层上最多有2^(i-1)个结点（i>=1）。 B、高度为k的二叉树，最多有2^k-1个结点（k>=0）。 C、对任何一棵二叉树，如果其叶结点有n个，度为2的非叶子结点有m个，则 n = m + 1。 D、具有n个结点的完全二叉树的高度为logn + 1 E、对于有n个结点的完全二叉树，按层次对结点进行编号（从上到下，从左到右），对于任意编号为i的结点：

1、二叉树的存储结构实现

二叉树结点包含四个固定的成员：结点的数据域、指向父结点的指针域、指向左子结点的指针域、指向右子结点的指针域。结点的数据域、指向父结点的指针域从TreeNode模板类继承而来。 二叉树结点的实现：

A、基于数据元素的查找 定义基于数据元素查找的函数

B、基于结点的查找 定义基于结点查找的函数

根据插入的位置定义二叉树结点的位置枚举类型：

在node结点的pos位置插入newnode结点的功能函数如下：

 //插入结点，无位置要求
 //插入结点，指定插入位置

 //插入数据，指定插入位置和父结点
 //插入数据，指定父结点

A、基于数据元素值删除

//根据数据元素删除结点

将二叉树中所有在堆空间分配的结点销毁。 清除node结点为根节点的二叉树的功能函数：

A、树中结点的数量 定义计算某个结点为根结点的树的结点的数量

B、树的高度 获取node结点为根结点的二叉树的高度的功能函数：

C、树的度 获取node为根结点的二叉树的度的功能函数：

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问依次，且仅被访问一次。 根据游标思想，提供一组遍历的先关函数，按层次访问二叉树中的数据元素。

定义克隆node结点为根结点的二叉树的功能函数：

判断两棵二叉树中的数据元素是否对应相等 定义二叉树相等比较的功能函数：

将当前二叉树与参数btree二叉树中对应的数据元素相加，返回一棵在堆空间创建的新的二叉树。 二叉树相加实例如下： 定义将两棵二叉树相加的功能函数：

三、二叉树的典型遍历方式

二叉树有先序、中序、后序三种遍历方式，三种遍历方法的不同主要是取决于根节点的遍历顺序。

如果二叉树为空，则无操作，直接返回。 如果二叉树非空，则执行以下操作： A、访问根结点； B、先序遍历左子树； C、先序遍历右子树。 先序遍历实现代码：

如果二叉树为空，则无操作，直接返回。 如果二叉树非空，则执行以下操作： A、中序遍历左子树； B、访问根结点； C、中序遍历右子树。 中序遍历实现代码：

如果二叉树为空，则无操作，直接返回。 如果二叉树非空，则执行以下操作： A、后序遍历左子树； B、后序遍历右子树； C、访问根结点。 后序遍历实现代码：

定义遍历方式的枚举类型：

根据参数order选择遍历的方式，返回数组保存了二叉树遍历结点

线索化二叉树是将二叉树转换为双向链表的过程（将非线性的二叉树转换为线性的链表）。 二叉树的线索化能够反映某种二叉树的遍历次序（结点的先后访问次序）。 线索化二叉树的过程： 通过某种遍历方式遍历二叉树，根据遍历次序将二叉树结点依次存储到辅助队列中，最后将辅助队列中保存的结点依次出队并连接（连接时，原二叉树结点的m_left指针作为双向链表结点的m_prev指针，指向结点的前驱；原二叉树结点的m_right结点作为双向链表结点的m_next指针，指向结点的后继），成为双向链表。

增加层次遍历方式LevelOrder到遍历方式枚举类型中。

层次遍历算法： A、将根结点入队 B、访问队头元素指向的二叉树结点 C、将队头元素出队，队头元素的孩子入队 D、判断队列是否为空，如果非空，继续B；如果为空，结束。 层次遍历二叉树的实例如下：

将队列中的所有结点连接成为一个线性的双向链表

4、线索化二叉树的实现

线索化二叉树函数接口的设计： BTreeNode<T>* thread(BTTraversal order) A、根据参数order选择线索化的方式（先序、中序、后序、层次） B、返回值是线索化二叉树后指向链表首结点的指针 C、线索化二叉树后，原有的二叉树被破坏，二叉树的所有结点根据遍历次序组建为一个线性的双向链表，对应的二叉树应为空。 线索化二叉树的流程：

树是一种数据结构，它是由n(n≥1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。

当n=0时，称为空树;
对于任一棵非空树(n>0)，它具备以下性质:
树中有一个称为“根(Root)”的特殊结点，用r表示;
其余结点可分为m(m>0)个互不相交的有限集T1, T2，…，Tm,其
中每个集合本身又是一棵树，称为原来树的“子树(SubTree)”

1.3、树的一些基本术语

2.树的度:树的所有结点中最大的度数
4.父结点(Parent) :有子树的结点是其子树的根结点的父结点
5.子结点(Child) :若A结点是B结点的父结点，则称B结点是A结点的子结点;子结点也称孩子结点。
6.兄弟结点(Sibling) :具有同一父结点的各结点彼此是兄弟结点。
7. 路径和路径长度:从结点n1到n的路径为个结点序列n1, N2… ,∩k, n,是n+1的父结点。路径所包含边的个数为路径的长度。
9.祖先结点(Ancestor):沿树根到某- -结点路径_上的所有结点都是这个结点的祖先结点。
10.子孙结点(Descendant):某一结 点的子树中的所有结点是这个结点的子孙。
11.结点的层次(Level) :规定根结点在1层,其它任一结点的层数是其父结点的层数加1。
12.树的深度(Depth) :树中所有结点中的最大层次是这棵树的深度。

1.4.1、儿子兄弟表示法

树结构中，位于同一层的节点之间互为兄弟节点。
孩子兄弟表示法，采用的是链式存储结构，其存储树的实现思想是：从树的根节点开始，依次用链表存储各个节点的孩子节点和兄弟节点。即一个节点第一个指针指向第一个儿子，第二个指针指向另一个兄弟。

1.4.2、双亲表示法

双亲表示法采用顺序表存储普通树，其实现的核心思想是：顺序存储各个节点的同时，给各节点附加一个记录其父节点位置的变量。

1.4.3、孩子表示法

孩子表示法存储普通树采用的是 “顺序表+链表” 的组合结构，其存储过程是：从树的根节点开始，使用顺序表依次存储树中各个节点，需要注意的是，与双亲表示法不同，孩子表示法会给各个节点配备一个链表，用于存储各节点的孩子节点位于顺序表中的位置。

二叉树T:一个有穷的结点集合。
若不为空，则它是由根结点和称为其左子树TL和右子树Tp的
两个不相交的二叉树组成。
二叉树具体五种基本形态,二叉树的子树有左右顺序之分。

2.2.2、完美二叉树（满二叉树）

2.2.3、完全二叉树

有n个结点的二叉树，对树中结点按从上至下、从左到右顺序进行编号，
编号为i (1≤i≤n)结点与满二叉树中编号为i结点在二叉树中位置相同

一个二叉树第i层的最大结点数为: 2-1，i≥1。
深度为k的二叉树有最大结点总数为:2 k_1, k≥1。
对任何非空二叉树T,若n。表示叶结点的个数、n,是度为2的非叶结点个数，那么两者满足关系n。=n, +1。

2.4、顺序结构（缺点造成空间浪费）

完全二叉树:按从_上至下、从左到右顺序存储n个结 点的完全二叉树的结点父子关系:

结点(序号为i )的左孩子结点的序号是2i,(若2i<=n，否则没有左孩子) ;
结点(序号为i)的右孩子结点的序号是2i+1,(若2i+1<=n， 否则没有右孩子)

2.5、链式结构实现（有代码）

2.5.1、结构体定义

2.5.2、创建二叉树

2.5.3、销毁二叉树

2.5.3、先序遍历二叉树

遇到一个节点，就把它压栈，并访问这个节点，并去遍历它的左子树；
然后按其有指针再去前序遍历该节点的右子树。

2.5.3、中序遍历二叉树

遇到一个节点，就把它压栈，并去遍历它的左子树；
当左子树遍历结束后，从栈顶弹出这个节点并访问它；
然后按其有指针再去前序遍历该节点的右子树。

2.5.4、后序遍历二叉树

实现思路：先创建两个堆。
1.S1作为调整堆，开始先从根节点先右子树开始把节点压入栈，当最后一个节点的右子树为空时，将该节点出栈，并访问该节点的左子树；
2.当左子树为空时：继续出栈
3.当左子树不为空时：将该节点入栈
4.s2记录着入栈的顺序，将这里节点依次出栈即完成后序遍历。

队列实现：遍历从根节点开始，首先根节点入队，然后开始执行循环：节点出队、访问该节点、其左右儿子入队。

层次遍历基本过程：先根节点入队，然后：
1.从队列中取出一个元素；
2.访问该节点指向的节点；
3.若该元素所指的左、右孩子节点非空，则将其左、右孩子的指针顺序入队。

3.1、二叉搜索树的概念

二叉查找树（Binary Search Tree）：（二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

3.2、二叉搜索树的原理

二叉搜索树（BST）又称二叉查找树或二叉排序树。一棵二叉搜索树是以二叉树来组织的，可以使用一个链表数据结构来表示，其中每一个结点就是一个对象。一般地，除了key和位置数据之外，每个结点还包含属性lchild、rchild和parent，分别指向结点的左孩子、右孩子和双亲（父结点）。如果某个孩子结点或父结点不存在，则相应属性的值为空（NIL）。根结点是树中唯一父指针为NULL的结点，而叶子结点的孩子结点指针也为NULL。

3.3、二叉搜索树的性质

1.若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
2. 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
3.任意结点的左、右子树也分别为二叉搜索树

3.4、二叉搜索树的操作

3.4.1、二叉搜索树的数据结构

3.4.2、二叉搜索树的初始化

3.4.3、查找指定值并放回地址

3.4.4、查找树的最小值

3.4.5、查找树的最大值

3.4.6、二叉搜索树的值插入

3.4.7、二叉搜索树的删除

3.4.7、打印二叉搜索树

4、平衡二叉树（AVL树）

4.1平衡二叉树的概念

给定接点水为n的AVL树的最大高度为O（log2N）。

4.2、平衡二叉树的调整(注：方框内的数值为序号，并非数值)

(注：方框内的数值为序号，并非数值)

不平衡的“发现者”是2，“麻烦节点” 3在发现者的右子树的右边，因而叫RR插入，需要RR旋转（右单旋）

(注：方框内的数值为序号，并非数值)
“发现者”是2，“麻烦节点”5在发现者的左子树的左边，因而叫LL插入，需要LL旋转（左单旋）

(注：方框内的数值为序号，并非数值)
“发现者”是1，“麻烦节点”为6，6在左子树的右边，因而叫LR插入，需要LR旋转。

(注：方框内的数值为序号，并非数值)
“发现者”是5，“麻烦制造节点是”9，9在有子树的左边，因而叫RL插入，需要RL旋转

4.3、平衡二叉树的操作

4.3.1、平衡二叉树的数据结构

4.3.2、寻找平衡二叉树的值，返回地址

4.3.3、得到平衡二叉树的高度

4.3.4、平衡二叉树LL旋转

4.3.5、平衡二叉树RR旋转

4.3.6、平衡二叉树LR旋转

4.3.7、平衡二叉树RL旋转

4.3.8、平衡二叉树数据插入

4.3.9、平衡二叉树数据删除

4.3.10、平衡二叉树销毁

4.3.11、平衡二叉树完整代码

5、哈夫曼树（WPL）的实现

5.1、哈夫曼树的定义

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

5.2、哈夫曼树的术语

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

2、结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

5.2、哈夫曼树的特点

1.没有度为1的节点。
n个叶子节点的哈夫曼树共有2n-1个节点；
哈夫曼树的任意非叶节点的左右子树交换后仍然是哈夫曼树。

5.3、哈夫曼树用于编码

1.左右分支：0、1；
2.字符只在叶子节点上

5.5、哈夫曼树的编码

　　二叉树是一种很常见的数据结构，但要注意的是，二叉树并不是树的特殊情况，二叉树与树是两种不一样的数据结构。

　 　一、 二叉树的定义

　　二、二叉树为何不是特殊的树

　　三、二叉树的五种基本形态

　　四、二叉树相关术语

　　五、二叉树的主要性质（6个）

　　六、二叉树的存储结构（2种）

　　七、二叉树的遍历算法（4种）

　　八、二叉树的基本应用：二叉排序树、平衡二叉树、赫夫曼树及赫夫曼编码

　　如果你知道树的定义（有限个结点组成的具有层次关系的集合），那么就很好理解二叉树了。定义：二叉树是n(n≥0)个结点的有限集，二叉树是每个结点最多有两个子树的树结构，它由一个根结点及左子树和右子树组成。（这里的左子树和右子树也是二叉树）。

　　值得注意的是，二叉树和“度至多为2的有序树”几乎一样，但，二叉树不是树的特殊情形。具体分析如下

二、二叉树为何不是特殊的树

　　1、二叉树与无序树不同

　　二叉树的子树有左右之分，不能颠倒。无序树的子树无左右之分。

　　2、二叉树与有序树也不同（关键）

　　当有序树有两个子树时，确实可以看做一颗二叉树，但当只有一个子树时，就没有了左右之分，如图所示：

三、二叉树的五种基本状态

　　满二叉树：所有叶子结点全部集中在最后一层，这样的二叉树称为满二叉树。（注意：国内的定义是每一层的结点都达到最大值时才算是满二叉树；而国际定义为，不存在度为1的结点，即结点的度要么为2要么为0，这样的二叉树就称为满二叉树。这两种概念完全不同，既然在国内，我们就默认第一种定义就好）。

　　完全二叉树：如果将一颗深度为K的二叉树按从上到下、从左到右的顺序进行编号，如果各结点的编号与深度为K的满二叉树相同位置的编号完全对应，那么这就是一颗完全二叉树。如图所示：

　　二叉树的性质是基于它的结构而得来的，这些性质不必死记，使用到再查询或者自己根据二叉树结构进行推理即可。

　　性质1：非空二叉树的叶子结点数等于双分支结点数加1。

　　证明：设二叉树的叶子结点数为X，单分支结点数为Y，双分支结点数为Z。则总结点数=X+Y+Z，总分支数=Y+2Z。

　　　　　由于二叉树除了根结点外其他结点都有唯一的分支指向它，所以总分支数=总结点数-1.。

　　　　　结合三个方程：总分支数=总结点数-1，即Y+2Z = X+Y+Z-1。化简得到X = Z + 1。即叶子结点数等于双分支结点数加1。

　　证明：二叉树结点最多的情况即为满二叉树的情况，由于是满二叉树，每个结点都有两个孩子，所以下一层是上一层的2倍，构成了公比为2的等比数列，而第一层只有根结点，所以首项是1。所以二叉树的第i层上最多有2 ^i-1 个结点。

　　性质3：高度（或深度）为K的二叉树最多有2^k - 1个结点(K>=1）。

　　证明：本性质其实就是性质2中描述的等比数列的前项和的问题。

　　性质4：若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：

　　(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;  

　　(2) 若 2i>n，则该结点无左孩子，  否则，编号为 2i 的结点为其左孩子结点；

　　(3) 若 2i+1>n，则该结点无右孩子结点，  否则，编号为2i+1 的结点为其右孩子结点。

　　为了方便说明，我们使用下图树1作为案例树。

　　顺序存储是使用一个数组来存储二叉树，我们一般将二叉树按照性质4的做法，即从上到下且从左至右进行 1 至 n 的编号，然后编号与数组下标对应，按照编号依次将对应的结点信息存储数组中即可。

　　第一步：给二叉树编号：

 　　注意，编号5的位置是没有结点的，但是我们这样编号的目的是为了更好的应用性质4，而性质4描述的是完全二叉树，所以我们编号时要将普通二叉树看做完全二叉树来进行编号，所以即使编号5即使没有结点也需要进行编号。

　　第二步：按编号存储到数组BTree[]中

　　第三步：按照性质4的规律取元素

　　性质4主要是描述结点的编号和双亲编号或孩子编号之间的数学关系，即我们知道了一个结点的编号，那么它的双亲编号和孩子孩子我们都能计算得到并从数组中取出来。

　　结论：像编号5这种情况会占用存储空间，所以这种存储方式最适合用于存储完全二叉树，而存储一般的二叉树则会浪费大量空间。

　　根据二叉树的结构，我们使用下面的链式结点来存储一个二叉树结点。

　　所以树1对应的链式存储结构为：

　　根据二叉树的结构特点：一般二叉树由左子树、根结点和右子树组成。这三个元素：左子树（L）、根结点（N）、右子树（R）有6种中排列组合，即NLR、LNR、LRN、NRL、RNL、RLN。而从左往右和从右往左这种遍历顺序是对称结构的，采用一种顺序即可，所以二叉树按照三个元素的排列顺序遍历就形成了：NLR（先序遍历）、LNR（中序遍历）和LRN（后序遍历）。

　　ps:二叉树的这三种遍历要用递归的思想去理解。

　　先序遍历（NLR）：根左右

　　2）先序遍历左子树

　　3）先序遍历右子树

　　中序遍历（LNR）：左根右

　　1）中序遍历左子树

　　3）中序遍历右子树

　　后序遍历（LRN）：左右根

　　1）后序遍历左子树

　　2）后序遍历右子树

　　java实现（遍历树1）：

　　层次遍历比较简单，即按照从上往下、从左往右一层一层遍历即可。层次遍历是现实，如果遍历的是顺序存储（数组存储）的二叉树，由于存储的时候就是按照从上往下从左往右的顺序存储的，直接按顺序取出即可；如果是链式存储的二叉树，需要使用一个循环队列进行操作：先将根结点入队，当前结点是队头结点，将其出队并访问，如果当前结点的左结点不为空将左结点入队，如果当前结点的右结点不为空将其入队。所以出队顺序也是从左到右依次出队。

　　二叉排序树，又称二叉查找树（Binary Search Tree），亦称二叉搜索树。

　　二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

　　（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；

　　（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

　　（3）左、右子树也分别为二叉排序树；

　　ps：根据二叉排序树的定义，如果对二叉排序树进行中序遍历，那么遍历的结果就是一个递增的序列。

　　二叉排序树的主要功能就是查找。首先将需要查找的序列排序后存储到二叉排序树中，那么要查找的关键字要么在左子树，要么在根结点，要么在右子树，所以我们首先将要查找的关键字与根结点做比较，相等则查找成功。小于根结点则递归查找左子树，大于根结点则递归查找右子树，直到出现相等情况则查找成功，否则查找失败。（该查找过程与折半查找类似）

　　平衡二叉树又称为AVL树，是一种特殊的二叉排序树，即左右两个子树高度之差不超过1，并且左右两个子树都是平衡二叉树的二叉排序树称为平衡二叉树。

　　为什么要构造平衡二叉树呢？对于一般的二叉排序树，其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此而决定。由于AVL树的左右子树高度之差不超过1，其高度一般都良好地维持在O（log（n）），大大降低了操作的时间复杂度。

　　平衡二叉树的实现算法：关键在于左右子树的平衡。具体的算法有：红黑树、AVL算法、Treap、伸展树、SBT来实现。有兴趣的可以自行搜索，这里就不再描述。

3、赫夫曼树及赫夫曼编码

　　赫夫曼树又叫做最优二叉树，特点是带权路径长度最短。

　　路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。

　　结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

　　树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

　　如下图有4个叶子结点的二叉树：

　　2、赫夫曼树的构造

　　以上面的二叉树为例：首先有4个叶子结点a、b、c、d，权值分别为7、5、2、4。则：

　　3、赫夫曼树的特点

　　1）权值越大的结点离根结点越近。

　　2）树中没有度为1的结点。这类树又称为正则（严格）二叉树。

　　4、赫夫曼树的应用：赫夫曼编码

　　赫夫曼编码是一种编码方式。例如我们需要发送右A、B、C、D这4个字符组成的一些文字，如果分别用00,01,10,11来代表要传送的A、B、C、D。则需要发送"ADA"就编码为：001100。

　　我们希望编码的长度能够越短越好，上面的编码方式长度显然是与字符个数成正比的，不能满足需求，所以赫夫曼想到了设置不同的编码长度来表达不同字符，那么让出现概率越高的字符设置编码长度越短即可。假设A、B、C、D出现的概率分别为0.4、0.3、0.2、0.1。那么A、B、C、D的编码就可以分别用0、00、01、1来表示。那么ADA的编码就是“010”，但"CA"的编码也是“010”，所以我们在设置不同长度的编码时需要使用前缀编码（即任一编码都不是其他编码的前缀，这样就不会产生歧义了）。所以A、B、C、D的编码修改为：0、10、110、111即可。

　　赫夫曼编码就是长度可变（编码长度最短）的前缀编码。其实，赫夫曼编码的构造就是赫夫曼树的构造过程：即字符相当于叶子结点；字符出现的概率相当于结点的权值；由于构造的赫夫曼树权值越大的结点离根结点越近，所以字符出现概率越大的字符离根结点越近，路径也就越短。

　　所以，A、B、C、D（0.4、0.3、0.2、0.1）构造的赫夫曼树过程如下：

　　1）构造赫夫曼树。

　　2）约定左分支表示0，右分支表示1。

　　3）从根结点到字符结点的路径组成的编码就是该字符的赫夫曼编码。