二叉树

8.1 为什么使用二叉树

• 因为它结合了数组和链表的优点，查找的速度和数组一样快，增删的速度和链表一样快。

8.1.1 在有序数组中插入数据项太慢

• 查找数据项使用二分法，需要O(logN)时间
• 插入或者删除需要移动一半的数据项（N/2次移动）

8.1.2 在链表中查找太慢

• 链表中插入和删除极快，时间复杂度为O(1)
• 链表中查找要从头开始遍历，并且逐个比较，费时为O(N)
• 链表不支持随机访问

8.1.3 用树解决问题

要是能有一种数据结构，既能像链表那样快速的插入和删除，又能像有序数组那样快速查找，那样就好了。树实现了这些特点，成为最有意思的数据结构之一。

8.1.4 树是什么

• 本章着重讲解的是一种特殊的的树——二叉树
• 先从广义上讨论一下树：树由边连接的节点而构成
  1. 节点：代表实体，或者说是对象
  2. 边：代表路径，或者说是引用
• 二叉树：每个节点最多有两个子节点

8.2 树的术语

8.2.1 路径

• 从一个节点走到另一个节点，所经过的节点的顺序排列就称为“路径”。

8.2.2 根

• 树顶端的节点称为“根”
• 从根到任意节点有且仅有一条路径

8.2.3 父节点

• 每个节点向上只有一条路径

8.2.4 子节点

• 每个节点向下可能有多条路径

8.2.5 叶节点

• 没有子节点的称为叶节点

8.2.6 子树

• 一个节点所有的后代

8.2.7 访问

• 查看节点的数据

8.2.8 遍历

• 遵循某种特定的顺序访问树中所有节点，例如升序

8.2.9 层

• 根节点是第0层

8.2.10 关键字

• 对象中通常会有一个数据域被指定为关键字值
• 将关键字显示在树节点的圆圈中

8.2.11 二叉树

• 最多只有两个子节点的树称为二叉树
• 二叉搜索树：左子节点的值小于父节点，右子节点的值大于或等于父节点

8.3 一个类比

• 计算机系统中，人们常遇到的树是分级文件结构
• 目录对应着子节点，文件对应着叶节点

8.4 二叉搜索树如何工作

• 对于一个给定关键字的节点，在一颗普通的二叉树中如何插入，删除，遍历。

8.4.1 BinaryTree专题applet

• 非平衡树
  1. 大部分节点在根的一边
  2. 它的个别子树依然可能是非平衡树
  3. 非平衡树源自于有序的插入

8.4.2 用Java代码表示树

• 可以用数组或者链表实现

8.5 查找节点

• 根据关键值查找节点是树的主要操作中最简单的，所以本章从查找开始学习。

8.5.1 使用专题applet查找一个节点

8.5.2 查找节点的Java代码

8.5.3 树的效率

8.6 插入一个节点

• 要插入节点，必须先找到插入的地方，这很像要找一个不存在的节点的过程。

8.6.1 使用专题applet插入一个节点

8.6.2 插入一个节点的Java代码

• 记录目标的父节点：parent

8.7 遍历树

• 遍历树的意思是根据一种特定顺序访问树的每一个节点。

8.7.1 中序遍历

• 中序遍历二叉搜索树会使所有的节点按关键字值升序被访问到

8.7.2 遍历的Java代码

8.7.3 遍历一颗三节点树

8.7.4 用专题applet遍历

8.7.5 前序和后序遍历

• 前缀表达式
• 后缀表达式

8.8 查找最大值和最小值

顺便说一下，在二叉搜索树中得到最大值和最小值是轻而易举的事情。

• 最小值：从根开始，往左走，找到一个没有左子节点的节点。
• 最大值：从根开始，往右走，找到一个没有右子节点的节点。

8.9 删除节点

• 删除节点是二叉搜索树常用的一般操作中最复杂的。

8.9.1 情况1：删除没有子节点的节点

image.png

• 将指向该节点的引用改为null

8.9.2 情况2：删除有一个子节点的节点

image.png

• 父节点直接指向子树的根
• 注意应用引用使得移动整棵子树非常容易，实际上，它们只是概念上的移动，并没有真实的移动。

8.9.3 情况3：删除有两个子节点的节点

1. 对于有两个子节点的简单情况：用中序后继替代

   
   image.png

2. 后继是右子节点：右子节点子树上移

   
   image.png

3. 后继是右子节点的左子后代

   
   image.png

8.10 二叉树的效率

• 树的大部分操作都需要从上到下一层一层地查找某个节点
• 树对所有常用的数据存储操作都有很高的效率
• 遍历不如其他操作快

8.11 用数组表示树

• 按从左到右的顺序存储树的每一层，下标为0的节点是根
• 树中的每个位置，无论是否存在节点，都对应数组中的一个位置
• 大多数情况下用数组表示树不是很有效率

8.12 重复关键字

• 有重复关键字的节点都插到与它关键字相同的节点的右子节点

8.13 完整的tree.java程序

8.14 哈夫曼（Huffman）编码

• 二叉树并不全是搜索树，很多二叉树用于其他的情况

8.14.1 字符编码

• 计算机里每个字符在没有压缩的文本文件中由一个字节（ASCII码），或两个字节（Unicode码）
• 有很多压缩数据的方法。对文本来说，最常用的方法是减少表示最常用字符的位数量
• 每个代码都不能是其他代码的前缀

8.14.2 用哈夫曼树解码

• 哈夫曼树用于压缩文本
• 从根开始，如果遇到0就向左走，遇到1就向右走

8.14.3 创建哈夫曼树

8.14.4 信息编码

8.14.5 创建哈夫曼编码