数据结构和算法(5)

2025年05月11日 1.6k 字大概 6 分钟

二叉树、图

二叉树

定义：
每个节点最多有两个子节点的树结构，称为左子节点和右子节点。

类比：
1、像家族的家谱图，每个人（节点）最多有两个孩子（左孩子和右孩子）。
2、像游戏中的技能树，每个技能可能有两个分支。

例如: 
          50
         /  \
       30   70
      /  \  /  \
     20  40 60  80

核心术语：

根节点（Root）：树的顶层节点（没有父节点）。
叶子节点（Leaf）：没有子节点的节点。
深度（Depth）：根节点到当前节点的边数。
高度（Height）：当前节点到最远叶子节点的边数。
子树（Subtree）：以某个节点为根的子树

规则：

每个节点的子节点数量可为0、1、2。
如果有两个子节点，则其中一个子节点的值必须小于父节点的值，另一个子节点的值必须大于父节点。

查找

查找原理
利用BST的性质：
左子树所有节点值 < 根节点值
右子树所有节点值 > 根节点值
查找流程（迭代实现）步骤：

从根节点开始。
若当前节点值等于target_value，返回该节点。
若target_value < 当前节点值，进入左子树。
若target_value > 当前节点值，进入右子树。
若当前节点为空，返回None。

时间复杂度
在平均情况下，每次进行一步判断，我们都把一半的节点排除掉了，与二分查找法相比，有着相同的效率O(log N)
但是如果二叉树不够理想，在极端情况下，变成链表的形式，它的查看效率会退化成O(N)

插入

插入时我们需要先查找对应的结点，方便我们将数据插入到合适的位置。主要在于查找，它的效率是O(log N)，而插入只需要一步。即插入的效率为O(log N)

删除

删除是二叉树各种操作中最麻烦的一个。
需要遵守以下的规则：

如果要删除的结点没有子节点，直接删除；
如果要删除的节点上有一个子节点，那么把它删除之后，还要将子节点填到被删除节点的位置；
如果要删除的结点有两个子节点，则将该节点替换成其后继节点。一个节点的后继结点，就是所有比被删除节点大的子节点中最小的那个。
1. 如果后集结点带有右子节点，则在后继结点填补被删除节点以后，用此右子节点代替后继结点的父节点的左子结点。

图

图是一种善于处理关系类型的数据结构，有了它可以很轻松地表示数据之间是如何关联的。例如社交软件上一个人的关系网，

概念

顶点（Vertex）
图中的每个元素称为顶点（或节点）。顶点可以表示任何实体，如城市、人、网页等。
例如，在一个社交网络图中，每个用户可以是一个顶点。
边（Edge）
边是连接两个顶点的线，表示顶点之间的关系。
边可以是有向的（Directed Edge）或无向的（Undirected Edge）。
无向边：边没有方向，表示两个顶点之间的双向关系。例如，城市之间的道路。
有向边：边有方向，表示从一个顶点指向另一个顶点的单向关系。例如，网页之间的链接。
权重（Weight）
边可以有权重（Weight），表示边的“代价”或“距离”。权重可以是正数、负数或零。
例如，在交通网络中，边的权重可以表示两个城市之间的距离或旅行时间。

广度优先搜索

    A —— B
    |    |
    C —— D

广度优先搜索（Breadth-First Search，BFS）是一种用于遍历或搜索图的算法。它从根节点开始，逐层访问（由近及远）所有相邻节点，直到找到目标节点或遍历完整个结构。BFS的核心思想是“先广后深”，即先访问离起点最近的节点，再逐步扩展到更远的节点。适用于多种实际场景，如最短路径问题、社交网络分析和网络爬虫等。通过队列实现的逐层遍历策略，BFS能够高效地遍历图中的节点，确保找到从起点到其他节点的最短路径。

BFS步骤

初始化队列和访问标记
创建一个空队列queue。
创建一个空集合visited，用于标记已访问的节点。
将起点加入队列
假设起点是A。
将A加入队列：queue = [A]。
标记A为已访问：visited = {A}。
循环处理队列
队列不为空，继续处理
- 第1次循环
  - 从队列中取出一个节点：current_node = A。
  - 处理A（例如，打印A）。
  - 遍历A的所有邻接节点：B和C。
  - B未访问过，将B加入队列：queue = [B]，标记B为已访问：visited = {A, B}。
  - C未访问过，将C加入队列：queue = [B, C]，标记C为已访问：visited = {A, B, C}。
- 第2次循环
  - 从队列中取出一个节点：current_node = B。
  - 处理B（例如，打印B）。
  - 遍历B的所有邻接节点：A和D。
  - A已访问过，跳过。
  - D未访问过，将D加入队列：queue = [C, D]，标记D为已访问：visited = {A, B, C, D}。
- 第3次循环
  - 从队列中取出一个节点：current_node = C。
  - 处理C（例如，打印C）。
  - 遍历C的所有邻接节点：A和D。
  - A已访问过，跳过。
  - D已访问过，跳过。
- 第4次循环
  - 从队列中取出一个节点：current_node = D。
  - 处理D（例如，打印D）。
  - 遍历D的所有邻接节点：B和C。
  - B已访问过，跳过。
  - C已访问过，跳过。
结束条件

队列为空，BFS结束。

效率

让顶点出队，将其设置为当前顶点
访问每个顶点的邻接点

这么看来每个顶点都有出队的情况，那么有V个顶点就有V次出列，大O记法表示则为O(V)。
不仅顶点需要处理，边也需要处理。每条边对应的两个顶点。有E条边则需要2E步来访问邻接点。大O记法则表示为O(V+E)。