树的相关知识
前述：一点学习的笔记。
无序树和有序树的区别
- 如果能将树中的结点看成从左至右是有次序的，且不能改变，就称其为有序树，否则为无序树
什么是森林
- 在结点不为0的树中，每个结点的子树集合就是该结点的森林
完全二叉树和满二叉树的区别
- 满二叉树：所有分支结点都有左子树和右子树，叶子结点只能在最后一层
- 完全二叉树：结点按层序依次编号，树中结点位置与同样深度的满二叉树中结点位置完全相同
- 两者联系：满二叉树一定是完全二叉树，完全二叉树并不一定是满二叉树
二叉树的存储结构
- 满二叉树和完全二叉树用数组存储
- 一般二叉树：二叉链表(lchild,data,rchild)
- 三叉链表(lchild,data,rchild,parent)
- 线索链表(lflag,lchild,data,rchild,rflag)
二叉树的遍历
- 前序：从根结点，先左后右，依次返回双亲结点
- 中序：从根结点的左子树开始，返回根结点，再到右子树
- 后序：从左子树的叶子结点开始，到右子树的叶子结点，最后返回根结点
- 层序：逐层遍历
树、森林、二叉树的转换
- 树到二叉树：用线连接所有兄弟结点，保留结点与其长子(左子树根结点)的连线，其余连线删去，调整位置
- 森林到二叉树：先把森林变为二叉树，再连接二叉树的根结点
- 二叉树到森林：若结点x是其双亲结点y的左孩子，则将结点x的右孩子，右孙子…与y连接起来，再去掉所有双亲与右孩子的连线
什么是哈夫曼树
- 带权路径最短的二叉树
哈夫曼树所涉及到的基本概念
- 结点的路径长度：根结点到该结点的路径上的连接数
- 树的路径长度：每个叶子结点的路径长度
- 结点带权路径长度：结点权值与路径长度的乘积
- 树的带权长度路径：(WPL)树中所有叶子结点的带权路径长度
怎样构建哈夫曼树
- 先对所给结点进行大小排序
- 选出权值最小的两个，按照小左大右放置
- 增加一个新的结点N1作为二叉树的根结点，其权值为两孩子结点之和
- 从剩余结点中选出最小权值的结点，与新增根结点N1进行对比，按小左大右的方式放置，使该结点成为N1的兄弟结点
- 重复第三步及以下操作，至最大权值结点成为最终二叉树的根结点
哈夫曼编码的作用
- 有效地压缩数据(20%~90%,依赖于数据特性)
如何构建哈夫曼编码
- 先假设S为进行编码的字符集合，F为字符使用频度集合
- 以F集合为权值构建一颗哈夫曼树
- si作为以fi为权值的叶结点的名字
- 从哈夫曼树的根结点出发，寻找去到叶结点si的一条路径，此间每经过一个左分支记一个’0’，每通过一个右分支记一个’1’，所得到的0/1序列就是si的哈夫曼编码
