一、树的几个概念
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