愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

数据结构总结——树、二叉树、哈夫曼树

一、树的几个概念


1、:儿子结点的个数
2、叶结点:度=0的结点
3、分支结点:度≠0的结点
4、内部结点:除根结点外的分支结点
5、祖先:父结点和自身(不包含自身的叫做真祖先
6、子孙:子结点和自身(不包含自身的叫做真结点
7、结点的高度:结点到各个叶结点的最长路径的长度

二、二叉树

二叉树的基本概念

1、二叉树中,每个结点至多有两个儿子结点,而且区分左儿子和右儿子
2、有序树只有一个儿子时,无需区分左右次序,而二叉树即使只有一个儿子也有左右之分
3、二叉树不是树的特殊情形
4、完全二叉树:除了最后一层,其他每层的结点都满了,最后一层可以有右边的结点没满
5、满二叉树:每一层的结点都满了,近似满二叉树:没有左儿子,就一定没有右儿子

二叉树的重要性质


1、高度为h的二叉树至少有h+1个结点,至多有2^(h+1) - 1个结点
2、含有n个结点的向下取整(logn) <= 二叉树高度 <= n-1
3、含有n个结点的二叉树共有C(2n, n) / (n+1)种形态
4、对任意的非空二叉树T,如果叶结点的个数为n0,而其度为2的结点数为n2,则:n0 = n2 + 1
5、要确定一个二叉树,必须要有中序遍历序列

三、哈夫曼树

1、概念:给定n个权值作为n个叶子结点,构造一颗二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树
2、基本术语:
1)结点的权:给结点的一个赋予某种含义的数值
2)带权路径长度:根结点到该结点的路径长度 × 结点的权
3)树的带权路径长度:即WPL,为根结点的带权路径长度之和
3、构造哈夫曼树:

4、哈夫曼编码:

由于哈夫曼树具有离根结点近的权值大,离根结点远的权值小的特点。而在通信中,我们希望能够尽量缩短传送的二进制串长度,对于这种情况下,采用何种编码就成为了一个重要的问题。而我们只要让高频字符用短编码,低频字符用较长编码,就能实现整体编码长度最优,而哈弗曼树刚好适应于这种场景,所以产生了哈夫曼编码

1)首先假设我们要传送“ADDDAAABBCCCDDDA”,我们可以先统计词频,如下:A(5)、B(2)、C(3)、D(6)
2)我们把词频作为权值,构造哈夫曼树得:

3)可以对每个叶子结点进行编码,编码规则为左边的路径权值为1,右边的路径权值为0,如此构造得:

  • D -> 6:0
  • A -> 5:10
  • B -> 2:111
  • C -> 3:110

4)所以,串就可以以上述编码发送:

1000010101011111111011011000010