二叉查找树&哈夫曼树
查找树的删除
- 叶子节点
- 直接删除，父节点对应置为空
- 有一个子节点
- 将子节点替代当前节点
- 有两个子节点
- 用左节点（用前驱节点）
- 左节点的右节点链接被删除的右子树，左节点的右子树的根当成新节点插入
- 左节点作为替代节点，右节点的根直接做插入
- 用右节点（用后驱节点）
- 右节点的左节点链接被删除的左子树，右节点的右子树的根当成新节点插入
- 右节点作为替代节点，左节点的根直接做插入
- 用左节点（用前驱节点）
哈夫曼树
- 最优二叉树
- 带权路径最小
- 一堆数据要构成哈夫曼树，所有的数据应当是叶子节点
- WPL（带权路径长度）= 节点全值*路径长度 之和
- 权值越大的点应该越靠近根，权值越小的点应该越靠近底
- 如何构建哈夫曼树
- 带权路径最小
- 同层当中小权值节点应当放在左边
- 优先级队列/堆（小数在前）
- 每次取队头两个节点组成一个和值节点从队尾放入
- 和值过后，如果队空，和值就是这棵树的根
6.哈夫曼树的插入和删除