一、树结构

1. 树的基础

• 树的性质：

  • 由n个节点组成的有限集合
  • 有且仅有一个根节点

• 重要术语：

  • 节点的度：该节点拥有的子树数量（直接子节点数）
  • 树的度：树中所有节点度的最大值
  • 示例：

    A  (度=3)
  / | \
 B  C  D   (B度=0, C度=2, D度=1)
    / \
   E   F

此树的度 = max({3,0,2,1}) = 3

• 层次：根为第1层，逐层递增

• 高度：从叶到根的最大层数

• 森林：由m（m≥0）棵互不相交的树组成的集合### 2. 特殊树

• （1）二叉树定义

  • 三大特征：

    1. 每个节点最多有两个子节点（左子节点和右子节点）
    2. 子树有明确的左右之分，次序不能颠倒
    3. 空树（节点数为0）也视为二叉树

  • 示例：

          A 
         / \  
        B   C  
       / \   \
      D   E   F
    

    （节点C只有右子节点F，仍符合二叉树定义）

（2）特殊二叉树

• 满二叉树

  • 特征：

    每层节点达到最大数

  • 典型示例：

         1
       /   \
      2     3
     / \   / \
    4   5 6   7
    

    （节点6缺少右兄弟，但仍是完全二叉树）

• 完全二叉树

  • 两大特征：

    1. 除最后一层外，其他层节点达到最大数
    2. 最后一层节点必须从左向右连续排列

  • 典型示例：

         1
       /   \
      2     3
     / \   /
    4   5 6
    

    （节点6缺少右兄弟，但仍是完全二叉树）

（3）特殊二叉树应用

• 堆的概念

  • 堆的本质：完全二叉树 + 堆序性质
  • 两种类型：

类型	性质	应用场景
大根堆	父节点值 ≥ 子节点值	优先队列（取最大）
小根堆	父节点值 ≤ 子节点值	定时任务调度

• 堆的操作：

  // 数组模拟堆（下标从1开始）
  int heap[100], size = 0;
  
  // 上浮调整（大根堆）
  void up(int pos) {
      while (pos > 1 && heap[pos] > heap[pos/2]) {
          swap(heap[pos], heap[pos/2]);
          pos /= 2;
      }
  }
  
  // 下沉调整（大根堆）
  void down(int pos) {
      int t = pos;
      if (2*pos <= size && heap[2*pos] > heap[t]) t = 2*pos;
      if (2*pos+1 <= size && heap[2*pos+1] > heap[t]) t = 2*pos+1;
      if (t != pos) {
          swap(heap[t], heap[pos]);
          down(t);
      }
  }
  

• 二叉搜索树（BST）

  • BST的本质：二叉树 + 排序性质

  • 核心性质：

    • 左子树所有节点值 < 根节点值
    • 右子树所有节点值 > 根节点值
    • 左右子树也必须满足BST性质

  • 操作复杂度：

操作	平均复杂度	最坏复杂度
查找	$O(\log n)$	$O(n)$
插入
删除

• BST结构示例：

         [8]
        /   \
      [3]    [10]
     /   \      \
   [1]   [6]    [14]
        /  \    /
      [4] [7][13]
  

  中序遍历结果：1,3,4,6,7,8,10,13,14

• BST的操作：

  // BST查找
  TreeNode* searchBST(TreeNode* root, int val) {
      if (!root || root->val == val) return root;
      return val < root->val ? searchBST(root->left, val) 
                            : searchBST(root->right, val);
  }
  // 判断是否是BST
  bool isBST(TreeNode* root, TreeNode* min = nullptr, TreeNode* max = nullptr) {
      if (!root) return true;
      if ((min && root->val <= min->val) || (max && root->val >= max->val))
          return false;
      return isBST(root->left, min, root) && 
             isBST(root->right, root, max);
  }
  

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

  • 哈夫曼树的本质：带权路径长度(WPL最短的二叉树

  • 核心性质：

    • 频率越高的字符编码越短
    • 满足前缀编码特性（无歧义解码）

  • 构建步骤：

    1. 将每个字符视为单节点树
    2. 每次选择权值最小的两棵树合并
    3. 新树权值为子树权值之和
    4. 重复直到只剩一棵树

  • 示例与编码：

字符	频率	编码
A	4	0
B	3	10
C	2	110
D	1	111

• 实现代码：

  struct HuffNode {
      char ch;
      int freq;
      HuffNode *left, *right;
  };
  
  void assignCodes(HuffNode* root, string code, unordered_map<char,string>& codes) {
      if (!root) return;
      if (!root->left && !root->right) {
          codes[root->ch] = code;
      }
      assignCodes(root->left, code+"0", codes);
      assignCodes(root->right, code+"1", codes);
  }
  

• 对比总结

特性	二叉搜索树	哈夫曼树
构建依据	节点插入顺序	字符出现频率
结构目标	快速查找	最优编码
时间复杂度	查找O(log n)~O(n)	构建O(n log n)
典型应用	数据库索引	文件压缩

二、图的系统讲解

1. 图的严格定义与分类

• 图的基本组成：

  • 顶点集合 V = {v₁, v₂, ..., vₙ}
  • 边集合 E = {e₁, e₂, ..., eₘ}

• 四大分类标准：

分类标准	类型	特点
方向性	无向图	边没有方向，(u,v)等同(v,u)
	有向图	边有方向， ≠
边权值	无权图	所有边权值相同（默认为1）
	带权图	边上有不同的权值
连通性	连通图（无向）	任意两顶点间有路径
	强连通图（有向）	任意两顶点双向可达
特殊结构	稀疏图	边数远少于完全图的边数
	稠密图	边数接近完全图的边数

2. 图的存储结构详解

（1）邻接矩阵

• 实现原理：

  • 使用二维数组g[N][N]存储
  • g[i][j]表示顶点i到j的边权（无权图用1/0表示是否存在边）

• 示例代码：

  const int N = 100;
  int g[N][N];  // 初始化为0
  
  // 添加无向边
  void addEdge(int u, int v) {
      g[u][v] = g[v][u] = 1;
  }
  
  // 检查边是否存在
  bool hasEdge(int u, int v) {
      return g[u][v] > 0;
  }
  

（2）邻接表

• 优化原理：

  • 对每个顶点维护一个链表，存储其邻接点
  • 适合稀疏图（空间复杂度O(V+E)）

• STL实现版：

  vector<int> adj[N];  // 无权图
  
  // 添加有向边
  void addEdge(int u, int v) {
      adj[u].push_back(v);
  }
  
  // 遍历u的邻接点
  for (int v : adj[u]) {
      cout << u << "->" << v << endl;
  }
  

3. 图的遍历基础

（1）DFS模板（递归版）

bool visited[N];
void dfs(int u) {
    visited[u] = true;
    cout << "Visit: " << u << endl;
    for (int v : adj[u]) {
        if (!visited[v]) dfs(v);
    }
}

（2）BFS模板（队列版）

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << "Visit: " << u << endl;
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

三、关键对比总结

数据结构	核心特征	适用场景	经典问题
完全二叉树	数组存储无浪费	堆结构实现	优先队列
二叉搜索树	左小右大的有序性	动态数据查找	单词频率统计
邻接矩阵	快速查询任意两顶点关系	稠密图存储	迷宫可达性判断
邻接表	节省存储空间	稀疏图处理	社交网络关系分析

1.二叉树 T，已知其前序遍历序列为 1 2 4 3 5 7 6，中序遍历序列为 4 2 1 5 7 3 6，则其后序遍历序列为（ ）。

{{ select(1) }}

• 4 2 5 7 6 3 1
• 4 2 7 5 6 3 1
• 4 2 7 5 3 6 1
• 4 7 2 3 5 6 1

2.前序遍历序列与后序遍历序列相同的二叉树为（ ）。

{{ select(2) }}

• 非叶子结点只有左子树的二叉树
• 只有根结点的二叉树
• 根结点无右子树的二叉树
• 非叶子结点只有右子树的二叉树

3.如果根的高度为 1，具有 61 个结点的完全二叉树的高度为（ ）。

{{ select(3) }}

• 5
• 6
• 7
• 8

4.一棵具有 5 层结点的满二叉树的结点数为（ ）。

{{ select(4) }}

• 31
• 32
• 33
• 16

5.表达式 a * (b + c) * d 的后缀形式是（ ）。

{{ select(5) }}

• a b c d * + *
• a b c + * d *
• a * b c + * d
• b + c * a * d

6.有向图中每个顶点的度等于该顶点的（ ）。

{{ select(6) }}

• 入度
• 出度
• 入度和出度之和
• 入度和出度之差

7.在无向图中，所有顶点的度数之和是边数的（ ）倍。

{{ select(7) }}

• 0.5
• 1
• 2
• 4

8.设 G 是有 6 个结点的完全无向图，要得到一颗生成树，需要从 G 中删去（ ）条边。

{{ select(8) }}

• 6
• 9
• 10
• 15

9.设 G 是有 n 个结点、m 条边 (n≤m) 的连通图，必须删去 G 的（ ）条边， 才能使得 G 变成一棵树。

{{ select(9) }}

• m - n + 1
• m - n
• m + n + 1
• n - m + 1

10.由四个没有区别的点构成的简单无向连通图的个数是（ ）。

{{ select(10) }}

• 6
• 7
• 8
• 9