二叉树

定义

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

二叉排序树的删除

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

二叉排序树 - 图2
二叉排序树 - 图3

二叉树的查找效率

二叉排序树 - 图4
上图的查找效率为 ASL=(1+22+34+4*3)/10=2.9

即每层节点总数乘以所在层数求和取平均

平衡二叉树

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

平衡二叉树的插入

下图为RR右单旋转
二叉排序树 - 图6
下图为LL左单旋转
二叉排序树 - 图7
下图为 LR先左后右 旋转
二叉排序树 - 图8
下图为 RL先右后左 旋转
二叉排序树 - 图9

哈弗曼树

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

带全路径计算

二叉排序树 - 图10

  • WPL=7×2+5×2+2×2+4×2=36
  • WPL = 7×3+5×3+4×2+1×2=46

  • WPL=7×1+5×2+2×3+4×3=35

    哈弗曼树的构造

  • 森林中选择出两颗结点的’权值最小’的二叉树

  • 合并两颗二叉树，增加一个新的节点作为’新的二叉树的根’，权值为’左右孩子的权值之和’

    哈夫曼编码

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

参考：https://juejin.cn/post/7016130383125151780