小菜鸟

二叉树：结构、分类与遍历全解析

二叉树是一种每个节点最多有两个子树（左子树和右子树）的树形结构，是数据结构中的基础且重要的模型。其简洁的层次关系和灵活的操作特性，使其广泛应用于索引、表达式解析、人工智能等领域。本文将从性质、分类、存储到遍历，全面解析二叉树。

二叉树的基本性质

二叉树的核心性质描述了节点数量、层数、深度之间的关系，是理解其结构的基础：

1. 第 i 层节点数上限：
   二叉树第i层（根节点为第 1 层）上的节点数目至多为 2^(i-1)。
   • 例：第 3 层最多有 2^(3-1)=4 个节点。
2. 深度为 k 的节点总数上限：
   深度为k的二叉树至多有 2^k - 1 个节点（满二叉树的情况）。
   • 例：深度为 3 的满二叉树有 2^3 - 1 = 7 个节点。
3. 叶子节点与度为 2 的节点关系：
   对任何二叉树，若叶子节点数为n₀，度为 2 的节点数为n₂，则 n₀ = n₂ + 1。
   • 原理：总边数 = 总节点数 - 1，且总边数 = 度为 1 的节点数 + 2× 度为 2 的节点数，联立推导可得。
4. 完全二叉树的深度：
   具有n个节点的完全二叉树，深度为 ⌊log₂n⌋ + 1（⌊x⌋ 表示向下取整）。
   • 例：n=7时，深度为 ⌊log₂7⌋ + 1 = 2 + 1 = 3。

二叉树的分类

根据结构和特性，二叉树可分为以下几类：

普通二叉树

每个节点最多有 2 个子树（左子树和右子树），无其他约束。

二叉查找树（BST，Binary Search Tree）

核心特性：

Spark 连接 JDBC：读 MySQL 用 DataFrame，别用 JdbcRDD 了

Spark 连接关系型数据库（MySQL、PostgreSQL 等），有两种方式：

• JdbcRDD 只能读，不能写，代码繁琐。早期 RDD API，已过时
• DataFrame API 读写都支持，语法简洁，性能更好

准备工作：加驱动、配连接

1. 加 JDBC 驱动

<!-- Maven -->
<dependency>
  <groupId>mysql</groupId>
  <artifactId>mysql-connector-java</artifactId>
  <version>8.0.28</version>
</dependency>

如果用 spark-submit 提交：

spark-submit --jars mysql-connector-java-8.0.28.jar your-app.jar

2. 连接参数

val jdbcUrl = "jdbc:mysql://localhost:3306/test?useSSL=false"
val props = new java.util.Properties()
props.setProperty("user", "root")
props.setProperty("password", "123456")
props.setProperty("driver", "com.mysql.cj.jdbc.Driver")

MySQL 驱动类名：

DataFrame

读数据：从 MySQL 到 DataFrame

方式1：读整张表

val df = spark.read.jdbc(jdbcUrl, "user", props)
df.show()

Redis 过期提醒功能详解：基于键空间事件的实现

Redis 的 notify-keyspace-events 配置提供了键空间事件通知功能，可实时监听键的过期、删除、修改等事件，其中过期提醒是最常用的场景（如订单超时取消、会话过期清理等）。本文基于 Redis 6.0.10 版本，详解过期提醒的配置、订阅方式及实践注意事项。

核心原理：键空间事件（Keyspace Events）

Redis 的事件通知基于发布 - 订阅（Pub/Sub） 机制：当键发生特定操作（如过期、删除）时，Redis 会自动向指定频道发布事件消息，客户端通过订阅这些频道即可实时获取通知。

• 事件分类：
  • keyspace 事件：以 __keyspace@<db>__:<key> 为频道，消息为事件类型（如 expired）。
  • keyevent 事件：以 __keyevent@<db>__:<event> 为频道，消息为键名（如 order:1001）。
    （过期提醒通常关注 keyevent 事件，直接获取过期的键名。）

配置开启过期提醒

配置 notify-keyspace-events

在 redis.conf 中设置事件通知类型，开启过期事件（x）和键事件（E）：

notify-keyspace-events Ex

• E：启用 keyevent 事件（按事件类型订阅）。
• x：启用过期事件（键过期时触发）。

动态修改配置（无需重启）

点击劫持（Clickjacking）攻击与防御详解

点击劫持是一种隐蔽的前端攻击手段，攻击者通过巧妙的页面布局欺骗用户，使其在不知情的情况下点击恶意链接或执行非预期操作。这种攻击利用了浏览器对 iframe 的嵌套支持，具有较强的迷惑性。以下从攻击原理、危害及防御措施展开说明。

点击劫持的攻击原理

点击劫持的核心是通过透明图层覆盖合法页面，诱导用户点击，具体流程如下：

1. 构造恶意页面：攻击者创建一个页面，通过 iframe 嵌套目标网站（如银行、社交平台等含有敏感操作的页面），并将 iframe 设置为透明（opacity: 0）。
2. 覆盖视觉元素：在恶意页面上放置诱骗性内容（如 “领取红包”“点击抽奖” 等按钮），位置与 iframe 中目标网站的敏感操作按钮（如 “转账”“确认支付”）完全重合。
3. 诱导用户点击：用户看到的是恶意页面的诱骗内容，点击时实际点击的是透明 iframe 中的目标网站按钮，从而在用户不知情的情况下触发敏感操作（如确认转账、授权登录）。

示例场景：
攻击者制作一个 “免费领取会员” 的页面，透明 iframe 嵌套某支付平台的 “确认付款” 页面，用户点击 “领取” 时，实际触发了支付平台的付款操作。

点击劫持的危害

• 非授权操作：用户在不知情的情况下执行敏感操作（如转账、修改密码、授权第三方应用）。
• 隐私泄露：诱导用户点击后，可能触发个人信息的提交或数据泄露（如点击 “查看详情” 实际触发个人资料的公开）。
• 账号安全风险：若目标页面涉及账号操作（如绑定手机、更换邮箱），可能导致账号被劫持。

DES 对称加密算法详解

DES（Data Encryption Standard，数据加密标准）是一种经典的对称加密算法，尽管已逐渐被安全性更高的 AES 取代，但作为对称加密的重要里程碑，其设计思想对理解加密算法具有重要意义。

DES 的核心特性

• 对称加密：加密和解密使用相同的密钥，密钥长度固定为56 位（实际存储为 64 位，含 8 位奇偶校验位）。
• 分组加密：将明文按 64 位分组，逐组加密，最后一组不足 64 位时需填充。
• 安全性：由于密钥长度较短（56 位），在现代计算能力下可被暴力破解，安全性已不足，但仍在部分 legacy 系统中使用。
• 工作模式：支持 ECB、CBC、CFB 等多种分组加密模式（示例代码中未指定，默认使用 ECB 模式，安全性较低）。

DES 加密与解密流程解析

1. 加密过程（核心代码解析）

步骤 1：初始化随机数生成器

SecureRandom sr = new SecureRandom();

SecureRandom用于生成加密过程中所需的随机数，确保加密的随机性（尽管 DES 的安全性主要依赖密钥）。

步骤 2：处理密钥

DESKeySpec dks = new DESKeySpec(key); // 从密钥字节数组创建DES密钥规范
SecretKeyFactory keyFactory = SecretKeyFactory.getInstance("DES"); // 创建密钥工厂
SecretKey securekey = keyFactory.generateSecret(dks); // 生成符合DES标准的密钥

• DESKeySpec：验证密钥合法性（必须为 8 字节，对应 56 位有效密钥）。
• SecretKeyFactory：将原始密钥转换为 DES 算法可识别的SecretKey对象。

步骤 3：初始化加密器