跳到主要内容

树

基础概念​

树是n个节点的有限集合（n>=0）,当 n = 0 时称为空树，在任一棵非空树中，有且仅有一个根节点。其余节点可分为 m(m>=0)个互不相交的有限子集 T1,T2,...,Tm，其中，每个 Ti 都是一棵树，并且称为根节点的子树。

树的基本概念如下：

  • 双亲、孩子和兄弟。结点的子树的根称为该结点的孩子；相应地，该结点称为其子结点双亲；具有相同双亲的结点互为兄弟。
  • 结点的度。一个结点的子树的个数称为该结点的度。例如 A 的度是 3，B 的度是 2，C 的度是 0，D的度是 1。（相当于只算了出度，出度和入度是图中的概念）
  • 叶子结点：叶子结点也称为终端结点，指度为 0 的节点，例如 E、F、C、G 都是叶子节点
  • 内部节点：度不为零的节点，也称为分支结点或非终端结点。除根节点外，分支结点也称为内部节点。例如 B、D 都是内部结点。
  • 结点的层次。根为第一层，根的孩子为第二层，依次类推，若某结点在第 i 层，则其孩子结点在 i+1 层。例如，A 在第 1 层，B、C、D 在第 2 层，E、F、G 在第 3 层。
  • 树的高度。一棵树的最大层数记为树的高度（深度）。例如，图中所示树的高度为 3。
  • 有序（无序）树。若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树，否则称为无序树。

二叉树​

二叉树是 n 个结点的有限集合，它或者是空树，或者是由一个根结点及 两颗互不相交的且分别称为左右子树的二叉树组成。

两种特殊的二叉树如下图所示：

  • 满二叉树：除了叶子结点，其余结点的度都是 2 。
  • 完全二叉树：从左到右，元素是不间断的。

二叉树有一些性质如下，要求掌握，在实际考试中可以使用特殊值法验证。

  1. 二叉树 第 i 层（i>=1）上至少有 2i−12^{i-1}个结点
  2. 深度为 k 的二叉树至多有 2k−12^k-1个结点（k>=1)。（等比数列求和）
  3. 对任何一颗二叉树，若其 终端结点数为 n0n_0,度为 2 的结点树为 n2n_2，则 n0=n2+1n_0 = n_2+1
提示

上面的公式可以画一个简单的二叉树使用特殊值法快速验证，也可以证明如下： 设一棵二叉树上 叶子结点树为 n0n_0,单分支结点数为 n1n_1，双分支结点数为 n2n_2，则总结点数为 n1+n2+n0n_1+n_2+n_0，在一颗二叉树中，所有结点的分支数（即度数）应该等于单分支结点数加上双分支结点数的2倍，即总的分支数=n1+2n2n_1+2n_2。由于二叉树中除根结点以外，每个结点都有唯一的一个分支指向它，因此二叉树中：总的分支数 = 总结点数 - 1。

所以 n1+2n2=n1+n2+n0−1n_1+2n_2= n_1+n_2+n_0-1 , 得到 n0=n2+1n_0=n_2+1。

  1. 具有 n个结点的完全二叉树的深度为 ⌊log2n⌋+1\lfloor log_2n \rfloor +1 (向下取整)

二叉树的存储​

顺序存储​

就是用一组 连续的存储单元存储二叉树中的节点，按照 从上到下、从左到右的顺序依次存储每个节点。

对于 深度为k的完全二叉树，除第 k 层外，其余每层中节点数都是上一层的 2 倍，由此，从一个节点的编号可以推测其双亲、左孩子和右孩子节点的编号。假设有 编号为 i 的节点，则有：

  • 若 i = 1，则该节点为根节点，无双亲；若 i >1,则该节点的双亲节点为 [i/2]。
  • 若 2i<=n ,则该节点的左孩子编号为 2i,否则无左孩子
  • 若 2i+1<=n,则该节点的右孩子编号为 2i+1,否则无右孩子。

显然，顺序存储结构对于完全二叉树而言既简单又节省空间，而对于一般二叉树则不适用。因为在顺序存储结构中，以节点在存储单元中的位置来表示节点之间的关系，那么对于一般的二叉树来说，也必须按照完全二叉树的形式存储，也就是要 添上一些实际上并不存在的“虚节点“，这将造成空间的浪费。

链式存储​

由于二叉树中节点包含有数据元素、左子树根、右子树根及双亲等信息，因此可以用 三叉链表或二叉链表（即一个节点含有三个指针或两个指针）来存储二叉树，链表的头指针指向二叉树的根节点。

二叉树的遍历​

一棵非空的二叉树由根节点、左子树、右子树三部分组成，遍历这三部分，也就遍历了整棵二叉树。这三部分遍历的基本顺序是先左子树后右子树，但根节点顺序可变，以根节点访问的顺序为准有以下三种遍历方式：

  • 先序：（前序）遍历，根左右
  • 中序：左根右
  • 后序：左右根

示例：前序：12457836 ；中序：42785136；后序：48752631

层次遍历：按层次，从上到下，从左到右。

反向构造二叉树​

仅仅有前序和后序是无法构造二叉树的，必须配合中序遍历才能反向构造出二叉树。

构造时，前序和后续遍历可以确定根节点，中序遍历用来确定根节点的左子树节点和右子树节点，而后按此方法进行递归，直至得出结果。

线索二叉树​

引入线索二叉树是为了保存 二叉树遍历时某节点的前驱节点和后继节点的信息，二叉树的链式存储只能获取到某节点的左孩子和右孩子节点，无法获取其遍历时的前驱和后继节点，因此可以在 链式存储中再增加两个指针域，使其分别指向前驱和后继节点，但这样太浪费存储空间，考虑下述实现方法：：

  • 若 n个节点的二叉树使用二叉链表存储，则必然有 n+1 个空指针域，利用这些空指针域来存放节点的前驱和后继节点信息，为此，需要增加两个标记，以区分指针域存放的到底是孩子节点还是遍历节点。

  • 若二叉树的二叉链表采用上述结构，则称为 线索链表，其中指向前驱、后继节点的指针称为线索，加上线索的二叉树称为线索二叉树。

  • ltag = 1 时 lchild 域指向节点的直接前驱动，否则指向节点的左孩子；rtag = 1 时 rchild 域指向节点的直接后继。

为什么n个节点的二叉树使用二叉链表存储，则必然有 n+1 个空指针域？

n 个节点使用二叉链表存储一共有 2n 个指针域，n 个节点所以用了 n 个，因为每一个节点都有一个指针域指向它（除了根节点），所以 2n-(n-1) = n+1。

最优二叉树（哈夫曼树）​

最优二叉树又称为哈夫曼树，是一类带权路径长度最短的树，相关概念如下：

  • 路径: 树中一个结点到另一个结点之间的通路。
  • 结点的路径长度：路径上的分支数目
  • 树的路径长度：根节点到达每一个叶子节点之间的路径长度之和
  • 权：节点代表的值
  • 节点的带权路径长度：该节点到根节点之间的路径长度乘以该节点的权值。
  • 树的带权路径长度（树的代价）：树的所有叶子节点的带权路径长度之和

哈夫曼树的求法: 给出一组权值，将其中 两个最小的权值作为叶子节点，其和作为父节点，组成二叉树，而后删除这两个叶子节点权值，并将父节点的值添加到改组权值中。重复进行上述步骤，直至所有权值都被使用完。

通过上述步骤求出的树的带权路径长度时最小的

若需要构造哈夫曼树(要保证左节点值小于右节点的值，才是标准的哈夫曼树），将标准哈夫曼树的左分支设为0，右分支设为1，写出每个叶子节点的编码，会发现，哈夫曼编码的前缀不同，因此不会混淆，同时也是最优编码

查找二叉树​

查找（排序）二叉树上的每个节点都存储一个值，且 每个节点的所有左孩子节点值都小于父节点值，而所有右孩子节点值都大于父节点值，是一个有规律排列的二叉树，这种数据结构可以方便查找、插入等数据操作。

二叉排序树的查找效率取决于二叉排序树的深度，对于节点个数相同的二叉排序树。平衡二叉树的深度最小，而 单枝树的深度是最大的，故效率最差。

平衡二叉树​

平衡二叉树又称为 AVL 树,它或者是一棵空树，或者是具有下列性质的二叉树。

  • 它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过 1。
  • 若将二叉树节点的 平衡因子（Balance Factor，BF）定义为该节点的左子树高度减去其右子树的高度，则平衡二叉树上的所有节点的平衡因子只可能是 -1 、0、1 。只要树上有一个节点的平衡因子的绝对值大于 1， 则该二叉树就是不平衡的。