c语言二叉树链式存储基本操作（数据结构-哈夫曼树的性质）

c语言二叉树链式存储基本操作（数据结构-哈夫曼树的性质）哈夫曼树的定义 其中n表示叶子结点的数目， w i 和 l i 分别表示叶子结点k i 的权值和树根结点到k i 之间的路径长度。 在许多应用中，常常将树中的结点赋上一个有着某种实际意义的实数，我们称此实数为该结点的权（weight)。结点的带权路径长度（weighted path length，WPL）规定为从树根结点到该结点之间的路径长度与该结点上权的乘积。 （3）树的带权路径长度 树的带权路径长度定义为树中所有叶子结点的带权路径长度之和，通常记为：

基本概念

（1）路径和路径长度

若在一棵树中存在着一个结点序列k₁、k₂、…、k_j，使得k_i是k_{i 1}的双亲（1≤i<j），则称此结点序列是从k₁到k_j的路径（Path）。因树中每个结点只有一个双亲结点，所以它也是这两个结点之间的唯一路径。从k₁到k_j所经过的分支数称为这两点之间的路径长度（path length），它等于路径上的结点数减1。如在图6-9(a)所示的二叉树中，从树根结点A到叶子结点G的路径为结点序列A、E、F、G，路径长度为3。

（2）结点的权和带权路径长度

在许多应用中，常常将树中的结点赋上一个有着某种实际意义的实数，我们称此实数为该结点的权（weight)。结点的带权路径长度（weighted path length，WPL）规定为从树根结点到该结点之间的路径长度与该结点上权的乘积。

（3）树的带权路径长度

树的带权路径长度定义为树中所有叶子结点的带权路径长度之和，通常记为：

其中n表示叶子结点的数目， w _i 和 l _i 分别表示叶子结点k _i 的权值和树根结点到k _i 之间的路径长度。

哈夫曼树的定义

哈夫曼树（huffman tree）又称作最优二叉树。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。因为构造这种树的算法最早是由哈夫曼于1952年提出的，所以被称之为哈夫曼树。

例如，有四个叶子结点a、b、c、d，分别带权为9、4、5、2，由它们构成的三棵不同的二叉树（当然还有其他许多种）分别如图6-11(a)、6-11(a)和6-11(c)所示。

由四个叶子结点构成的三棵不同的带权二叉树

这三棵二叉树的带权路径长度WPL分别为：

(a) WPL=9×2 4×2 5×2 2×2=40

(b) WPL=4×1 2×2 5×3 9×3=50

(c) WPL=9×1 5×2 4×3 2×3=37

其中图6-11(c)树的WPL最小，此树就是哈夫曼树。

从上面可以看出，根据n个带权叶子结点所构成的二叉树中，满二叉树或完全二叉树不一定是最优二叉树。权值越大的结点离树根越近（即路径长度越短）的二叉树才是最优二叉树。

哈夫曼树的性质

1.除叶结点外，每个结点的度数都为2

2.叶结点数比非叶结点数多1

例：哈夫曼树有10个叶子结点，该树共有19个结点