二叉树是n(n≥0)个节点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和俩颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
(1)每个结点最多俩颗子树,所以二叉树中不存在度大于2的结点。没有子树或者有一颗子树都是可以的。
(2)左子树和右子树是有顺序的,次序不能任意颠倒。(人的的左右手)
(3)即使树中某节点只有一颗子树,也要区分是左子树还是右子树。
(1)斜树(左斜树,右斜树):所有的节点都是只有右(左)子树。
(2)满二叉树:节在一颗二叉树中,如果所有的分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。
(3)完全二叉树:编号顺序没有断。
极端情况下深度为K的右斜树,它只有K课结点,却需要分配 2的(k-1)次方-1个存储单元,太浪费。所以顺序存储结构一般用于完全二叉树。
树的路径长度:从树中一个结点到另一个节点之间的分支构成俩个结点之间的路径,路径上的分支数目称作路径长度。树的路径长度就是从树根到每一结点的路径长度之和。
赫夫曼树:带权路径长度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
此时,我们对这六个字母用其从树根到叶子所经过路径的 0 或 1 来编码,可以得 到如表 6-12-3 所示这样的定义。
也就是说我们的数据被压缩的。解码的时候逆推就行,发送方和接收方必须要约定好同样的赫夫曼编码规则。