03、树

树的数据结构

二叉树的数据结构

二叉树的建立

• 利用递归原理
• 利用遍历的原理打印变插入（要利用扩展二叉树）

  扩展二叉树：将二叉树的每个节点的空指针引出一个虚结点，其值为一特定值，比如“#”，我们将这种处理后的二叉树为原二叉树的扩展二叉树。

线索二叉树

• 定义：当某个结点的左子树或者右子树不存在时，将它们的指针根据某种遍历方式，存放前驱和后继。
• 指向前驱和后继的指针称为线索，加上线索的二叉树链表称为线索链表，相应的二叉树称为线索二叉树
• 线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程。

  树、森林、二叉树的转换

  树->二叉树

1. 加线。所有兄弟结点之间加一条线
2. 去线。每个节点只保存第一个孩子结点的连线，删除与其他孩子结点之间的连线。

3. 调整。第一个孩子是左孩子，兄弟变为该孩子的右孩子。

   森林->二叉树

4. 把每棵树转换为二叉树

5. 第一棵树不动，从第二棵树开始，依次把后一棵树的根节点作为前一棵树的右孩子

   二叉树->树

6. 加线。与左孩子的所有右孩子结点连线

7. 去线。删除原来所有结点与其右孩子结点的连线。

8. 层次调整

   二叉树->森林

9. 从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。

10. 再将每棵树分离后的二叉树转换为树

    树与森林的遍历

    树的遍历

11. 先根遍历，类似前序遍历

12. 后跟遍历，类似后序遍历

    森林的遍历

13. 前序遍历：先访问森林中第一棵树的根节点，然后先根遍历每棵子树，再依次用同样的方式遍历剩余的树。

14. 后序遍历：先后根遍历每棵子树，然后访问根节点，再依次用同样的方式遍历剩余的树。

    哈夫曼树及其应用

• 先转为叶子结点带权的二叉树
• 哈夫曼树：带权路径长度WPL最小的二叉树称作哈夫曼树。

  WPL的长度=所有叶子节点权*到根的距离的和

构造哈夫曼树
找出最小的组成二叉树，与剩下的最小的比，如果小于作为左子树，大于作为右子树，组成二叉树。直到所有的结点都到了二叉树的叶子节点上。

哈夫曼编码

作用：用于压缩传送数据。

前缀编码：若要设计出长度不等的编码，则必须是任一字符的编码都不是另一个字符编码的前缀。