给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
在构造哈夫曼树的过程中不能保证一定是完全树或是平衡树,而对于哈夫曼树左右孩子结点的权值之和构造其父结点,因此父结点权值一定大于其左右孩子结点,
权值相同的结点可能会因为构造的形态不同,导致构造结果不一样,权值不一样。
二叉树存在一个特定度为0的结点(叶子结点)记作n0,度为2的结点记作n2,满足n2+1= n0。哈弗曼树只有度为0和度为2的结点,二者必定差值为1,因此,结点总数即二者之和n0+n2=(n2+1)+n2=2n2+1时,必定为奇数。