【数据结构】树

发表于 | 分类于 |

数据结构笔记-树部分。

树

树的定义

树（Tree）是一种抽象数据类型，它由节点（Nodes）组成，这些节点通过边（Edges）连接起来，具有以下特点：

  • 树有一个特殊的节点称为根节点（Root），它没有前驱节点。
  • 除了根节点外，每个节点都有且仅有一个前驱节点，称为父节点（Parent）。
  • 每个节点可以有零个或多个后继节点，称为子节点（Children）。
  • 没有两个节点有相同的子节点，即树中没有环。
  • 树的子节点具有层次结构。

普通树

基础定义

  • 节点（Node）：树的每个元素。
  • 叶子节点（Leaf）：没有子节点的节点。
  • 内部节点（Internal Node）：至少有一个子节点的节点。
  • 高度（Height）：树中最长路径的边数。
  • 深度（Depth）：从根节点到该节点的边数。

双亲表示法

  • 每个节点包含指向父节点的指针。

基本实现思想：

  • 使用数组来存储树的所有节点，数组的每个元素代表一个节点。
  • 为每个节点设置一个父指针/索引，存储其双亲节点在数组中的指针/索引。

优点：

  • 通过双亲索引可以快速访问任一节点的所有祖先节点。

缺点：

  • 难以直接获取任一节点的孩子节点。
  • 节点的插入和删除操作较为复杂，需要更新双亲数组。

孩子表示法

  • 每个节点包含一个指向其子节点的链表或数组。

基本实现思想：

  • 节点结构中包含一个子节点列表，可以是单向链表或数组。
  • 通过遍历子节点列表来获取所有子节点。

优点：

  • 方便地添加和删除子节点。
  • 直接访问任一节点的所有子节点。

缺点：

  • 获取特定子节点（如第一个或最后一个）可能需要遍历整个子节点列表。

孩子兄弟表示法

  • 每个节点包含指向其第一个子节点和下一个兄弟节点的指针。

基本实现思想：

  • 节点结构中包含两个指针，一个指向第一个子节点，另一个指向下一个兄弟节点。
  • 通过兄弟指针可以遍历同一层的所有节点。

优点：

  • 方便地遍历同一层级的节点。
  • 插入和删除节点时，可以容易地维护兄弟关系。

缺点：

  • 需要额外的空间来存储兄弟指针。
  • 对于非叶子节点，需要单独的逻辑来管理子节点链表。

二叉树

顺序存储

  • 使用数组按照层次顺序存储二叉树的节点。
  • 根节点位于数组的第一个位置。
  • 对于任意节点，其左子节点的索引为 2 * i + 1，右子节点的索引为 2 * i + 2，其中 i 是该节点在数组中的索引。

优点：

  • 空间利用率高，不需要额外的指针。
  • 可以通过简单的计算直接访问任意节点的左右子节点。

缺点：

  • 树的深度固定，不适合动态变化的二叉树。
  • 需要特殊处理完全二叉树中数组中的空位。

链式存储

  • 每个节点包含数据和两个分别指向左右子节点的指针。

基本实现思想：

  • 节点结构中包含数据域和两个指针域，分别指向左子节点和右子节点。
  • 通过指针可以形成树的逻辑结构。

优点：

  • 灵活地表示各种形态的二叉树。
  • 插入和删除操作相对简单。

缺点：

  • 需要额外的空间来存储指针。
  • 遍历节点时需要递归或显式栈。

线索二叉树

线索二叉树：

  • 将二叉树中空的左子节点指针指向其前驱节点，空的右子节点指针指向其后继节点。

基本实现思想：

  • 在二叉树的节点中增加线索的概念，将原本空的子节点指针转换为线索。
  • 线索可以是“前驱线索”或“后继线索”。

优点：

  • 可以方便地进行树的中序遍历，无需栈空间。
  • 简化了某些遍历操作。

缺点：

  • 需要额外的空间来存储线索信息。
  • 更新节点时需要维护线索的正确性。

双向线索二叉树：

  • 每个节点包含指向左右子节点、左线索（指向前驱）和右线索（指向后继）的指针。

基本实现思想：

  • 在线索二叉树的基础上，为每个节点增加指向后继的线索。
  • 后继线索可以是其右子节点或其父节点的左子节点。

优点：

  • 可以方便地进行树的前序遍历和逆中序遍历。

缺点：

  • 线索的维护更加复杂，特别是在树结构发生变化时。

二叉树的遍历

遍历是按照某种顺序访问二叉树的所有节点的过程。

先序遍历：

  • 访问根节点，然后先序遍历左子树，最后先序遍历右子树。

中序遍历：

  • 中序遍历左子树，访问根节点，然后中序遍历右子树。

后序遍历：

  • 后序遍历左子树，后序遍历右子树，最后访问根节点。

层次遍历：

  • 按层次顺序访问节点，通常使用队列来实现。

哈夫曼树

哈夫曼树（Huffman Tree），也称为最优二叉树，是一种带权路径长度最短的二叉树，即给定一组叶子结点的权值，构造一棵二叉树，使得树的带权路径长度最小。

  • 树的每个叶子节点代表一个数据元素，非叶子节点代表这些数据元素的组合。

基本定义

路径和路径长度

  • 在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

结点的权及带权路径长度

  • 若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

树的带权路径长度

  • 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。$WPL=(W1L1+W2L2+ W3L3+…+WnLn)$

构造过程

哈夫曼树广泛应用于数据压缩算法中，如哈夫曼编码。

哈夫曼树的构造过程如下：

  1. 初始化：
    • 创建一个优先队列（可以是小顶堆），其中每个元素都是一个只包含一个节点的单节点树，节点的权值即为其频率或权重。
    • 将所有节点按照它们的权值从小到大插入优先队列。
  2. 合并节点：
    • 从优先队列中取出权值最小的两个节点（树）。
    • 创建一个新的内部节点作为这两个节点的父节点，其权值等于两个子节点的权值之和。
    • 将新的内部节点重新插入优先队列。
  3. 重复步骤2：
    • 重复上述过程，直到优先队列中只剩下一个节点（树）为止。这最后一个节点就是哈夫曼树的根节点。

哈夫曼编码

哈夫曼编码是一种使用变长编码表对数据进行编码的方法，其中编码表是根据数据中字符出现的频率来构建的。哈夫曼树就是用来生成这种编码表的工具。

构建哈夫曼编码：

  • 从根节点开始遍历树，向左走赋值为0，向右走赋值为1，直到到达叶子节点，这样就可以得到每个字符的哈夫曼编码。