数据结构之树(二)二叉树、赫夫曼树的定义与特点

xiaoxiao2021-03-01  21

1、二叉树的定义

     二叉树是n(n≥0)个节点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和俩颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

2、二叉树的特点:

(1)每个结点最多俩颗子树,所以二叉树中不存在度大于2的结点。没有子树或者有一颗子树都是可以的。

(2)左子树和右子树是有顺序的,次序不能任意颠倒。(人的的左右手)

(3)即使树中某节点只有一颗子树,也要区分是左子树还是右子树。

 

3、一些特殊的二叉树结构

(1)斜树(左斜树,右斜树):所有的节点都是只有右(左)子树。

(2)满二叉树:节在一颗二叉树中,如果所有的分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。

 

(3)完全二叉树:编号顺序没有断。

 

4、二叉树的顺序存储结构:

      极端情况下深度为K的右斜树,它只有K课结点,却需要分配 2的(k-1)次方-1个存储单元,太浪费。所以顺序存储结构一般用于完全二叉树。

 

5、二叉树的链式存储结构:

6、赫夫曼树

树的路径长度:从树中一个结点到另一个节点之间的分支构成俩个结点之间的路径,路径上的分支数目称作路径长度。树的路径长度就是从树根到每一结点的路径长度之和。

赫夫曼树:带权路径长度WPL最小的二叉树称作赫夫曼树。

    二叉树a的路径长度:1+1+2+2+3+3+4+4=20                      二叉树b的路径长度:1+2+3+3+2+1+2+2=16

  二叉树a的带权路径长度WPL=5*1+15*2+40*3+30*4+10*4=315     二叉树a的带权路径长度WPL=5*3+15*3+40*2+30*2+10*2=220

7、赫夫曼编码:压缩传输数据

     此时,我们对这六个字母用其从树根到叶子所经过路径的 0 或 1 来编码,可以得 到如表 6-12-3 所示这样的定义。

     也就是说我们的数据被压缩的。解码的时候逆推就行,发送方和接收方必须要约定好同样的赫夫曼编码规则。

 

 

转载请注明原文地址: https://www.6miu.com/read-3850325.html

最新回复(0)