• 小知识，大挑战！本文正在参与“程序员必备小知识”创作活动。

二叉排序树

定义

左子树节点<根节点值<右子树节点，对于二叉排序树进行中序遍历，可以得到一个递增序列,下图中序遍历序列为:1 2 3 4 6 8

二叉排序树的删除

1)若删除节点z是叶节点，则直接删除
2)若z只有一颗左子树或右子树，则让z的子树代替z的位置(用子女代替)
3)若z有左右子树，找第一个子女来填补

2图

3图

二叉排序树的平均查找效率

上图的查找效率为 ASL=(1+2*2+3*4+4*3)/10=2.9   
即每层节点总数乘以所在层数求和取平均

平衡二叉树

任意节点的`左右子树高度差的绝对值不超过1`，这样的二叉树称为'平衡二叉树';
左右子树的高度差称为节点的'平衡因子'

• –>平衡 如下
• –>不平衡 如下

※平衡二叉树的插入

下图为RR右单旋转

下图为LL左单旋转

下图为 LR先左后右 旋转

下图为 RL先右后左 旋转

哈夫曼树

树中节点常常被赋予一个表示某种意义的数值称为’权’; 树中所有叶节点的带权路径长度之和称为该树的’带权路径长度–>WPL’

下图带权路径计算

• (a) WPL=7×2+5×2+2×2+4×2=36
• (b) WPL = 7×3+5×3+4×2+1×2=46
• (c)WPL=7×1+5×2+2×3+4×3=35

哈夫曼树的构造

• 森林中选择出两颗结点的’权值最小’的二叉树
• 合并两颗二叉树，增加一个新的节点作为’新的二叉树的根’，权值为’左右孩子的权值之和’

哈夫曼编码

若没有一个编码是另一个编码的’前缀’,则称这样的编码为’前缀编码’