# 现代编程思想 树 Hongbo Zhang ## 数据结构：树 • 树 · 二叉树 • 二叉搜索树 • 二叉平衡树 ## 生活中的树状图 - 生活中有很多的数据的结构与一颗树相似 - 谱系图（又称，家族树） ☐ 文件结构 ☐ 数学表达式 , \left(0, 2\right), \left(1, 3\right) $$ ☐ 代数数据结构定义 线段树：每一个节点都存储了一根线段及对应的数据，适合一维查询 • 二叉树：每个节点至多有两个分支：左子树与右子树 - KD-Tree：支持K-维度的数据（例如平面中的点、空间中的点等）的存储与查询的二叉树，每一层更换分叉判定的维度 • B-Tree：适合顺序访问，利于硬盘存储数据 • R-Tree：存储空间几何结构 · ..... ## 数据结构：二叉树 - 二叉树要么是一棵空树，要么是一个节点；它最多具有两个子树：左子树与右子树。

1. 栈 5.2. 队列 5.3. 双向队列 5.4. 小结 6. 散列表 6.1. 哈希表 6.2. 哈希冲突 6.3. 小结 7. 树 7.1. 二叉树 7.2. 二叉树遍历 7.3. 二叉搜索树 7.4. AVL树* 7.5. 小结 8. 堆 8.1. 堆 8.2. 建堆操作* 8.3. 小结 102 110 129 [Image](/uploads/documents/1/9/2/f/192f937bf9fb0442c22f8fa4e104cd54/p35_2.jpg) 部分示例代码需要一些前置知识，包括数组、链表、二叉树、递归算法等。如果遇到看不懂的地方无需担心，可以在学习完后面章节后再来复习，现阶段先聚焦在理解空间复杂度含义和推算方法上。 ## 常数阶 $ O(1) $ 常数阶常见于数量与输入数据大小 n 递归函数产生的平方阶空间复杂度 ## 指数阶 $ O(2^{n}) $ 指数阶常见于二叉树。高度为 n 的「满二叉树」的结点数量为 $ 2^{n}-1 $ ，使用 $ O(2^{n}) $ 空间。 /// == File: space_complexity.java === /* 指数阶（建立满二叉树） */ TreeNode buildTree(int n) { if (n ==

3 双向队列 5.4 小结 第6章 哈希表 6.1 哈希表 6.2 哈希冲突 6.3 哈希算法 6.4 小结 第7章 树 7.1 二叉树 7.2 二叉树遍历 7.3 二叉树数组表示 7.4 二叉搜索树 7.5 AVL树* 7.6 小结 第8章 堆 8.1 堆 8.2 建堆操作 8.3 Top-K问题 8.4 小结 堆排序 11.8 桶排序 11.9 计数排序 11.10 基数排序 11.11 小结 第12章 分治 12.1 分治算法 12.2 分治搜索策略 12.3 构建二叉树问题 12.4 汉诺塔问题 12.5 小结 第13章 回溯 13.1 回溯算法 13.2 全排列问题 13.3 子集和问题 13.4 N皇后问题 13.5 小结 for (let i = 0; i < n; i++) { count++; } return count; } 图 2-13 展示了线性对数阶的生成方式。二叉树的每一层的操作总数都为 n，树共有 $ \log_{2}n + 1 $ 层，因此时间复杂度为 $ O(n\log n) $ 。 ![Image](/uploads/documents/8/c

3 双向队列 5.4 小结 第6章 哈希表 6.1 哈希表 6.2 哈希冲突 6.3 哈希算法 6.4 小结 第7章 树 7.1 二叉树 7.2 二叉树遍历 7.3 二叉树数组表示 7.4 二叉搜索树 7.5 AVL树* 7.6 小结 第8章 堆 8.1 堆 8.2 建堆操作 8.3 Top-K问题 8.4 小结 堆排序 11.8 桶排序 11.9 计数排序 11.10 基数排序 11.11 小结 第12章 分治 12.1 分治算法 12.2 分治搜索策略 12.3 构建二叉树问题 12.4 汉诺塔问题 12.5 小结 第13章 回溯 13.1 回溯算法 13.2 全排列问题 13.3 子集和问题 13.4 N皇后问题 13.5 小结 linear_log_recur(n // 2) for _ in range(n): count += 1 return count 图 2-13 展示了线性对数阶的生成方式。二叉树的每一层的操作总数都为 n，树共有 $ \log_{2}n + 1 $ 层，因此时间复杂度为 $ O(n\log n) $ 。 ![Image](/uploads/documents/f/f/

3 双向队列 5.4 小结 第6章 哈希表 6.1 哈希表 6.2 哈希冲突 6.3 哈希算法 6.4 小结 第7章 树 7.1 二叉树 7.2 二叉树遍历 7.3 二叉树数组表示 7.4 二叉搜索树 7.5 AVL树* 7.6 小结 第8章 堆 8.1 堆 8.2 建堆操作 8.3 Top-k 问题 8.4 小结 堆排序 11.8 桶排序 11.9 计数排序 11.10 基数排序 11.11 小结 第12章 分治 12.1 分治算法 12.2 分治搜索策略 12.3 构建二叉树问题 12.4 汉诺塔问题 12.5 小结 第13章 回溯 13.1 回溯算法 13.2 全排列问题 13.3 子集和问题 13.4 n 皇后问题 13.5 小结 for (int i = 0; i < n; i++) { count++; } return count; } 图 2-13 展示了线性对数阶的生成方式。二叉树的每一层的操作总数都为 n，树共有 $ \log_{2}n + 1 $ 层，因此时间复杂度为 $ O(n\log n) $ 。 ![Image](/uploads/documents/0/c/

1. 栈 5.2. 队列 5.3. 双向队列 5.4. 小结 6. 散列表 6.1. 哈希表 6.2. 哈希冲突 6.3. 小结 7. 树 7.1. 二叉树 7.2. 二叉树遍历 7.3. 二叉搜索树 7.4. AVL树* 7.5. 小结 8. 堆 8.1. 堆 8.2. 建堆操作* 8.3. 小结 10. 123 13 [Image](/uploads/documents/c/4/2/1/c4210fafaddf269065f9c0217e1393df/p35_2.jpg) 部分示例代码需要一些前置知识，包括数组、链表、二叉树、递归算法等。如果遇到看不懂的地方无需担心，可以在学习完后面章节后再来复习，现阶段先聚焦在理解空间复杂度含义和推算方法上。 ## 常数阶 $ O(1) $ 常数阶常见于数量与输入数据大小 n 无关的常量、变量、对象。 递归函数产生的平方阶空间复杂度 ## 指数阶 $ O(2^{n}) $ 指数阶常见于二叉树。高度为 n 的「满二叉树」的结点数量为 $ 2^{n}-1 $ ，使用 $ O(2^{n}) $ 空间。 /// == File: space_complexity.go === /* 指数阶（建立满二叉树） */ func buildTree(n int) *treeNode { if

3 双向队列 5.4 小结 第6章 哈希表 6.1 哈希表 6.2 哈希冲突 6.3 哈希算法 6.4 小结 第7章 树 7.1 二叉树 7.2 二叉树遍历 7.3 二叉树数组表示 7.4 二叉搜索树 7.5 AVL树* 7.6 小结 第8章 堆 8.1 堆 8.2 建堆操作 8.3 Top-k 问题 8.4 小结 堆排序 11.8 桶排序 11.9 计数排序 11.10 基数排序 11.11 小结 第12章 分治 12.1 分治算法 12.2 分治搜索策略 12.3 构建二叉树问题 12.4 汉诺塔问题 12.5 小结 第13章 回溯 13.1 回溯算法 13.2 全排列问题 13.3 子集和问题 13.4 n 皇后问题 13.5 小结 stride(from: 0, to: n, by: 1) { count += 1 } return count } 图 2-13 展示了线性对数阶的生成方式。二叉树的每一层的操作总数都为 n，树共有 $ \log_{2}n + 1 $ 层，因此时间复杂度为 $ O(n\log n) $ 。 ![Image](/uploads/documents/d/0/

1. 栈 5.2. 队列 5.3. 双向队列 5.4. 小结 6. 散列表 6.1. 哈希表 6.2. 哈希冲突 6.3. 小结 7. 树 7.1. 二叉树 7.2. 二叉树遍历 7.3. 二叉搜索树 7.4. AVL树* 7.5. 小结 8. 堆 8.1. 堆 8.2. 建堆操作* 8.3. 小结 9. 图 126 9.1. [Image](/uploads/documents/a/3/6/c/a36c6607364e062c2c586d931dafcdb3/p33_2.jpg) 部分示例代码需要一些前置知识，包括数组、链表、二叉树、递归算法等。如果遇到看不懂的地方无需担心，可以在学习完后面章节后再来复习，现阶段先聚焦在理解空间复杂度含义和推算方法上。 ## 常数阶 $ O(1) $ 常数阶常见于数量与输入数据大小 n ## 指数阶 $ O(2^{n}) $ 指数阶常见于二叉树。高度为 n 的「满二叉树」的结点数量为 $ 2^{n}-1 $ ，使用 $ O(2^{n}) $ 空间。 # === File: space_complexity.py === def build_tree(n): """ 指数阶（建立满二叉树）""" if n ==

1. 栈 5.2. 队列 5.3. 双向队列 5.4. 小结 6. 散列表 6.1. 哈希表 6.2. 哈希冲突 6.3. 小结 7. 树 7.1. 二叉树 7.2. 二叉树遍历 7.3. 二叉搜索树 7.4. AVL树* 7.5. 小结 8. 堆 8.1. 堆 8.2. 建堆操作* 8.3. 小结 101 109 120 [Image](/uploads/documents/8/3/4/8/834807da689a19f979d0c329c637b2bd/p35_1.jpg) 部分示例代码需要一些前置知识，包括数组、链表、二叉树、递归算法等。如果遇到看不懂的地方无需担心，可以在学习完后面章节后再来复习，现阶段先聚焦在理解空间复杂度含义和推算方法上。 ## 常数阶 $ O(1) $ 常数阶常见于数量与输入数据大小 n 递归函数产生的平方阶空间复杂度 ## 指数阶 $ O(2^{n}) $ 指数阶常见于二叉树。高度为 n 的「满二叉树」的结点数量为 $ 2^{n}-1 $ ，使用 $ O(2^{n}) $ 空间。 /// == File: space_complexity.js === /* 指数阶（建立满二叉树） */ function buildTree(n) { if (n === 0)

1. 栈 5.2. 队列 5.3. 双向队列 5.4. 小结 6. 散列表 6.1. 哈希表 6.2. 哈希冲突 6.3. 小结 7. 树 7.1. 二叉树 7.2. 二叉树遍历 7.3. 二叉搜索树 7.4. AVL树* 7.5. 小结 8. 堆 8.1. 堆 8.2. 建堆操作* 8.3. 小结 9. 图 136 9.1. [Image](/uploads/documents/6/e/4/9/6e491024041f225ae5bbf102c9220f0f/p35_2.jpg) 部分示例代码需要一些前置知识，包括数组、链表、二叉树、递归算法等。如果遇到看不懂的地方无需担心，可以在学习完后面章节后再来复习，现阶段先聚焦在理解空间复杂度含义和推算方法上。 ## 常数阶 $ O(1) $ 常数阶常见于数量与输入数据大小 n 递归函数产生的平方阶空间复杂度 ## 指数阶 $ O(2^{n}) $ 指数阶常见于二叉树。高度为 n 的「满二叉树」的结点数量为 $ 2^{n}-1 $ ，使用 $ O(2^{n}) $ 空间。 /// == File: space_complexity.swift === /* 指数阶（建立满二叉树） */ func buildTree(n: Int) -> TreeNode?