线性表
栈和队列
字符串
数组和广义表
树和二叉树
哈夫曼树
哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。
所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层，叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=(W1L1+W2L2+W3L3+…+WnLn)，N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明哈夫曼树的WPL是最小的。
构造方法和思路
1.根据给定的n个权值{w1,w2,…,wn}
构成二叉树集合F={T1,T2,…,Tn},
其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树为空.
2.在集合F中 选取两棵根结点权值最小的树 作为左右子树构造一棵新的二叉树, 且置新的二叉树的根结点的权值为左右子树根结点的权值之和
3.在集合F中删除这两棵树,同时将新的二叉树加入F中.
4.重复2、3,直到集合F只含有一棵树为止.(得到哈夫曼树)
