数据结构与算法分析：树与哈希表（一）

遇到的问题，都有解决方案，希望我的博客能为你提供一点帮助。

一、概述

背景：链表处理大量数据时，线性访问耗时多。二叉查找树多数操作平均运行时间为 O (log N)，相对于链表树更加高效。

1.预备知识

1.1. 树的定义与基本概念

• ​树（Tree）​: 非线性数据结构，由节点（Node）和边（Edge）组成，满足以下条件：

  • 存在唯一根节点（Root），无父节点。
  • 除根节点外，每个节点有且仅有一个父节点。
  • 从根到任意节点有唯一路径，无环路。

• ​关键术语：

  • 根节点（Root）：树的顶端节点，没有父节点。

  • 子节点（Child）：一个节点的直接下级节点。

  • 父节点（Parent）：一个节点的直接上级节点。

  • 叶子节点（Leaf）：没有子节点的节点。

  • 内部节点（Internal Node）：至少有一个子节点的节点。

  • 子树（Subtree）：一个节点及其所有后代节点构成的树。

  • 边（Edge）：连接两个节点的线段。

  • 路径（Path）：从某一节点到其子孙节点的连续边序列。

  • 深度（Depth）：根节点到该节点的路径长度（根节点深度为0）。

  • 高度（Height）：节点到最深叶子节点的路径长度（叶子节点高度为0）。

  • 树的深度=树的高度

  • 节点所在的层（level）：从顶至底递增，根节点所在层为 1 。

  • 节点的度（degree）：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。

class TreeNode:def __init__(self, val, left=None, right=None):self.val = valself.left = leftself.right = rightdef plot_tree(root):"""可视化二叉树"""import matplotlib.pyplot as pltfrom matplotlib.patches import Circlefig, ax = plt.subplots(figsize=(10, 8))ax.set_aspect('equal')ax.axis('off')def get_height(node):if not node:return 0return 1 + max(get_height(node.left), get_height(node.right))tree_height = get_height(root)def plot_node(node, x, y, dx):if not node:return# 绘制当前节点circle = Circle((x, y), 0.3, fill=True, color='lightblue')ax.add_patch(circle)ax.text(x, y, str(node.val), ha='center', va='center', fontsize=12)# 绘制左子树if node.left:new_x = x - dxnew_y = y - 1ax.plot([x, new_x], [y-0.3, new_y+0.3], 'k-', lw=1.5)plot_node(node.left, new_x, new_y, dx/2)# 绘制右子树if node.right:new_x = x + dxnew_y = y - 1ax.plot([x, new_x], [y-0.3, new_y+0.3], 'k-', lw=1.5)plot_node(node.right, new_x, new_y, dx/2)plot_node(root, 0, tree_height-1, 2**(tree_height-2))plt.xlim(-2**(tree_height-1), 2**(tree_height-1))plt.ylim(-1, tree_height)plt.show()# 测试用例
if __name__ == "__main__":# 构建一个示例树#       1#      / \#     2   3#    / \#   4   5root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)plot_tree(root)

 

1.2树的递归定义

 递归定义是一种通过自我引用来描述数据结构或算法的方式。对于树这种分层结构，递归定义尤其自然，因为每个子树本身也是一棵树。递归定义包含两个关键部分：

1. ​基线条件（Base Case）​：定义最简单、不可再分的情况（通常是空树或叶子节点）。
2. ​递归条件（Recursive Case）​：通过组合更小的树来定义更大的树。 

通用树的递归定义

一个树可以是：

• ​空树​（基线条件），或者​一个根节点，连接若干个子树​（递归条件），每个子树本身也是树。

​数学表达：

T=∅或T=(v,{T1​,T2​,...,Tn​})

• v：根节点的值
• {T1​,T2​,...,Tn​}：子树集合

动态演示建树过程： 

import matplotlib.pyplot as plt
from matplotlib.patches import Circle
import timeclass TreeNode:def __init__(self, val, left=None, right=None):self.val = valself.left = leftself.right = rightdef build_tree_recursively(values, index=0):"""递归构建二叉树:param values: 节点值列表:param index: 当前节点索引:return: 构建好的树节点"""if index >= len(values) or values[index] is None:return Nonenode = TreeNode(values[index])# 递归构建左子树node.left = build_tree_recursively(values, 2*index+1)# 递归构建右子树node.right = build_tree_recursively(values, 2*index+2)return nodedef visualize_recursive_build(root, values):"""可视化递归构建过程:param root: 树的根节点:param values: 节点值列表"""fig, ax = plt.subplots(figsize=(12, 8))ax.set_aspect('equal')ax.axis('off')# 计算树的高度def get_height(node):if not node:return 0return 1 + max(get_height(node.left), get_height(node.right))tree_height = get_height(root)# 存储节点高度信息node_heights = {}def calc_heights(node):if not node:return 0h = 1 + max(calc_heights(node.left), calc_heights(node.right))node_heights[id(node)] = h - 1return hcalc_heights(root)# 递归构建并可视化def recursive_build_visualize(node, x, y, dx, depth=0, is_new=False):if not node:return# 绘制当前节点color = 'red' if is_new else 'lightblue'circle = Circle((x, y), 0.35, fill=True, color=color, alpha=0.8)ax.add_patch(circle)# 显示节点信息node_info = f"值: {node.val}\n深度: {depth}\n高度: {node_heights.get(id(node), 0)}"ax.text(x, y, node_info, ha='center', va='center', fontsize=10, bbox=dict(facecolor='white', alpha=0.7))plt.pause(0.5)  # 暂停0.5秒展示当前步骤# 递归构建左子树if 2*values.index(node.val)+1 < len(values) and values[2*values.index(node.val)+1] is not None:new_x = x - dxnew_y = y - 1.5ax.plot([x, new_x], [y-0.35, new_y+0.35], 'b-', lw=1.5, alpha=0.6)plt.pause(0.3)  # 展示连接线left_val = values[2*values.index(node.val)+1]left_node = TreeNode(left_val)node.left = left_noderecursive_build_visualize(left_node, new_x, new_y, dx/2, depth+1, True)# 递归构建右子树if 2*values.index(node.val)+2 < len(values) and values[2*values.index(node.val)+2] is not None:new_x = x + dxnew_y = y - 1.5ax.plot([x, new_x], [y-0.35, new_y+0.35], 'r-', lw=1.5, alpha=0.6)plt.pause(0.3)  # 展示连接线right_val = values[2*values.index(node.val)+2]right_node = TreeNode(right_val)node.right = right_noderecursive_build_visualize(right_node, new_x, new_y, dx/2, depth+1, True)# 开始可视化构建过程plt.title("递归构建二叉树过程 (红色:新添加节点)", pad=20)recursive_build_visualize(root, 0, tree_height-1, 2**(tree_height-2))plt.xlim(-2**(tree_height-1), 2**(tree_height-1))plt.ylim(-tree_height, tree_height)# 设置中文字体plt.rcParams['font.sans-serif'] = ['SimHei']  # 使用黑体显示中文plt.rcParams['axes.unicode_minus'] = False  # 解决负号显示问题plt.show()# 示例使用
if __name__ == "__main__":# 定义节点值列表 (None表示空节点)values = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]# 构建完整的树结构root = build_tree_recursively(values)# 可视化递归构建过程visualize_recursive_build(root, values)

演示视频可以在我的视频资源里看：20250330_101822-CSDN直播

2、二叉树（Binary Tree）

2.1. 定义

• 每个节点最多有两个子节点（左子节点和右子节点）。

• 结构示例：

  class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right

 二叉树的递归定义

一个二叉树可以是：

• ​空树​（基线条件），或者一个根节点，连接一个左子树和一个右子树​（递归条件），每个子树本身也是二叉树。

​数学表达：

或

2.2. 特殊二叉树类型

(1) 满二叉树（Full Binary Tree）

• 每个节点要么是叶子节点，要么恰好有两个子节点。

• 示例：

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

(2) 完全二叉树（Complete Binary Tree）

• 除最后一层外，其他层节点全满，且最后一层节点尽量靠左排列。

• 示例：

        1/   \2     3/ \   /4   5 6

(3) 二叉搜索树（BST, Binary Search Tree）

• 左子树所有节点值 < 根节点值 < 右子树所有节点值。

• 作用：支持高效查找、插入、删除（时间复杂度 O(log n)）。

• 示例：

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

  2.3树的遍历法

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

2.3.1. 深度优先遍历（DFS）

• 前序遍历（Preorder）：根 → 左 → 右
  示例：1 → 2 → 4 → 5 → 3 → 6 → 7

  def preorder(root):if not root: return []return [root.val] + preorder(root.left) + preorder(root.right)

• 中序遍历（Inorder）：左 → 根 → 右
  BST 中序遍历结果有序。
  示例：4 → 2 → 5 → 1 → 6 → 3 → 7

  def inorder(root):if not root: return []return inorder(root.left) + [root.val] + inorder(root.right)

• 后序遍历（Postorder）：左 → 右 → 根
  示例：4 → 5 → 2 → 6 → 7 → 3 → 1

  def postorder(root):if not root: return []return postorder(root.left) + postorder(root.right) + [root.val]

2.3.2. 广度优先遍历（BFS / 层序遍历）

• 按层次逐层访问节点。

• 示例：1 → 2 → 3 → 4 → 5 → 6 → 7

  from collections import deque
  def level_order(root):if not root: return []queue = deque([root])res = []while queue:node = queue.popleft()res.append(node.val)if node.left: queue.append(node.left)if node.right: queue.append(node.right)return res

  完整代码示例：

class TreeNode:"""二叉树节点类属性:val: 节点值left: 左子节点right: 右子节点"""def __init__(self, val=0, left=None, right=None):"""初始化二叉树节点参数:val: 节点值，默认为0left: 左子节点，默认为Noneright: 右子节点，默认为None"""self.val = valself.left = leftself.right = rightdef preorder(root):"""前序遍历二叉树参数:root: 二叉树根节点返回:包含前序遍历结果的列表"""if not root: return []return [root.val] + preorder(root.left) + preorder(root.right)def inorder(root):"""中序遍历二叉树参数:root: 二叉树根节点返回:包含中序遍历结果的列表"""if not root: return []return inorder(root.left) + [root.val] + inorder(root.right)def postorder(root):"""后序遍历二叉树参数:root: 二叉树根节点返回:包含后序遍历结果的列表"""if not root: return []return postorder(root.left) + postorder(root.right) + [root.val]from collections import deque
def level_order(root):"""层序遍历二叉树参数:root: 二叉树根节点返回:包含层序遍历结果的列表"""if not root: return []queue = deque([root])res = []while queue:node = queue.popleft()res.append(node.val)if node.left: queue.append(node.left)if node.right: queue.append(node.right)return res# 示例用法
if __name__ == "__main__":# 构建示例树#       1#      / \#     2   3#    / \ / \#   4  5 6 7root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)root.right.left = TreeNode(6)root.right.right = TreeNode(7)print("前序遍历:", preorder(root))print("中序遍历:", inorder(root))print("后序遍历:", postorder(root))print("层序遍历:", level_order(root))

 C++简易版

#include <iostream>
#include <vector>
#include <queue>using namespace std;// 二叉树节点结构体
struct TreeNode {int val;         // 节点存储的值TreeNode* left;  // 指向左子节点的指针TreeNode* right; // 指向右子节点的指针// 构造函数// 参数x: 节点存储的整数值TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 前序遍历二叉树（根-左-右）
// 参数root: 二叉树的根节点
// 返回值: 包含前序遍历结果的整数向量
vector<int> preorder(TreeNode* root) {if (!root) return {}; // 空树返回空向量vector<int> result;result.push_back(root->val); // 访问根节点vector<int> left = preorder(root->left); // 递归遍历左子树vector<int> right = preorder(root->right); // 递归遍历右子树result.insert(result.end(), left.begin(), left.end()); // 合并左子树结果result.insert(result.end(), right.begin(), right.end()); // 合并右子树结果return result;
}// 中序遍历二叉树（左-根-右）
// 参数root: 二叉树的根节点
// 返回值: 包含中序遍历结果的整数向量
vector<int> inorder(TreeNode* root) {if (!root) return {}; // 空树返回空向量vector<int> left = inorder(root->left); // 递归遍历左子树vector<int> result;result.push_back(root->val); // 访问根节点vector<int> right = inorder(root->right); // 递归遍历右子树left.insert(left.end(), result.begin(), result.end()); // 合并根节点结果left.insert(left.end(), right.begin(), right.end()); // 合并右子树结果return left;
}// 后序遍历二叉树（左-右-根）
// 参数root: 二叉树的根节点
// 返回值: 包含后序遍历结果的整数向量
vector<int> postorder(TreeNode* root) {if (!root) return {}; // 空树返回空向量vector<int> left = postorder(root->left); // 递归遍历左子树vector<int> right = postorder(root->right); // 递归遍历右子树right.push_back(root->val); // 访问根节点left.insert(left.end(), right.begin(), right.end()); // 合并右子树和根节点结果return left;
}// 层序遍历二叉树（广度优先）
// 参数root: 二叉树的根节点
// 返回值: 包含层序遍历结果的整数向量
vector<int> levelOrder(TreeNode* root) {if (!root) return {}; // 空树返回空向量queue<TreeNode*> q; // 使用队列辅助遍历q.push(root); // 根节点入队vector<int> result;while (!q.empty()) {TreeNode* node = q.front(); // 取出队首节点q.pop();result.push_back(node->val); // 访问当前节点if (node->left) q.push(node->left); // 左子节点入队if (node->right) q.push(node->right); // 右子节点入队}return result;
}int main() {// 构建示例树//       1//      / \//     2   3//    / \ / \//   4  5 6 7// 这是一个完全二叉树，用于测试各种遍历方法TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);root->right->left = new TreeNode(6);root->right->right = new TreeNode(7);cout << "前序遍历: ";for (int num : preorder(root)) {cout << num << " ";}cout << endl;cout << "中序遍历: ";for (int num : inorder(root)) {cout << num << " ";}cout << endl;cout << "后序遍历: ";for (int num : postorder(root)) {cout << num << " ";}cout << endl;cout << "层序遍历: ";for (int num : levelOrder(root)) {cout << num << " ";}cout << endl;// 释放内存delete root->right->right;delete root->right->left;delete root->left->right;delete root->left->left;delete root->right;delete root->left;delete root;return 0;
}

3.二叉树的数组表示 

核心思想：用连续的内存空间（数组）存储二叉树节点，通过索引计算确定节点间的父子关系。

适用场景

• 完全二叉树：数组表示最紧凑，无空间浪费。

• 非完全二叉树：可能存在空间浪费，需用特殊值标记空节点。

3.1、数组存储规则

3.1.1. 索引分配规则（适用于完美二叉树）

假设数组从 索引0 开始存储：

• 根节点：索引为 0。

• 父节点索引 i：

  • 左子节点索引：2*i + 1

  • 右子节点索引：2*i + 2

• 子节点索引 j：

  • 父节点索引：⌊(j-1)/2⌋（向下取整）

2. 空节点标记（非完美二叉树）

• 用特定值（如 None、null 或特殊符号）表示缺失的节点。

---

3.1.2、示例分析

示例1：完全二叉树的数组表示

• 树结构：

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

• 数组表示：

  [1, 2, 3, 4, 5, 6, 7]

  • 索引关系：

    • 根节点 1 的索引为 0。

    • 左子节点 2 的索引为 1（2*0+1）。

    • 右子节点 3 的索引为 2（2*0+2）。

    • 节点 4（索引 3）的父节点为 1（⌊(3-1)/2⌋=1）。

示例2：非完全二叉树的数组表示

• 树结构：

        1/   \2     3\     \5     7

• 数组表示（用 null 填充空缺）：

  [1, 2, 3, null, 5, null, 7]

  • 说明：

    • 索引 3（左子节点位置）为 null，表示节点 2 无左子节点。

    • 索引 5（右子节点位置）为 null，表示节点 3 无左子节点。

---

3.2、数组表示 vs. 链式表示

维度	数组表示	链式表示
空间效率	完全二叉树高效；非完全二叉树可能浪费空间	灵活，无空间浪费
访问速度	直接通过索引计算，速度快	需遍历指针，速度较慢
插入/删除	需要移动元素，效率低	修改指针即可，效率高
适用场景	完全二叉树、堆	任意二叉树（尤其是非完全树）

---

3.3、代码实现

3.3.1. 根据数组构建二叉树（链式结构）

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef build_tree(arr, i=0):if i >= len(arr) or arr[i] is None:return Noneroot = TreeNode(arr[i])root.left = build_tree(arr, 2*i + 1)root.right = build_tree(arr, 2*i + 2)return root# 示例：构建示例2的非完全二叉树
arr = [1, 2, 3, None, 5, None, 7]
root = build_tree(arr)

 C++版

#include <vector>
#include <queue>
#include <iostream>
using namespace std;/*** @brief 二叉树节点结构* @param val 存储的数据元素* @param left 指向左子节点的指针* @param right 指向右子节点的指针*  */
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x = 0, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(x), left(l), right(r) {}
};/*** @brief 根据数组构建二叉树* @param arr 包含二叉树节点值的数组，-1表示空节点* @param i 当前处理的数组索引，默认为0(根节点)* @return TreeNode* 构建完成的二叉树根节点* @note 使用完毕后需要调用deleteTree释放内存*/
TreeNode* buildTree(const vector<int>& arr, int i = 0) {// 参数校验if (arr.empty()) {return nullptr;}// 递归终止条件：索引越界或遇到空节点标记if (i < 0 || i >= arr.size() || arr[i] == -1) {return nullptr;}// 创建当前节点并递归构建左右子树TreeNode* root = new TreeNode(arr[i]);root->left = buildTree(arr, 2 * i + 1);root->right = buildTree(arr, 2 * i + 2);return root;
}/*** @brief 释放二叉树内存* @param root 二叉树根节点*/
void deleteTree(TreeNode* root) {if (!root) return;deleteTree(root->left);deleteTree(root->right);delete root;
}void printTree(TreeNode* root) {if (!root) {return;  // 空节点，直接返回  }queue<TreeNode*> q;  // 队列用于层次遍历    q.push(root);  // 根节点入队while (!q.empty()) {TreeNode* curr = q.front();q.pop();cout << curr->val << " ";  // 输出当前节点的值if (curr->left) {q.push(curr->left);  // 左子节点入队} else {}                 // 空节点，不做处理if (curr->right) {q.push(curr->right);  // 右子节点入队} else {}                 // 空节点，不做处理}   
}/*** @brief 演示二叉树构建和删除*/
int main() {// 示例数组表示二叉树vector<int> treeData = {1, 2, 3, -1, 4, 5, 6, -1, -1, 7, 8};// 构建二叉树TreeNode* root = buildTree(treeData);// 这里可以添加遍历或其他操作cout << "Tree in level order: ";printTree(root);cout << endl << "Tree deleted." << endl;// 释放内存deleteTree(root);return 0;

 

3.3.2. 将二叉树转为数组表示

def tree_to_array(root):if not root:return []queue = [root]res = []while queue:node = queue.pop(0)if node:res.append(node.val)queue.append(node.left)queue.append(node.right)else:res.append(None)# 去除末尾的 None（可选）while res and res[-1] is None:res.pop()return res# 示例：将链式树转回数组
print(tree_to_array(root))  # 输出 [1, 2, 3, None, 5, None, 7]

 c++版

#include <vector>
#include <queue>
#include <iostream>
#include <memory>
using namespace std;/*** @brief 二叉树节点结构* 使用智能指针管理内存，防止内存泄漏*/
struct TreeNode {int val;shared_ptr<TreeNode> left;shared_ptr<TreeNode> right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};/*** @brief 将二叉树转换为数组表示（层次遍历）* @param root 二叉树根节点* @return 包含节点值的vector，空节点用-1表示* @note 使用智能指针避免内存泄漏*/
vector<int> treeToArray(shared_ptr<TreeNode> root) {vector<int> result;if (!root) {return result;}queue<shared_ptr<TreeNode>> q;q.push(root);while (!q.empty()) {auto node = q.front();q.pop();if (node) {result.push_back(node->val);q.push(node->left);q.push(node->right);} else {result.push_back(-1); // 使用-1表示空节点}}// 去除末尾的-1（可选）while (!result.empty() && result.back() == -1) {result.pop_back();}return result;
}int main() {try {// 构建示例二叉树auto root = make_shared<TreeNode>(1);root->left = make_shared<TreeNode>(2);root->right = make_shared<TreeNode>(3);root->left->right = make_shared<TreeNode>(5);root->right->right = make_shared<TreeNode>(7);// 转换为数组并打印vector<int> arr = treeToArray(root);cout << "层次遍历结果: ";for (int val : arr) {cout << val << " ";}cout << endl;// 输出: 1 2 3 -1 5 -1 7 } catch (const exception& e) {cerr << "错误: " << e.what() << endl;return 1;}return 0;
}